Ayuda para programar un sudoku...

Pues así a lo bruto se puede hacer mediante backtracking. No se si existirá algún algoritmo para disminuir el tiempo, pero para empezar es una solución sencilla.

Salu2!

No me refiero al tiempo, sino que, si yo muestro, por poner un ejemplo (partiendo de que sea un sudoku de 9x9), muestro 15 numeros de los 81 que tiene, ¿cómo me aseguro que con esos 15 numeros es posible resolver el sudoku?

Si yo me refiero a eso, con lo del tiempo me refiero al 'rendimiento' del algoritmo. Con backtracking (prueba y error) es la forma más sencilla de hacerlo

Salu2!

Perdón por mi ignorancia, pero no comprendo la forma que me dices

La forma más sencilla es que hagas primero la solución y luego, que elimines X casillas al azar.

EDITO: Y, por supuesto, no te olvides de eliminar el sudoku "obvio":

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

yanosoyyo escribió:La forma más sencilla es que hagas primero la solución y luego, que elimines X casillas al azar.

EDITO: Y, por supuesto, no te olvides de eliminar el sudoku "obvio":

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sip, la idea era resolverlo antes, pero al eleminiar las X casillas, quizás no queden datos suficientes como para resolverlo... he ahi mi duda xD

Siempre puedes comprobar que en cada fila y columna tenga que haber un mínimo de X números visibles.

Hola:

El problema de hacerlo por fuerza bruta es que habrá veces que el Sudoku que ha empezado a generar no tenga solución y se quede pillado. Yo ahora mismo estoy haciendo un Sudoku también en java, así que igual te puedo dar algunas pistas que te pueden resultar útiles.

En mi caso he optado por generar todo el Sudoku para luego descartar números. Para ello he preferido ir rellenando los números de la tabla seguidos con posiciones aleatorias, es decir, empezamos con el 1 en el primer 3x3 en una de las nueve posiciones posibles y seguimos con el siguiente. Así con los demás 3x3 hasta que lleguemos al último. Luego pasamos al siguiente número y hacemos lo mismo. Por supuesto este método ha de tener en cuenta las reglas del sudoku a la hora de revisar los números que hay en el panel, aunque de momento podemos ignorar la comprobación de 3x3, pues el número que estamos introduciendo en la tabla de 3x3 no va a estar nunca repetido. También es útil que el método tenga alguna forma de saber qué posiciones de las 9 posibles ha probado, más que nada para evitar el usar demasiados ciclos de procesador (y más en mi caso, que el Sudoku que estoy desarrollando es para móviles).

Como digo según se va generando la tabla es posible que llegue un punto en el que no pueda seguir poniendo más números, pues el Sudoku que está generando a partir de X momento puede no tener solución. Para ello en el mío cree una matriz de 4 X 81, en la cual se registran los sudokus de manera temporal cuando se han terminado de introducir los 3, 5, 7 y 8, de esa forma podemos volver atrás cuando el Sudoku se quede pillado y no tener que empezar a generarlo de nuevo con todo lo que ello conllevaría (aunque en algún caso no quedará más remedio).

Bueno, y una vez el Sudoku está generado toca seleccionar los números que van a aparecer en pantalla. En mi caso lo que hice fue sumarle 10 a 3 números de cada 3x3, y luego mediante un número aleatorio sumar 10 a otros 2~4 más. Luego cuando los vaya a dibujar en pantalla los números entre el 1 y el 9 los ignoras y sólo dibujas los comprendidos entre el 11 y al 19 (saldrán en naranja), que deberían ser unos 29~31 números en mi caso; creo que son suficientes para poder resolverlo. Luego por ejemplo puedes hacer que los números que meta el usuario sean introducidos como números del 21 al 29 y salgan en pantalla de un color distinto a los otros, de esa forma además puedes hacer que el método que comprueba si el número que quieres introducir es correcto no te deje sobrescribir los números que la máquina puso inicialmente, pudiendo sólo escribir encima de los números comprendidos del 1 al 9 (que serán interpretados como 0) o del 21 al 29.

Te pongo una captura de todo esto que te comento:



Sí, es un Sudoku con los colores de EOL De momento no me he metido demasiado con la parte gráfica

Un saludo y nada, espero que te resulte de ayuda.

Apmomp escribió:El problema de hacerlo por fuerza bruta es que habrá veces que el Sudoku que ha empezado a generar no tenga solución y se quede pillado

