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.
Por qué importa
Las operaciones de bits son dramáticamente más rápidas que los métodos de array en bucles ajustados. En un motor V8 moderno, un solve completo con backtracking tarda ~0.4ms en los puzzles más difíciles conocidos. La UI se mantiene a 60fps incluso resolviendo dentro de un requestAnimationFrame.
La UI: hacer que se sienta viva
El tablero se renderiza en un elemento Canvas por rendimiento, con una capa de estado de React encima para la selección de celdas. La propagación de restricciones corre de forma reactiva mientras escribes, resaltando en rojo las celdas que se convertirían en contradicciones — así ves al solver pensar en tiempo real.
El objetivo no era solo resolver Sudoku. Era construir algo que te enseñe cómo piensa.