Técnicas de Resolución de Sudokus
El Sudoku es un rompecabezas que se resuelve mediante lógica (no son necesarios
ni adivinar ni la aritmética). La idea básica para completar los rompecabezas es
encontrar celdas para las que conocemos un único candidato.
Lo Básico
Las reglas del Sudoku son que debemos rellenar con un número cada celda de la cuadrícula,
utilizando los números del 1 al 9. Las restricciones son que sólo podemos usar cada
número una sola vez en cada fila, cada columna y cada uno de los recuadros de 3x3.
Echemos un vistazo a este puzzle incompleto...
Los tres interrogantes se encuentran en sitios en los que no hay ningún valor, pero
en los que fácilmente podemos encontrar un número para cada uno. Si el resto de
la línea o recuadro está completo, con un simple proceso de eliminación sabremos
cual es el valor que falta.
En este caso, el único número que falta de la fila horizontal es el 3.
El número que falta en la columna es el 9.
En del recuadro es un 4.
Técnicas Fáciles
La mayor parte de Sudokus de los que podemos encontrar en los periódicos se pueden
resolver con dos sencillas técnicas:
Marcar las Casillas
Muchos de los jugadores de Sudoku en papel tienden a utilizar sus propios sistemas
para ayudarse a completar los Sudokus. Muy pocos son los que completan la cuadrícula
escribiendo directamente los números finales.
La forma más común de marcar las casillas es escribir pequeños números (que normalmente
se llaman "marcas de lápiz") que en realidad significan "este número sigue siendo
posible para esta casilla". Podemos llegar a la conclusión que una celda sólo puede
contener el "5 y el 8" pero no cual de los dos. Si escribimos un pequeño 58 en la
celda, seguramente después encontraremos otro lugar que nos permita eliminar una
de las marcas (5 u 8). De esta forma, si elimináramos el 5, sabríamos que esta celda
sólo podría contener el 8, de forma que podremos borrar ambas marcas y escribir
un 8 más grande.
No es necesario rellenar todas las marcas (los buenos jugadores piensan que esto
les ralentiza en los puzzles más fáciles, pero lo necesitan hacer en los puzzles
más difíciles).
Muchas de las siguientes técnicas no proporcionan una posición directa, pero nos
pueden ayudar permitiendonos eliminar alguna de las marcas.
La utilización de las marcas hace muy sencillo encontrar los Candidatos Únicos (ver
el 3 del bloque de 3x3 de arriba a la derecha).
En playSudoku.biz tenemos una herramienta dedicada especialmente a esto, llamada"marcadores"
que es muy similar a las marcas de lápiz, con la ventaja de no tener que utilizar
la goma de borrar.
Técnicas Medias
Yendo un poco más lejos, hay algunas técnicas extra que nos pueden ayudar a encontrar
emplazamientos válidos o a eliminar algunas de las marcas. Obviamente, éstas son
difíciles de utilizar sin las marcas en lápiz.
Técnicas Avanzadas
Siguiendo la progresión, podemos encontrar otras técnicas para ayudarnos en la resolución.
Técnicas de Maestro
Una vez dominadas las anteriores técnicas, podemos ir un poco más lejos y aplicar
técnicas más complicadas.
Todavía Más Difícil
Conociendo ya estas técnicas, ¿seremos capaces de resolver todos los posibles Sudokus?
Bueno, talvez si, tal vez no. La gran mayoría de rompecabezas no requieren las técnicas
más complicadas, pero hay algunos que no se pueden resolver simplemente con lógica,
y que requieren algún tipo de "adivinación" para resolverlos. Algunos argumentan
que la adivinación es una forma de lógica.
Nishio es una forma de adivinacion, en la que vemos una adivinación que causa una
contradicción, significando que podemos eliminarla. Continuando con esto, es posible
resolver Sudokus completos a partir de adivinaciones, pero nos puede costar mucho.
Resolución por ordenador
Para los programadores es relativamente sencillo construir una búsqueda por el método
de backtracking o "vuelta atrás". Ésta asignaría, típicamente, un valor (supongamos
que 1, o el más cercano a 1 disponible) a la primera celda disponible (supongamos
que la superior izquierda) y entonces continuar asignando el siguiente valor disponible
(supongamos que 2) a la siguiente celda disponible. Esto continuaría hasta que se
descubriera una duplicación, en cuyo caso, el siguiente valor alternativo se colocaría
en el primer campo alterado. En el caso de que ningún valor cumpliera la restricción
se retrocedería hasta la casilla anterior y se probarían los siguientes números.
Aunque lejos de la eficiencia computacional, este método encontrará la solución
si se permite el suficiente tiempo de computación. Un programa más eficiente podría
dejar una huella de valores potenciales para las celdas, eliminando valores imposibles
hasta que sólo un valor quedase para una celda determinada. Entonces se rellenaría
esa celda y se usaría esa información para más eliminaciones y así, sucesivamente
hasta el final. Esto emularía más exactamente lo que un resolutor humano haría sin
el método de ensayo y error.
Codificar la búsqueda para imposibilidades basadas en contingencias e incluso múltiples
contingencias (como sería requerido para los Sudoku más difíciles) es bastante
complejo de construir a mano. De cualquier modo, tales complicaciones son innecesarias
si todo lo que el programador desea hacer es encontrar una solución eficientemente.
Una forma más eficiente de construir soluciones involucra herramientas de programación
más avanzadas.
Algunos programas así construidos, que emulan la resolución humana, permiten estimar
la dificultad que tendrá un humano para encontrar la solución.