No se porqué me da la sensación de que no has entendido lo que he querido decir con 'fuerza bruta'. Backtracking lo que hace es ir probando, y en el momento en el que no se cumplen las reglas vuelve hacia atrás y prueba más posibilidades. De hecho, tras leer las explicaciones da la sensación de que es lo que tú mismo estás haciendo, aunque sea sin darte cuenta.

Salu2

Dagaren escribió:

No se porqué me da la sensación de que no has entendido lo que he querido decir con 'fuerza bruta'. Backtracking lo que hace es ir probando, y en el momento en el que no se cumplen las reglas vuelve hacia atrás y prueba más posibilidades. De hecho, tras leer las explicaciones da la sensación de que es lo que tú mismo estás haciendo, aunque sea sin darte cuenta.

Salu2

Argg, cierto, me quedé sólo con la primera parte de tu post

Yo programe un sudoku para la uni, se hizo a partir de un sudoku real (del que encuentras en los diarios) mediante la permuta de filas columnas y no se que mas, te generaba mas de diferentes.

Creo que en realidad se hace asi en los juegos cutres y tal, ya que requiere poco calculo y siempre lo puedes ampliar con mas sudokus (si no, las expansiones que te vienen, para que cojones sirven si con el base ya tienes todos los posibles?)

Buff, parece mas complejo de lo que parecia xDDD

De momento, (esta en fase de inicio xD), tengo una matriz de 9x9, la inicializo todo a 0, cree metodos para comprobar si un numero esta en una fila, en una columna, y en un subcuadrado. Crearé otro que lo rellene, y una vez esten resueltos, mostrar X numeros (lo haré con Swing). A ver cómo sale la cosa...

Ten en cuenta que un sudoku solo es válido si tiene una y solo una única solución. Así que tendrás que ir con cuidado si usas técnicas como ir quitando números o dejar visibles n números.

Hace un tiempo vi un algoritmo de dominio público escrito en C que generaba sudokus, si buscas no creo que te cueste mucho encontrarlo.


Por otra parte, si te gusta la algorítmica, un algoritmo muy interesante para resolver sudokus es el dancing links de Donald Knuth. Este tío es un freak de cojones, veamos el porqué de dancing links:

Donald Knuth escribió:This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance; hence I like to call (1) and (2) the technique of dancing links.

¡Qué grande!


Edito: Se me olvidaba, el paper donde lo presentó lo puedes obtener de la página de D. Knuth, es el 159.


Saludos

Lo mejor que podrias hacer es un algoritmo que genere un sudoku valido mediante backtracking, y una vez lo tengas, como te han comentado, vas eliminando casillas. Lo que yo haria es, cada vez que eliminas una casilla, lanzar el algoritmo a ver cuantas soluciones te encuentra, y cuando tras quitar una casilla te encuentre más de una solucion, restauras la ultima casilla eliminada y tendrás los números justos para que la solución sea única.

Vamos, seguramente no es la mejor forma, pero creo que podria funcionar bien.

En cuanto al algoritmo de Knuth, NeoRave se refiere al "AlgoritmoX", los dancing links es la tecnica que se utiliza en dicho algoritmo para eliminar y restaurar de forma eficiente filas y columnas de una matriz. Si implementases la resolucion del Sudoku con el AlgoritmoX seria muy eficiente, pero es bastante mas complicado que con Backtracking, que para una solucion va volao.

Espero haberte ayudado. Saludos

Yo hace poco hice un sudoku en haskell en el cual entre otras cosas se podía elegir el nivel de dificultad y puse un botón que te decía si ibas bien a la hora de resolverlo o no.

La idea principal a la hora de generar los tableros fue la de rellenar un tablero mediante backtracking, y una vez que este estuviese entero generar tuplas de números aleatorios de 0 a 9 e ir borrando las casillas correspondiemtes. Dependiendo del nivel de dificultad borraba más o menos casillas.

Ahora no puedo extenderme con el post porque me tengo que ir, pero luego te podría describir con más detalle el algoritmo, aunque lo que te ha dicho la gente está bien.

Salu2

Pacoloko escribió:En cuanto al algoritmo de Knuth, NeoRave se refiere al "AlgoritmoX", los dancing links es la tecnica que se utiliza en dicho algoritmo para eliminar y restaurar de forma eficiente filas y columnas de una matriz. Si implementases la resolucion del Sudoku con el AlgoritmoX seria muy eficiente, pero es bastante mas complicado que con Backtracking, que para una solucion va volao.

Cierto, se me fue la olla, gracias por la corrección Respecto a la dificultad, ahí está la gracia, conocerlo, entenderlo e implementarlo. También depende del tiempo y ganas que tengas, claro.

Saludos