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.Construyendo un Sudoku Solver 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.
Además, si elige "eliminar hasta que solo le quede una posibilidad", aún no podrá resolver algunos sudokus. Hay una gran cantidad de sudokus "más difíciles" en los que en realidad tiene que realizar algún tipo de búsqueda antes de poder estar seguro de qué número colocar (DFS/BFS). De lo contrario, pasar por cada columna y así sucesivamente no es realmente -que horrible o ineficiente, siempre y cuando configure las estructuras de datos en consecuencia, pero como he dicho, no va a resolver -todo- sudokus. – wasatz
@wasatz: Sí, investigué un poco y encontré eso. Sin embargo, parece que muchas otras personas han encontrado soluciones más eficientes que, aunque odio admitirlo, están muy por encima de mi nivel de comprensión. –
@Justian, busqué en Google rápidamente y encontré algunas recomendaciones para usar el "Algoritmo de enlaces de baile" (http://en.wikipedia.org/wiki/Dancing_Links). No he visto este algoritmo antes (y realmente no tengo tiempo para leerlo en este momento) pero parece prometedor. Tal vez algo que vale la pena echarle un vistazo? :) – wasatz