• Publicidad

Algoritmo para SudoKus

¿Estás desarrollando un proyecto, o piensas hacerlo? Pon aquí tu propuesta, lo más seguro es que alguien esté interesado en ayudarte.

Algoritmo para SudoKus

Notapor explorer » 2010-01-09 11:47 @532

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...
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Publicidad

Re: Algoritmo para SudoKus

Notapor 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 ;)
Uriel Lizama Perl programmer fundador de Perl en Español
Perl Programming Language
Avatar de Usuario
kidd
Creador de Perl en Español
Creador de Perl en Español
 
Mensajes: 1166
Registrado: 2003-10-15 16:52 @744
Ubicación: México

Re: Algoritmo para SudoKus

Notapor 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 :wink:
Expect the worst, is it the least you can do?
Avatar de Usuario
creating021
Perlero frecuente
Perlero frecuente
 
Mensajes: 595
Registrado: 2006-02-23 16:17 @720
Ubicación: Frente al monitor

Re: Algoritmo para SudoKus

Notapor 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.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Algoritmo para SudoKus

Notapor creating021 » 2010-01-09 21:05 @920

Ese era el punto :lol: (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?
Avatar de Usuario
creating021
Perlero frecuente
Perlero frecuente
 
Mensajes: 595
Registrado: 2006-02-23 16:17 @720
Ubicación: Frente al monitor

Re: Algoritmo para SudoKus

Notapor 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.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Algoritmo para SudoKus

Notapor 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
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14480
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Algoritmo para SudoKus

Notapor 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... ;)
Uriel Lizama Perl programmer fundador de Perl en Español
Perl Programming Language
Avatar de Usuario
kidd
Creador de Perl en Español
Creador de Perl en Español
 
Mensajes: 1166
Registrado: 2003-10-15 16:52 @744
Ubicación: México


Volver a Proyectos

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 8 invitados

cron