Inicio / Desafíos PPT / Sudoku / Instrucciones
Desafío Sudoku
Instrucciones
Como todo el mundo sabe, Sudoku es una palabra que viene del japonés, cuya traducción aproximada es "Colocar Números". Un Sudoku se suele considerar un rompecabezas matemático, aunque lo único que tiene de matemático son los números, no es necesario tener ningún conocimiento matemático para resolver este tipo de rompecabezas.
Aunque no está muy claro cuando surgieron los Sudokus, se suele considerar que se originó sobre los años 70. El equipo de historiadores de PHP-Hispano no podia creer estos datos, así que decidió realizar un profunda investigación en busca de indicios de Sudokus en la antigüedad. Tras varios días sin conseguir nada en firme, el equipo se consiguió hacer con esta impresionante imagen de los años 40:
Hay Sudokus muy variados y pintorescos pero para este desafio nos centraremos en los Sudokus regulares. ¿Y que es un Sudoku regular? la respuesta es muy fácil, se trata de los Sudokus cuyas dimensiones son las de algún número entero al cuadrado y que tienen una única solución. El Sudoku más conocido y difundido es el Sudoku 9x9, en el cual partimos de una cuadrícula 9x9 dividida en 9 regiones de 3x3, en cada casilla puede ir un único número del 1 al 9 y se trata de rellenar esta cuadrícula de manera que no se repita ningún número en ninguna fila, columna o región.
Para los que os quedasteis como estabais os ilustraremos el problema. En la siguiente imagen podemos ver un Sudoku 9x9 con números en verde y números en rojo. Los números en rojo estan mal colocados: el 4 porque ya hay un 4 en la misma fila, el 7 porque hay otro 7 en la misma columna y el 1 porque la región de 3x3 ya contiene otro 1. Los números en verde están bien colocados dado que en la región en la que están sólo pueden ir colocados en esa posición.
Al día siguiente de que el equipo de historiadores de PHP-Hispano recibiera la foto de Einstein intentando resolver el Sudoku, una nueva imagen aún más espectacular, o escalofriante según se mire, apareció en la bandeja de correo envíada por una persona que no quiere desvelar su identidad. Tras realizar varias pruebas para confirmar su autenticidad, las imágenes han sido archivadas y catalogadas.
Lo que se pide para el desafío es desarrollar un programa que resuelva todo tipo de Sudokus regulares (4x4, 9x9, 16x16, 25x25...) para poder enviárselo con nuestra máquina del tiempo a Einstein, ya que mientras intentaba resolver el Sudoku, el pobre estuvo 3 días subsistiendo a base de comerse las uñas
No es necesario realizar una interfaz (para Aeoris interficie) web para el programa, se puede hacer ejecutando desde consola. Tampoco será necesario analizar el Sudoku introducido para comprobar que éste sea un Sudoku válido.
Sin embargo, si es necesario que el sudoku sea cargado en memoria a partir de un archivo de texto cuya estructura sea igual a los sudokus que teneis de ejemplo al final de este texto.
Nota: Será necesario mostrar el tiempo total que toma el programa en resolver el Sudoku que se le introduce.
Lo que se valorará para los premios:
- Técnica utilizada para resolver el problema: Backtracking, Devorador, Programación Dinámica...
- Complejidad temporal y espacial del algoritmo (que sea rápido y que no consuma mucha memoria)
Sudokus 9x9 son faciles de conseguir, teneis varios miles de millones en www.websudoku.com, os dejamos a continuación un Sudoku 4x4 y otro 16x16 de ejemplo para que podáis realizar vuestras pruebas con ellos.
Sudoku 4x4
Sudoku 16x16
Suerte a todos los participantes.
Desafío ideado y redactado por Arias
Imágenes de archivo cedidas por Zubyc xD
Foro asociado al desafío
Aunque no está muy claro cuando surgieron los Sudokus, se suele considerar que se originó sobre los años 70. El equipo de historiadores de PHP-Hispano no podia creer estos datos, así que decidió realizar un profunda investigación en busca de indicios de Sudokus en la antigüedad. Tras varios días sin conseguir nada en firme, el equipo se consiguió hacer con esta impresionante imagen de los años 40:
Hay Sudokus muy variados y pintorescos pero para este desafio nos centraremos en los Sudokus regulares. ¿Y que es un Sudoku regular? la respuesta es muy fácil, se trata de los Sudokus cuyas dimensiones son las de algún número entero al cuadrado y que tienen una única solución. El Sudoku más conocido y difundido es el Sudoku 9x9, en el cual partimos de una cuadrícula 9x9 dividida en 9 regiones de 3x3, en cada casilla puede ir un único número del 1 al 9 y se trata de rellenar esta cuadrícula de manera que no se repita ningún número en ninguna fila, columna o región.
Para los que os quedasteis como estabais os ilustraremos el problema. En la siguiente imagen podemos ver un Sudoku 9x9 con números en verde y números en rojo. Los números en rojo estan mal colocados: el 4 porque ya hay un 4 en la misma fila, el 7 porque hay otro 7 en la misma columna y el 1 porque la región de 3x3 ya contiene otro 1. Los números en verde están bien colocados dado que en la región en la que están sólo pueden ir colocados en esa posición.
Al día siguiente de que el equipo de historiadores de PHP-Hispano recibiera la foto de Einstein intentando resolver el Sudoku, una nueva imagen aún más espectacular, o escalofriante según se mire, apareció en la bandeja de correo envíada por una persona que no quiere desvelar su identidad. Tras realizar varias pruebas para confirmar su autenticidad, las imágenes han sido archivadas y catalogadas.
Lo que se pide para el desafío es desarrollar un programa que resuelva todo tipo de Sudokus regulares (4x4, 9x9, 16x16, 25x25...) para poder enviárselo con nuestra máquina del tiempo a Einstein, ya que mientras intentaba resolver el Sudoku, el pobre estuvo 3 días subsistiendo a base de comerse las uñas
No es necesario realizar una interfaz (para Aeoris interficie) web para el programa, se puede hacer ejecutando desde consola. Tampoco será necesario analizar el Sudoku introducido para comprobar que éste sea un Sudoku válido.
Sin embargo, si es necesario que el sudoku sea cargado en memoria a partir de un archivo de texto cuya estructura sea igual a los sudokus que teneis de ejemplo al final de este texto.
Nota: Será necesario mostrar el tiempo total que toma el programa en resolver el Sudoku que se le introduce.
Lo que se valorará para los premios:
- Técnica utilizada para resolver el problema: Backtracking, Devorador, Programación Dinámica...
- Complejidad temporal y espacial del algoritmo (que sea rápido y que no consuma mucha memoria)
Sudokus 9x9 son faciles de conseguir, teneis varios miles de millones en www.websudoku.com, os dejamos a continuación un Sudoku 4x4 y otro 16x16 de ejemplo para que podáis realizar vuestras pruebas con ellos.
Sudoku 4x4
Sudoku 16x16
Suerte a todos los participantes.
Desafío ideado y redactado por Arias
Imágenes de archivo cedidas por Zubyc xD
Foro asociado al desafío