• Inicio
• Acerca de nativos2020
• Contacto
• Descargas

Como resolver sudokus computacionalmente

Escrito por Jose Carlos el 26 de Enero de 2008

Desde que los sudokus se pusieron de moda, se ha convertido en algo habitual que los profesores de programación propongan a sus alumnos que programen un algoritmo que los resuelva.

Realmente existen muchas formas de abordar el problema, la primera que se viene a la mente es que el programa vaya probando todos los sudokus posibles hasta que encaje, pero esto es poco eficiente, otro método sería utilizar backtracking, pero esto tampoco es tan eficiente, y es que hay una manera de calcular la solución del sudoku sin tener que ir probando.

Lo primero en lo que hay que pensar es en como funciona un sudoku, el juego es sencillo, hay 9 cuadros en 3 filas de a 3, que a su vez tienen dentro cada uno, otros 9 cuadros mas pequeños en 3 filas de a 3.

Al empezar el juego, algunas de las 81 celdas están rellenadas con un número y el juego consiste en rellenar el resto de celdas vacías con el número correspondiente, teniendo en cuenta las siguientes normas:

• No puede haber repetido ningún número en ninguna fila ni columna
• No puede repetirse ningún número en ningún cuadro (los cuadros son los grupos de 9 celdas)

Además, según las normas del sudoku, se considera un sudoku válido a aquellos sudokus que solo tienen una solución, es decir, que con los números dados inicialmente, solo hay una forma de rellenarlo que cumpla las 2 normas anteriores.

Tomando como base esta última propiedad de sudoku válido con una única solución, existe una forma rápida y fácil de determinar que número va en que celda. Lo primero que necesitamos es saber identificar los posibles números de una celda, entendemos por posible número aquel que pueda ir en una celda vacía, ya que no está presenta en su misma fila, columna o caja, por ejemplo, en la figura de arriba en la primera celda de todas, los números posibles son: 3, 5, 7 y 9.

Una vez sabido esto, podemos extender un poco mas nuestro análisis del sudoku, diciendo que en todas las columnas, filas y cajas, estarán presentes todos los números, ya que hay 9 celdas por columna, y hay 9 números, la única forma de rellenarlo sin que se duplique ninguno, es usarlos todos.

Llegados a este punto, podríamos decir que si analizamos cada celda del tablero sacando sus valores posibles, habrá como mínimo una celda que sea la única de su fila, columna o caja que pueda contener un valor X, por ejemplo, la única que pueda contener un 6, lo que significa que ahi tiene que ir un 6, para rellenar con todos los números.

Cuando introducimos ese número único, todo el tablero se ve afectado, esto significa que tras introducirlo, volvemos a leer todos los valores posibles de cada celda, ahora habrá de nuevo una o mas celdas, que sean las únicas que puedan contener ese valor, y así sucesivamente hasta rellenar todo el sudoku.

Pero, ¿por que pasa esto? esto pasa por que si no fuese así, y no hubiese ninguna celda que fuese la única en su fila, columna o caja que pudiese contener un valor X, el sudoku tendría mas de una solución, y sería un sudoku invalido.

Hacer un programa que aplique esta teoría es fácil, pero además, esta forma de resolver sudokus nos abre las puertas a un nuevo descubrimiento, y es que mucha gente se pregunta ¿por que un sudoku es mas difícil que otro? y no, no depende de la cantidad de números iniciales en el tablero, sino que depende de la cantidad de celdas que cumplen lo anteriormente explicado, es decir, si sacamos todos los posibles valores del tablero, y hay gran cantidad de celdas que son las únicas que pueden contener el valor X en su fila, columna o caja, entonces ese sudoku es fácil, pero si por el contrario, hay solo una celda que lo cumple, y al rellenarla, se desvela otra única celda, ese sudoku es muy complejo.

El tema de los sudokus se extiende mucho mas, y realmente el método explicado no sirve para todos los sudokus, y esto es debido a como funciona el sudoku internamente, pero espero que el artículo haya servido para aclarar un poco como funciona el juego y como intentar resolverlo en un problema de programación.

Publicado en: Matemáticas, Programación
Tags: algoritmo, Matemáticas, Programación, sudoku
Reacciones de otros blogs sobre esta entrada