Buenas... necesito ayuda.
Necesito encontrar un algoritmo o fuente de programación que genere Sudokus de tamaño 16x16, con la máxima dificultad o menor número de pistas, y, -lo más complicado-, que se garantice que la solución sea única.
Es un asunto bastante complicado, y no he encontrado soluciones...
-
- Publicidad
Algoritmo para SudoKus
8 mensajes
• Página 1 de 1
Algoritmo para SudoKus
por explorer » 2010-01-09 11:47 @532
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
-
explorer - Administrador
- Mensajes: 14480
- Registrado: 2005-07-24 18:12 @800
- Ubicación: Valladolid, España
Publicidad
Re: Algoritmo para SudoKus
por kidd » 2010-01-09 15:07 @671
Hola Joaquín,
Interesante tema. ¿Le has echado un vistazo al proyecto de GNOME Sudoku?
http://sourceforge.net/projects/gnome-sudoku/
Por ahí alguien hizo un script que lo usa pero hace el output a PDF:
http://www.opensky.ca/~jdhildeb/software/sudokugen/
Acabo de encontrar otro:
http://sourceforge.net/projects/sudoku-perl/
No sé por donde has andado así que te voy poniendo lo que voy encontrando
Interesante tema. ¿Le has echado un vistazo al proyecto de GNOME Sudoku?
http://sourceforge.net/projects/gnome-sudoku/
Por ahí alguien hizo un script que lo usa pero hace el output a PDF:
http://www.opensky.ca/~jdhildeb/software/sudokugen/
Acabo de encontrar otro:
http://sourceforge.net/projects/sudoku-perl/
No sé por donde has andado así que te voy poniendo lo que voy encontrando
-
kidd - Creador de Perl en Español
- Mensajes: 1166
- Registrado: 2003-10-15 16:52 @744
- Ubicación: México
Re: Algoritmo para SudoKus
por creating021 » 2010-01-09 17:36 @775
Supongo que necesitas dos algoritmos, el primero para resolverlo y el segundo sólo tienes que colocar números aleatoriamente
Expect the worst, is it the least you can do?
-
creating021 - Perlero frecuente
- Mensajes: 595
- Registrado: 2006-02-23 16:17 @720
- Ubicación: Frente al monitor
Re: Algoritmo para SudoKus
por explorer » 2010-01-09 18:27 @810
No, creating021, necesito generarlos.
De hecho, he visto que la generación de Sudokus, en su estado más complicado, requiere de la resolución a cada paso de la generación, para comprobar que la solución es única. Por ello, hacer un Sudoku de nivel muy alto, puede llevar mucho tiempo de cálculo. Y más si es de 16x16.
Para mi, lo primordial es saber que se genera una solución única.
De hecho, he visto que la generación de Sudokus, en su estado más complicado, requiere de la resolución a cada paso de la generación, para comprobar que la solución es única. Por ello, hacer un Sudoku de nivel muy alto, puede llevar mucho tiempo de cálculo. Y más si es de 16x16.
Para mi, lo primordial es saber que se genera una solución única.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
-
explorer - Administrador
- Mensajes: 14480
- Registrado: 2005-07-24 18:12 @800
- Ubicación: Valladolid, España
Re: Algoritmo para SudoKus
por creating021 » 2010-01-09 21:05 @920
Ese era el punto 
(tengo que trabajar en mis respuestas).
Puede que no sea la mejor solución pero lo que puedes hacer es generar miles de sudokus que tengan las características de ser difícil (esto definido por reglas básicas, como el número de números usados en una fila), lo guardas en una base de datos y compruebas con uno de esos algoritmos de Wikipedia. Si el sudoku tiene más de una respuesta... lo borras.
Hmmm... aunque en el último enlace que Uriel pone dice:
¡Y está hecho en Perl!
(tengo que trabajar en mis respuestas).Puede que no sea la mejor solución pero lo que puedes hacer es generar miles de sudokus que tengan las características de ser difícil (esto definido por reglas básicas, como el número de números usados en una fila), lo guardas en una base de datos y compruebas con uno de esos algoritmos de Wikipedia. Si el sudoku tiene más de una respuesta... lo borras.
Hmmm... aunque en el último enlace que Uriel pone dice:
Sudoku player that offers a board, assistance and finding more than 1 solution using a (text based) ANSI screen.Added is also a sudoku generator, producing the single solution sudoku type
¡Y está hecho en Perl!
Expect the worst, is it the least you can do?
-
creating021 - Perlero frecuente
- Mensajes: 595
- Registrado: 2006-02-23 16:17 @720
- Ubicación: Frente al monitor
Re: Algoritmo para SudoKus
por explorer » 2010-01-09 21:18 @929
Sí, ya he visto los enlaces de Uriel. El de Perl no me vale porque está ajustado a un tamaño de 9x9.
Si no veo nada en tamaños de 16x16, entonces buscaré en tamaños de 4x4.
He encontrado algo interesante: http://www.a-kat.com/Sudoku.xhtml
Mirando su código veo que sí, que utiliza la técnica de jugar cada posición, para comprobar que la solución es única.
Si no veo nada en tamaños de 16x16, entonces buscaré en tamaños de 4x4.
He encontrado algo interesante: http://www.a-kat.com/Sudoku.xhtml
Mirando su código veo que sí, que utiliza la técnica de jugar cada posición, para comprobar que la solución es única.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
-
explorer - Administrador
- Mensajes: 14480
- Registrado: 2005-07-24 18:12 @800
- Ubicación: Valladolid, España
Re: Algoritmo para SudoKus
por explorer » 2010-01-11 13:54 @621
Los dos módulos Perl que he encontrado que son capaces de generar Sudokus de varios tamaños son: Games::Sudoku::Component y Games::Sudoku::General. Veremos a ver...
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
-
explorer - Administrador
- Mensajes: 14480
- Registrado: 2005-07-24 18:12 @800
- Ubicación: Valladolid, España
Re: Algoritmo para SudoKus
por kidd » 2010-01-11 18:04 @794
Interesantes los módulos, por la documentación me parece que el segundo podría estar más cercano, pero sería cuestión de probar.
A ver que tal salen tus pruebas...
A ver que tal salen tus pruebas...
-
kidd - Creador de Perl en Español
- Mensajes: 1166
- Registrado: 2003-10-15 16:52 @744
- Ubicación: México
8 mensajes
• Página 1 de 1
¿Quién está conectado?
Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 2 invitados