# Backtracking
Es una técnica recursiva en donde tratamos de construir la solución a un problema de forma incremental.

Podemos verlo así: vamos colocando pieza por pieza, validando que al colocarla la solución hasta ese momento siga siendo válida. Si sigue siendo válida, continuamos, si no, "cortamos" esa solución y ya no seguimos intentando más.

El backtracking sigue siendo un tipo de fuerza bruta, pero más optimizada. La diferencia es que la fuerza bruta intenta todas las combinaciones y hasta el final verifica que sean válidas, pero el backtracking checa la validez en todo momento, pudiendo así descartar candidatos desde mucho antes.

Para generar todas las soluciones, intentamos colocar un elemento en la posición actual que vayamos. Después, llamamos de forma recursiva a la función en la siguiente posición, y luego quitamos el elemento que colocamos. De ahí el nombre.

## Sudoku
Dado un tablero de números de $9 \times 9$ dividido en 9 subcuadrados de $3 \times 3$ donde cada casilla tiene un número del 1 al 9, determinar todas las posibles soluciones de un tablero parcialmente lleno abjo las siguientes reglas:
- En cada fila y en cada columna no puede haber números repetidos, es decir, cada número del 1 al 9 aparece exactamente una vez.
- En cada subcuadrado se cumple lo mismo, todos los números del 1 al 9 aparecen exactamente una vez.

Ejemplo:

Vamos a ir recorriendo cada una de las 81 casillas y en donde no haya un número en negro, vamos a intentar colocar todos los números posibles que no violen las reglas descritas. Si logramos llenar las 81 casillas, ya garantizamos que hay solución.

**Solución:**

#include <bits/stdc++.h>
using namespace std;

int tablero[9][9];
int cnt = 0;

