Red101

Hace unas semanas estuve durante un par de tardes programando un applet resolvedor de sudokus. El applet es muy sencillo, y desarrollándolo he visto que resolver un sudoku es básicamente un proceso mecánico. Esto ha hecho que pierda todo el interés en este tipo de puzzles, así que… nunca volveré a perder el tiempo resolviendo un sudoku.

El algoritmo es básicamente así:

Paso 1: Preparación
- A cada celda cuyo valor desconocemos le asociamos la lista de valores “123456789″

Paso 2: Eliminación de números en listas
- Para cada celda desconocida, miramos su fila, su columna y su cuadro de 3×3 correspondientes. En la lista marcamos como “no válidos” los números conocidos que veamos. Después de esto, la lista para una celda podría ser algo así como: 1—5—9, indicando que por el momento hemos descubierto que los únicos números válidos para dicha celda serían el 1, el 5 y el 9.

Con este método habrá celdas para las que nos quedemos con un único número. Ejemplo: —–6—

En este último caso marcamos la celda como “completada”, damos el número por válido y volvemos a aplicar el paso 2 para todas las celdas (incluso para las que ya lo habíamos aplicado), ya que descubrir un nuevo valor fijo puede desencadenar el descubrimiento de nuevos valores por este mismo procedimiento.

Paso 3: Búsqueda de valores únicos
Para cada fila, cada columna y cada región hacemos lo siguiente:
contamos las veces que aparece cada número en las listas que hemos obtenido en el paso anterior.

Si un número sólo aparece una vez, entonces marcamos la celda en la que sale dicho número como “completada”. En dicho caso volvemos a iniciar el proceso desde el paso 2.

Ejemplo:
Si en un cuadro de 3×3 tuviésemos las siguientes listas:

–3—78- —4–789 1-3-5-78-
–3-5-78- 12——- –3-5-78-
1—-6— -23—7– ——–9

podemos llegar a la conclusión de que el número 4 debe ir en la segunda celda, ya que aunque en principio, siguiendo el método del paso 2 hemos visto que los números posibles para la segunda celda son 4,7,8 y 9, esta es la única celda de este grupo en la que aparece el 4, con lo que por fuerza debe ir ahí.

Aplicando estas reglas repetidamente, se puede resolver la gran mayoría de los sudokus. Si después de aplicarlas aún nos quedaran celdas con varios números, entonces haríamos lo siguiente:

Paso 4: tratar de adivinar
Coger una celda que tenga todavía una lista con varios números, y asumir que uno de ellos es el bueno.
Aplicar de nuevo el algoritmo desde el paso 2. (esto convierte el algoritmo en recursivo)
Haciendo esto pueden pasar 2 cosas:

- El sudoku se resuelve definitivamente! FIN.
- llegamos a un estado inconsistente y el sudoku no se puede resolver. En este caso deshacemos los cambios que hayamos hecho y volvemos a aplicar el paso 4 para otro número distinto.

En breve publicaré el código del applet, que probablemente sea más claro y autoexplicativo.