Desarrollo y diseño

Programar Sudoku en 'C'

xCoNDoR
xCoNDoR #1 Nov '10

Hola mediavida, tengo un problema..

No hago mas que darle vueltas desde hace unos dias, y no consigo sacar buenos resultados.. necesito hacer lo siguiente:

Un programa en 'C', que genere un Sudoku resuelto, osea:

  • Tablero 9x9 con numeros aleatorios
  • Numeros del 1 al 9 sin repetirse en horizontal, vertical ni en celdas de 3x3 (el llamado sudoku, vaya).

Pues bien, no doy a basto.. no se que orden o proceso seguir para no dar con un bucle infinito al generar numeros aleatorios para reyenar el array de 9x9..

Alguna idea?

Gracias

DaRk-eXe
DaRk-eXe #2 Nov '10

nose a si de primeras se me ocurre que uses un Conjunto para controlar que no se repitan los números en los arrays y que cada vez que coloques un número compruebes con fila, columna y cubo pero vamos.. es lo primero que he pensado.. lo mismo luego me pongo a hacerlo y veo alguna forma mejor..

xCoNDoR
xCoNDoR #3 Nov '10

#2 he hecho pruebas así pero es imposible sin volver atrás, me llega a resolver 3 lineas y media porque el numero necesario en el segundo cubo superior ya está usado en esa misma fila por ejemplo.. estoy totalmente en blanco ahora mismo despues de provar mil formas

S
Sarjan #4 Nov '10

20 segundos de Google:

Sudoku Generation Algorithm

How can you generate Sudoku puzzles? I do not know what the 'best' algorithm is, but here is what I have done in my simple little python program.

First, we need a Sudoku solver. My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough.

If only one number fits in a square without row, column, and box conflicts, we fill it in.
If a number needed by a row, column, or box can only go in one square in that row, column, or box, we fill it in.
If we can't fill in anything using rules 1 or 2, then we find a most-constrained place or number where we can guess (for example, two choices is better than three), and we try all the guesses.
The last bit about trying all the guesses will require some backtracking. When we are selecting a place to guess, we choose one randomly among the most-constrained places, and we shuffle the choices to try them in a random order.

The result is if we tell the solver to solve an empty board, we get a nice random fully-solved Sudoku board.

To generate Sudoku puzzles, we start with a solved board, and we choose some minimal hints to reveal as follows.

Going through the squares in shuffled order, reveal each square only if it is not deduced by the other revealed squares (using the solver without guessing). This produces a list of about 30 to 40 hints which together dermine the 81 squares of the board.
Going through the chosen hints in shuffled order, attempt dropping each one, and fully solve the board far enough to find two solutions if there are two. Replace the hint unless the solution is still unique with the hint removed.
Notice that generating a minimal puzzle this way requires us to do the work of solving a Sudoku board about twenty times, so it takes a lot more work to generate a minimal Sudoku puzzle than it does to solve one. If there are ways of generating Sudoku puzzles more quickly, I'd love to know.

MrPaytoN
MrPaytoN #5 Nov '10

Piensa un método alternativo que no sea crear filas sin repeticion.

Se me acaba de ocurrir , no sé si funcionara.

Creas un cubo sin repeticiones y luego a a partir de el vas creando filas .

Lo mejor es que cojas papel y lápiz y le pongas a dar a la imaginación xD

JameZ-
JameZ- #6 Nov '10

que llevas de codigo ahora mismo? podrias ponerlo, y el montaje que le has puesto y demas.. vamos mas informacion que pareces que quieres que te lo pongan y fuera xD

xCoNDoR
xCoNDoR #7 Nov '10

#4 Voy a intentar comprender eso, creo que es lo que busco, no sé porque no he pensado en buscar el algoritmo en google, voy a ver si me sirve.
Edit: Hay cosas que mi inglés no me hace entender correctamente, y el traductor de google no me ayuda, alguien es tan amable ?

#5 También he pensado en eso, pero creo que estoy en las mismas

#6 No pido ningun codigo, da igual lo que lleve, no es esa mi pregunta

eXtreM3
eXtreM3 #8 Nov '10

