Construyendo un Sudoku Solver EFICIENTE

Question

Sí, sé que esto no es nada nuevo y que hay muchas preguntas por ahí (incluso tiene su propia etiqueta), pero me gustaría crear un Sudoku Solver en Java con el único propósito de entrenándome para escribir código que sea más eficiente.

Probablemente la manera más fácil de hacer esto en un programa es tener una gran cantidad de loops para analizar cada columna y fila, recolectar los valores posibles de cada celda y luego eliminar las celdas con una sola posibilidad (si contienen solo 1 número, o son la única celda en su fila/columna que contiene este número) hasta que tenga un acertijo resuelto. Por supuesto, un solo pensamiento de la acción debería levantar una bandera roja en la mente de todos los programadores.

Lo que estoy buscando es la metodología para solucionar este problema de la forma más eficiente posible (intente no incluir demasiados códigos, quiero entender esa parte yo mismo).

Quiero evitar algoritmos matemáticos si es posible, sería demasiado fácil y el 100% no es mi trabajo.

Si alguien pudiera proporcionar un proceso de pensamiento paso a paso y eficiente para resolver un rompecabezas de Sudoku (ya sea por un humano o por computadora), estaría muy feliz :). Estoy buscando algo impreciso (por lo que es un desafío), pero lo suficientemente informativo (para no perderme del todo) para ayudarme a comenzar.

Muchas gracias,

Justian Meyer

EDIT:

En cuanto a mi código, me puse a pensar: ¿cuál sería algunas de las posibilidades para el almacenamiento de estos estados de resolución (es decir, el Cuadrícula de Sudoku). Arrays 2D y matrices 3D vienen a la mente. ¿Cuál podría ser el mejor? 2D podría ser más fácil de manejar desde la superficie, pero las Matrices 3D también proporcionarían el número de "caja"/"jaula".

EDIT:

importa. Voy a ir con una matriz 3D.

Answer 1

Depende de cómo se defina eficiente.

Puede utilizar un método de fuerza bruta, que busca en cada columna y fila, recopila los valores posibles de cada celda y elimina las celdas con una sola posibilidad.

Si tiene celdas restantes con más de una posibilidad, guarde el estado del rompecabezas, elija la celda con la menor cantidad de posibilidades, elija una de las posibilidades e intente resolver el rompecabezas. Si la posibilidad que eligió conduce a una contradicción de rompecabezas, restaure el estado guardado del rompecabezas, regrese a la celda y elija una posibilidad diferente. Si ninguna de las posibilidades en la celda que eligió resuelve el acertijo, elija la siguiente celda con las menores posibilidades. Haz un ciclo por las restantes posibilidades y celdas hasta que hayas resuelto el rompecabezas.

Intentar resolver el rompecabezas significa buscar a través de cada columna y fila, recogiendo los valores posibles de cada celda, y eliminando las celdas con una sola posibilidad. Cuando todas las células se eliminan, has resuelto el rompecabezas.

Puede utilizar un método lógico/matemático, donde su código intenta diferentes estrategias hasta que se resuelve el rompecabezas. Busque en Google "estrategias de sudoku" para ver las diferentes estrategias. Usando métodos lógicos/matemáticos, tu código puede "explicar" cómo se resolvió el rompecabezas.

Answer 2

Cuando hice la mía, pensé que podría resolver cada tablero usando un conjunto de reglas sin hacer ningún retroceso. Esto resultó imposible, ya que incluso los acertijos dirigidos a jugadores humanos potencialmente requieren hacer algunas hipótesis.

Así que comencé implementando las "reglas" básicas para resolver un rompecabezas, tratando de encontrar la siguiente regla para implementar que permitiera la resolución de dónde se detuvo la última vez. Al final, me vi obligado a agregar un algoritmo recursivo de fuerza bruta, pero la mayoría de los acertijos se resuelven sin usar eso.

Escribí una publicación de blog sobre mi sudoku solver. Solo lea la sección "El algoritmo" y obtendrá una idea bastante buena de cómo lo hice.

http://www.byteauthor.com/2010/08/sudoku-solver/

Answer 3

Si alguien necesita una aplicación Android de referencia, escribí una solución que utiliza el algoritmo del poste anterior.

completa de código de fuente abierta aquí: https://github.com/bizz84/SudokuSolver

Además, esta solución se carga Sudoku Puzzles en formato JSON desde un servidor web y una copia de los mensajes de los resultados.

Answer 4

Debería pensar en reducir el problema de Sudoku a SATisfiability problem.

Este método le evitará pensar demasiado mathematically pero más logically sobre la IA.

El objetivo paso a paso es básicamente:

* Find all the constraints that a Sudoku has. (line, column, box). 
* Write these constraints as boolean constraints. 
* Put all these constraints in a Boolean Satisfiability Problem. 
* Run a SAT solver (or write your own ;)) on this problem. 
* Transform the SAT solution into the solution of the initial Sudoku. 

Se ha realizado por Ivor Spence utilizando SAT4J y se puede encontrar el applet de Java de su trabajo aquí: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

También puede descargar directamente el código Java del sitio web SAT4J, para ver cómo se ve: http://sat4j.org/products.php#sudoku.

Y, por último, la gran ventaja de este método es: Puede resolver N*N Sudokus, y no sólo la típica 9*9, que es en mi opinión, mucho más difícil para una IA :).