Cómo implementar Backtracking en JavaScript
El backtracking es una técnica de búsqueda y exploración utilizada en problemas que requieren encontrar soluciones mediante prueba y error, descartando opciones inválidas y retrocediendo cuando sea necesario. En este artículo, te enseñaré cómo funciona esta estrategia y cómo implementarla en JavaScript, con ejemplos prácticos.
📌 ¿Qué es el Backtracking?
El backtracking es un algoritmo que usa una búsqueda recursiva para resolver problemas al explorar todas las posibilidades de una solución y descartar aquellas que no cumplen con los requisitos. Se basa en la idea de:
1. Intentar una solución parcial.
2. Verificar si es válida.
3. Si no lo es, retroceder y probar otra opción.
4. Si lo es, continuar hasta encontrar una solución completa.
Algunos problemas clásicos que se resuelven con backtracking son:
- El problema de las N reinas ♔
- El Sudoku 🧩
- La búsqueda de caminos en laberintos 🏁
- La generación de combinaciones y permutaciones 🔢
✨ Implementación del Backtracking en JavaScript
Vamos a ilustrar el backtracking con tres ejemplos clásicos: resolver un Sudoku, el problema de las N reinas y la generación de combinaciones.
🧩 1. Resolver un Sudoku con Backtracking
Un Sudoku es un juego de lógica donde debemos llenar una cuadrícula de 9x9 con números del 1 al 9, asegurándonos de que no se repitan en filas, columnas y subcuadrantes de 3x3.
Código en JavaScript:
function esValido(tablero, fila, columna, num) {
for (let i = 0; i < 9; i++) {
if (tablero[fila][i] === num || tablero[i][columna] === num) {
return false;
}
}
let subFila = Math.floor(fila / 3) * 3;
let subColumna = Math.floor(columna / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (tablero[subFila + i][subColumna + j] === num) {
return false;
}
}
}
return true;
}
function resolverSudoku(tablero) {
for (let fila = 0; fila < 9; fila++) {
for (let columna = 0; columna < 9; columna++) {
if (tablero[fila][columna] === 0) {
for (let num = 1; num <= 9; num++) {
if (esValido(tablero, fila, columna, num)) {
tablero[fila][columna] = num;
if (resolverSudoku(tablero)) {
return true;
}
tablero[fila][columna] = 0;
}
}
return false;
}
}
}
return true;
}
// Prueba con un tablero incompleto
let sudoku = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
];
resolverSudoku(sudoku);
console.log(sudoku);📝 Explicación del código:
-
esValido()verifica si un número puede colocarse en una celda sin romper las reglas. -
resolverSudoku()recorre el tablero en busca de espacios vacíos (0) e intenta llenarlos con un número válido. - Usa recursión y retroceso (backtracking) si una decisión no lleva a una solución.
♔ 2. Resolver el problema de las N Reinas
Este problema consiste en colocar N reinas en un tablero de ajedrez NxN de forma que ninguna se ataque entre sí (no pueden compartir la misma fila, columna ni diagonal).
Código en JavaScript:
function esSeguro(tablero, fila, columna, n) {
for (let i = 0; i < fila; i++) {
if (tablero[i] === columna || tablero[i] - i === columna - fila || tablero[i] + i === columna + fila) {
return false;
}
}
return true;
}
function resolverNReinas(n, fila = 0, tablero = [], soluciones = []) {
if (fila === n) {
soluciones.push([...tablero]);
return;
}
for (let columna = 0; columna < n; columna++) {
if (esSeguro(tablero, fila, columna, n)) {
tablero[fila] = columna;
resolverNReinas(n, fila + 1, tablero, soluciones);
}
}
}
let soluciones = [];
resolverNReinas(8, 0, [], soluciones);
console.log(soluciones);📌 Explicación:
- Se usa una lista de soluciones.
-
esSeguro()verifica si es posible colocar una reina en la fila sin ser atacada. - Se prueban todas las opciones y se retrocede si una colocación no es válida.
🔢 3. Generar combinaciones de un conjunto
El backtracking también es útil para generar combinaciones. Por ejemplo, encontrar todas las combinaciones posibles de k elementos en un conjunto.
Código en JavaScript:
function generarCombinaciones(arr, k, inicio = 0, combinacion = [], resultado = []) {
if (combinacion.length === k) {
resultado.push([...combinacion]);
return;
}
for (let i = inicio; i < arr.length; i++) {
combinacion.push(arr[i]);
generarCombinaciones(arr, k, i + 1, combinacion, resultado);
combinacion.pop();
}
}
let resultado = [];
generarCombinaciones([1, 2, 3, 4], 2, 0, [], resultado);
console.log(resultado);📌 Explicación:
- Se exploran todas las combinaciones posibles sin repetir elementos.
-
Se usa una lista temporal (
combinacion) para almacenar soluciones parciales.
📢 Conclusión
El backtracking es una estrategia poderosa y versátil en algoritmos de búsqueda y generación de combinaciones. Aunque puede ser costoso en términos de tiempo de ejecución, es una de las formas más intuitivas de resolver problemas de exploración. 🚀
Jorge García
Fullstack developer