Vamos a ver, hace mucho que no pienso en c, veamos el pseudocódigo:

  • Creas un primer cubo 3x3
  • Rellenas de manera aleatoria filas y columnas
  • Creas un segundo cubo contiguo a la derecha y miras la [1][1] , [1][2] y [1][3] para no repetir en la primera fila. Lo mismo con 2ª y 3ª fila.
  • Creas el tercer y último cubo horizontal y repites lo del paso anterior.
    Y ahora viene lo jodido... creo, así mentalmente que no todas las combinaciones son posibles, ya que donde podría cuadrar un "7" o un "2" a lo mejor te fuerza error en el último cuadrado 3x3 ...
    Entonces supongo que se podría generar un cubo igual que en el paso anterior, y si no hay soluciones posibles (porque son reales y el pc las saca en 0,) que te regenere el último cubo, y así sucesivamente.

Putas horas, como me rayo solo xD

CODIGO FUENTE COMPLETO DE SUDOKU EN C#
eXtreM3
eXtreM3 #9 Nov '10

FAIL, no cabía todo en un spoiler xD

2ª parte
xCoNDoR
xCoNDoR #10 Nov '10

#8 Te refieres a generar el primer cubo, despues el segundo y espues el tercero osea los 3 de arriba del todo, uno por uno sin infringir las leyes del sudoku ?
De ser así seria posible, es mas, lo e hecho, pero los siguientes pasos podrian (y seguramente sea asi) no tener solucion posible y por lo tanto me quedaria colgado.. es ahí donde me quedo en blanco, tendria que hacer algo como volver a generar los 3 cubos otra vez tantas veces como fuesen necesarias para que alguna vez tubiese suerte y pudiese generar el siguiente cubo, pero al llegar al ultimo sería casi imposible creo..
Creo que tiene que haber alguna otra regla o paso en el proceso que me asegure que no voy a encontrar un error tan frecuente como el que encontraría siguiendo estos pasos..

No se si me he explicado..

El codigo fuente que me has pegado es en C# y aunque lo medio-entiendo, lo tengo que programar en 'C' simple

Gracias!

LOc0
LOc0 #11 Nov '10

No es por tocar los huevecillos pero en #4 tienes el algoritmo (en inglés, eso sí). Si no dominas el idioma, la idea es:

1º Coges un sudoku en blanco y eliges al azar un número (1-9) y una de las 81 casillas.

2º Resuelves ese sudoku (que tiene muchas soluciones y te quedas con la primera solución).

3º Te coges un sudoku en blanco y vas copiando las casillas del que tienes resuelto al azar siempre y cuando la casilla NO pueda ser deducida con el resto de casillas que ya tienes. Al principio ninguna casilla se puede deducir* ya que el sudoku está en blanco, pero cuando lleves unas 25 o por ahí te darás cuenta de que no puedes meter más casillas no deducibles.

En resumen, necesitas tener un sudoku-solver. Cuanto mejor sea (mejor deduciendo, porque adivinando, adivinan todos igual), tendrás un control más preciso de la dificultad que tendrá el sudoku que estás generando.

El esquema que sigue un solver suele ser:

1º) Calcula los candidatos de cada casilla. (En un sudoku en blanco cada casilla tiene TODOS los candidatos).

2º) FASE DE DEDUCCiÓN -> Aplicando reglas lógicas es capaz de asignar los valores correctos de algunas casillas.

3º) Si en el paso 2º dedujo algo, vuelve al paso 1º. Si no, pasa al 4º

4º) Backtracking (ir metiendo en cada casilla uno de sus candidatos hasta que llegas a un imposible que te hace volver hacia atrás y probar un candidato distinto en la última casilla que probaste). En esta fase tb puedes meter deducción para acelerar un poco, pero recordando cual fue la casilla donde "adivinaste" por si tienes que volver hacia atrás.

Salu2 ;)

*deducir = sacar sin utilizar backtracking.

xCoNDoR
xCoNDoR #12 Nov '10

#11 Gracias, se me vienen ideas nuevas a la cabeza, cuando le dedique tiempo posteo, estate atento que tendre preguntas seguro :P

Muchas gracias

eXtreM3
eXtreM3 #13 Nov '10

Es que tienes que partir de la base de que no todas las combinaciones son posibles, es muy difícil hacer el algoritmo correcto. De hecho el código ese que he puesto arriba lo he compilado y a veces se queda pillao buscando soluciones, pone "Buscando candidatos" y te salta un mensajito de que la lógica no llega a tanto, que si quieres buscarlo por la fuerza bruta, y resolver un sudoku por fuerza bruta la verdad es que es un poco locura, descartado.

En realidad las posibilidades son limitadas, y no hay tantas eh... pero bueno yo también me quedaría atrancado estando en tu lugar, hay un momento que te quedas "hola..."

YiTaN
YiTaN #14 Nov '10

