python - hacer - aprender a programar videojuegos desde cero
Ayuda de diseño de programación: ¿cómo estructurar un programa de resolución de sudoku? (9)
Intento crear un programa de resolución de sudoku en Java (quizás Python). Solo me pregunto cómo debería estructurar esto ...
¿Creo una clase y hago de cada caja un objeto de esa clase (9x9 = 81 objetos)? Si es así, ¿cómo controlo todos los objetos? En otras palabras, ¿cómo hago que todos llamen a un determinado método en la clase?
¿Acabo de crear funciones para calcular y simplemente controlar todos los números allí con algo así como una matriz multi-D?
Y en realidad, incluso si pudiera crear múltiples funciones, ¿cómo controlaría todos los objetos si tuviera que convertir cada cuadro en un objeto?
Gracias.
¿Necesitas hacerlo en Python o Java? Hago mucha programación en Python, pero esto se puede hacer mucho más concisamente con un programa entero usando un lenguaje como AMPL o GLPK, que me parece más elegante (y generalmente más eficiente) para problemas como este.
Aquí está en AMPL, aunque no he verificado cómo funciona esto: http://taha.ineg.uark.edu/Sudoku.txt
Bueno, usaría una clase para el sudoku en sí, con una matriz de 9 x 9 y toda la funcionalidad para agregar números y detectar errores en el patrón.
Otra clase se usará para resolver el rompecabezas.
La forma más sencilla de hacerlo es representar el tablero mediante una matriz 2D de 9x9. Querrá tener referencias a cada fila, columna y cuadro de 3x3 como un objeto separado, por lo que almacenar cada celda en una cadena tiene más sentido (en Java) que usar una primitiva. Con una Cadena puede mantener referencias al mismo objeto en múltiples contenedores.
No lo sobreinforme. Es una matriz de 2-D o tal vez una clase de la Junta que representa una matriz de 2-D en el mejor de los casos. Tenga funciones que calculen una fila / columna determinada y funciones que le permitan acceder a cada cuadrado. Se pueden usar métodos adicionales para validar que cada sub-3x3 y cada fila / columna no violen las restricciones requeridas.
Primero, parece que hay dos tipos de células.
Llamadas conocidas; aquellos con un valor fijo, sin opciones.
Células desconocidas; aquellos con un conjunto de valores candidatos que reduce a un único valor final.
En segundo lugar, hay varios grupos de células.
Filas horizontales y columnas verticales que deben tener una celda de cada valor. Esa restricción se usa para eliminar valores de varias celdas en la fila o columna.
3x3 bloques que deben tener una celda de cada valor. Esa restricción se usa para eliminar valores de varias celdas en el bloque.
Finalmente, está la grilla general. Esto tiene varias vistas complementarias.
Son 81 celdas.
Las celdas también se recogen en una cuadrícula de 3x3 de bloques de 3x3.
Las celdas también se recogen en 9 columnas.
Las celdas también se recogen en 9 filas.
Y tienes un objeto de estrategia de solución.
Cada celda Desconocida configuró para
set( range(1,10) )como los valores candidatos.Para cada fila, columna y bloque 3x3 (27 colecciones diferentes):
a. Para cada celda:
- Si tiene un valor definido (las células conocidas y las desconocidas lo implementan de manera diferente): elimine ese valor de todas las demás celdas de esta agrupación.
Lo anterior debe repetirse hasta que no se encuentren cambios.
En este punto, o lo tiene resuelto (todas las celdas informan un valor definido), o bien, tiene algunas celdas con valores múltiples. Ahora tiene que recurrir a un sofisticado solucionador de seguimiento para encontrar una combinación de los valores restantes que "funciona".
Si estás atascado y estás interesado en un tutorial de una solución, Peter Norvig escribió un artículo sobre un solucionador de Sudoku implementado en Python.
Tal vez un diseño que tenía una caja por casilla, y otra clase para representar el rompecabezas en sí que tendría una colección de cajas, contiene todas las reglas para las interacciones de caja, y el control del juego en general sería un buen diseño.
Una clase que contiene una matriz de 1d de 81 ints (0 está vacía) es suficiente para la clase de regla. La clase de regla impone las reglas (no hay números duplicados en cada fila, columna o cuadrado de 3x3). También tiene una matriz de 81 bools para que sepa qué celdas son fijas y cuáles deben ser resueltas. La interfaz pública para esta clase tiene todos los métodos que necesita para manipular la placa:
int getCell(int x, int y);
bool setCell(int x, int y, int value);
bool clearCell(int x, int y);
int[] getRow(int x);
int[] getCol(int y);
int[] getSubBox(int x, int y);
void resetPuzzle();
void loadPuzzle(InputStream stream);
Luego, su solucionador usa la interfaz pública de esta clase para resolver el acertijo. La estructura de clases del solucionador supongo que es el propósito de escribir el solucionador de Sudoku número 5 millones. Si buscas consejos, editaré esta publicación más tarde.
solo por diversión, aquí está lo que se supone que es el programa más corto, en python, que puede resolver una cuadrícula de sudoku:
def r(a):i=a.find(''0'') if i<0:print a [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]r(raw_input())
Hmm ok, es bastante críptico y no creo que coincida con tu pregunta, así que me disculpo por este ruido :)
De todos modos, encontrarás aquí una explicación de estos 173 personajes. También hay una explicación en francés aquí