// Backtracking
void resuelve(int fila, int columna){
	// Revisar si ya terminamos de llenar el tablero
	if(fila == 9 && columna == 0){
		// Ya encontramos una solución válida hasta este punto
		// Hacer algo con la solución encontrada
		cnt++;
		cout << "Solución #" << cnt << ":\n";
		for(int i = 0; i < 9; ++i){
			for(int j = 0; j < 9; ++j){
				cout << tablero[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
		return;
	}
	// Checo si soy una casilla vacía
	if(tablero[fila][columna] == 0){
		// Vamos a intentar colocar un número en la casilla actual (fila, columna)
		vector<bool> esValido(10, true);
		// Descartar números en la fila actual
		for(int j = 0; j < 9; ++j){
			esValido[tablero[fila][j]] = false;
		}
		// Descartar números en la columna actual
		for(int i = 0; i < 9; ++i){
			esValido[tablero[i][columna]] = false;
		}
		// Descartar números en el subcuadrado actual
		// Hallamos los límites de mi subcuadrado
		int inicioFila = 3 * (fila / 3), inicioColumna = 3 * (columna / 3);
		int finFila = inicioFila + 2, finColumna = inicioColumna + 2;
		for(int i = inicioFila; i <= finFila; ++i){
			for(int j = inicioColumna; j <= finColumna; ++j){
				esValido[tablero[i][j]] = false;
			}
		}
		// Intentar colocar en (fila, columna) los números válidos
		for(int d = 1; d <= 9; ++d){
			// Solo colocamos números válidos
			if(esValido[d]){
				// Lo colocamos
				tablero[fila][columna] = d;
				// Avanzamos una posición
				int sigFila = fila, sigColumna = columna + 1;
				if(sigColumna == 9){
					sigColumna = 0;
					sigFila++;
				}
				resuelve(sigFila, sigColumna);
				// Quitar el dígito actual para dar paso a otras soluciones
				tablero[fila][columna] = 0;
			}
		}
	}else{
		// La casilla no está vacía, simplemente avanzamos
		int sigFila = fila, sigColumna = columna + 1;
		if(sigColumna == 9){
			sigColumna = 0;
			sigFila++;
		}
		resuelve(sigFila, sigColumna);
	}
}

int main(){
	// Leer el tablero de la entrada
	for(int i = 0; i < 9; ++i){
		for(int j = 0; j < 9; ++j){
			cin >> tablero[i][j];
		}
	}
	// Hallar todas las soluciones
	resuelve(0, 0);
	return 0;
}

Problema: [link](https://projecteuler.net/problem=96)

## N-reinas
Colocar $n$ reinas en un tablero de ajedrez de $n \times n$ tal que ninguna se ataque entre sí. Dos reinas se atacan si están en la misma fila, columna o diagonal.

Ejemplo, para $n=8$, una posible configuración es:

Solución:

#include <bits/stdc++.h>
using namespace std;

int tablero[20][20];
int n;

int cnt = 0;

bool esValido(int fila, int columna){
	// Todos los chequeos se hacen a mi izquierda

	// Checar si la reina en (fila, columna) no colisiona con otra en la misma fila
	for(int j = 0; j < columna; ++j){
		if(tablero[fila][j] == 1){
			return false;
		}
	}

	// Checar la diagonal que va hacia arriba.
	// Por ejemplo, si estamos en (2, 3), entonces la diagonal de arriba consiste de las casillas (1, 2) y (0, 1)
	for(int i = fila-1, j = columna-1; i >= 0 && j >= 0; --i, --j){
		if(tablero[i][j] == 1){
			return false;
		}
	}

	// Checar la diagonal que va hacia abajo.
	// Por ejemplo, si estamos en (2, 3), la diagonal de abajo es (3, 2), (4, 1) y (5, 0)
	for(int i = fila+1, j = columna-1; i < n && j >= 0; ++i, --j){
		if(tablero[i][j] == 1){
			return false;
		}
	}

	// Es válido colocar una reina aqui
	return true;
}

void resuelve(int columna){
	if(columna == n){
		// Procesar la solución
		cnt++;
		cout << "Solucion #" << cnt << ":\n";
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				cout << tablero[i][j] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
		return;
	}
	// Intentar colocar una reina en cada posición de la columna actual y avanzamos
	for(int fila = 0; fila < n; ++fila){
		// Verificar que en la posición actual pueda colocar una reina
		if(esValido(fila, columna)){
			// La colocamos
			tablero[fila][columna] = 1;
			// Avanzamos recursivamente
			resuelve(columna + 1);
			// La quitamos
			tablero[fila][columna] = 0;
		}
	}
}

int main(){
	cin >> n;
	resuelve(0);
	return 0;
}

## Imprimir todas las permutaciones de una cadena
Dada una cadena $s$, imprimir todas sus posibles permutaciones.
Por ejemplo, si $s="abc"$, entonces:
- abc
- acb
- bac
- bca
- cab
- cba
La idea de solución es llevar la posición en la que estoy dentro de la cadena y por cada letra que esté a mi derecha incluyéndome, la intercambio conmigo y avanzo una posición.

Solución:

#include <bits/stdc++.h>
using namespace std;

string s;

void resuelve(int inicio){
	if(inicio == s.size()){
		cout << s << "\n";
	}else{
		for(int i = inicio; i < s.size(); ++i){
			swap(s[inicio], s[i]);
			resuelve(inicio + 1);
			swap(s[inicio], s[i]);
		}
	}
}

int main(){
	cin >> s;
	cout << "\n";
	resuelve(0);
	return 0;
}

## Soluciones a la ecuación
Dados los coeficientes enteros positivos $a_1, a_2, \ldots, a_m$ y un valor de $n$, queremos hallar todas las soluciones enteras no negativas de la ecuación $a_1x_1 + a_2x_2 + \ldots + a_mx_m = n$.

Ejemplo: si $a_1=1, a_2=2$ y $n=6$, entonces la ecuación a resolver es $x_1+2x_2=6$, cuyas soluciones son:
- $x_1=0, x_2=3$
- $x_1=2, x_2=2$
- $x_1=4, x_2=1$
- $x_1=6, x_2=0$

Solución:

#include <bits/stdc++.h>
using namespace std;

void resuelve(int posicion, const vector<int> & a, vector<int> & x, int resto){
	if(posicion == a.size()){
		if(resto == 0){
			for(int xi : x){
				cout << xi << " ";
			}
			cout << "\n";
		}
	}else{
		for(int xi = 0; xi <= resto/a[posicion]; ++xi){
			x[posicion] = xi;
			resuelve(posicion + 1, a, x, resto - a[posicion]*xi);
			x[posicion] = -1;
		}
	}
}

int main(){
	int m;
	cin >> m;
	vector<int> a(m), x(m, -1);
	for(int & ai : a){
		cin >> ai;
	}
	int n;
	cin >> n;
	resuelve(0, a, x, n);
	return 0;
}

## Problema: More or less
[Link al problema](https://codeforces.com/gym/102343/problem/F)