Con C la cosa se complica un poco más, pero con programación lógica me parece divertidísimo solucionar este tipo de juegos :P

xCoNDoR
xCoNDoR #15 Nov '10

Mirar, el programa me genera un tablero con huecos aleatorios y numeros sin saltarse las reglas del sudoku, por ejemplo este:

claro que, no significa que tenga solución.. por lo que no sé si me falta implementar alguna logica mas o añadir backtracking apartir de ahí

¿ como lo veis ?

eXtreM3
eXtreM3 #16 Nov '10

Mírate este hilo

http://www.latinocheats.com/generador-de-sudokus-sencillo-y-t6126.html

Está el código en php explicado y documentado, puede ser que te eche una mano en ciertas funciones.

Pero la dinámica que sigue es colocar números aleatorios siguiendo las reglas y pasarle la función para hacerlo

  • Si se resuelve: le quita números y te lo muestra (en tu kaso seria mostrarlo directamente)
  • Si no lo resuelve pq no tiene solución: pinta uno nuevo

Por eso a veces tarda un wevo en recargar la página, porque tiene que hacer uno, y otro, y otro, y otro... hasta que sale uno bueno ;)

http://www.primolius.com.ar/sudoku.php

Shendraf
Shendraf #17 Nov '10

Esto lo tuve de ejercicio en la carrera y tuve que usar backtracking en C, ofc. Echaré un vistazo en el baúl y cuando lo encuentre, lo posteo.

Elektr0_ddr
Elektr0_ddr #18 Nov '10

Ahi tienes un ejemplo de sudoku en JAVA http://www.heimetli.ch/ffh/simplifiedsudoku.html

1
xCoNDoR
xCoNDoR #19 Nov '10

#18 Genial, no sabes cuanto te lo agradezco, me ha servido perfectamente para entenderlo y hacerlo a mi manera

xCoNDoR
xCoNDoR #20 Nov '10

Mirar, sacado del codigo de #18 pasado a C, hay algo que no consigo entender, a ver si podeis explicarmelo alguno.

spoiler

El programa funciona perfectamente, pero cuando la función resolver llega a sudoku[row][col] = 0; , no entiendo porqué debebería seguir el programa y no acabar ahí.

Alguien lo entiende mejor ?

Meleagant
Meleagant #21 Nov '10 :psyduck:

Los algoritmos de vuelta atrás son tus amigos.

xCoNDoR
xCoNDoR #22 Nov '10

#21 Donde está ese algoritmo ? Es lo que no consigo ver

Meleagant
Meleagant #23 Nov '10 :psyduck:

A ver, no tengo ganas de hacerte la tarea, pero básicamente lo que necesitas saber es cómo implementar un algoritmo de vuelta atrás (o backtracking) y es probable que la mejor solución pase por utilizar el patrón estrategia.

Con esos datos y Google, no necesitas más.

xCoNDoR
xCoNDoR #24 Nov '10

#23 El programa funciona perfectamente tal y como está. Resuelve el sudoku en blanco o con algunas casillas asignadas.

Mi pregunta no era esa

LOc0
LOc0 #25 Nov '10

#24

De hecho, hay UN SÓLO CASO en que después de

sudoku[row][col] = 0;

el programa acaba. Ese caso es la PRIMERA LLAMADA que se hace a la función resolver (en la primera casilla vacía del sudoku). En el resto de llamadas no termina el programa, sino que al quedarse sin candidatos en la casilla actual, la marca otra vez como vacía y vuelve a la casilla "adivinada" anterior para probar con otro de sus candidatos. Échale un vistazo -> http://www.algoritmia.net/articles.php?id=33

Salu2 ;)

xCoNDoR
xCoNDoR #26 Nov '10

Gracias LOc0, al final anoche entendi la recursividad de las funciones gracias al depurar, despues de darle muchas vueltas. De todos modos le echare un vistazo a ese enlace cuando tenga un rato

bLaKnI
bLaKnI #27 Nov '10 Inocente

Alguien ha oído hablar alguna vez de los problemas NP?
Y de los SAT solvers?

Olvídate de programar "en un pim-pam" un Sudoku solver, my friend. :)

http://minisat.se/MiniSat.html

xCoNDoR
xCoNDoR #28 Nov '10

Ya lo terminé ;)
Gracias

LOc0
LOc0 #29 Nov '10

#27

Sí, y es un tema muy interesante, aunque creo que se va un poco de lo que pedía #1

Salu2 ;)

Usuarios habituales

Tags