Construyendo un solver de Sudoku desde cero en el navegador
Un análisis profundo de la propagación de restricciones, búsqueda con backtracking, y cómo hacerlo lo suficientemente rápido para que se sienta instantáneo — sin servidor, sin dependencias.
Quería entender cómo funcionan los solvers de restricciones a un nivel fundamental, así que construí un solver de Sudoku completamente en el navegador con cero dependencias. El resultado resuelve cualquier puzzle válido en menos de 2ms.
El algoritmo: propagación de restricciones + backtracking
La clave está en que no necesitas probar cada posibilidad. Antes del backtracking, propagas restricciones: si una celda solo puede tener un valor, asígnalo. Si una unidad (fila, columna, caja) solo puede colocar un dígito en una celda, colócalo ahí. Esto solo resuelve la mayoría de los puzzles de nivel periódico sin ninguna búsqueda.
function propagate(grid: Grid, cell: number, digit: number): Grid | false {
const peers = PEERS[cell];
for (const peer of peers) {
const result = eliminate(grid, peer, digit);
if (result === false) return false;
grid = result;
}
return grid;
}Representando el tablero como bitmask
Cada celda almacena un entero de 9 bits donde cada bit representa si ese dígito todavía es posible. Esto hace que la intersección y eliminación sean operaciones O(1) en lugar de recorridos de array. El tablero completo es un typed array de 81 valores uint16 — 162 bytes.
El objetivo no era solo resolver Sudoku. Era construir algo que te enseñe cómo piensa.