Poco después de publicar este post, encontré algunos errores. El código corregido se encuentra en las respuestas #12 y #13. En las anteriores se puede ver el desarrollo de estos errores. Disculpen las molestias.
Buenas a todos. Estoy muy feliz de hacer este post. Como el título indica, se trata de un generador de sudokus sencillo; sencillo en el sentido de que para entenderlo no hace falta un gran conocimiento ni de matemática, ni de programación. De hecho, algunas cosas podrían estar más "comprimidas", pero decidí dejarlas así para que fuera más prolijo y legible el programa. No es el mejor (de hecho, tiene algunos defectos, que pueden colaborar para solucionarlos
), pero sí genera sudokus (y válidos)
. Este script lo hice únicamente por diversión, como un reto a mí mismo. Lo "libero" en este foro, pueden usarlo como gusten siempre y cuando no sea para fines comerciales y pongan un enlace a este hilo.
Bueno, paso a explicarlo:
La generación del sudoku se realiza en dos partes:
- Se genera el sudoku completo, como quedaría una vez resuelto.
- Al sudoku completo, se le quitan aleatoriamente números, de modo que siempre siga quedando una solución única.
Generación del sudoku completo:
Básicamente, lo que hace el script es completar la matriz del sudoku (9 x 9) que en nuestro caso será un
array de 81 elementos. Para ello, el script itera 81 veces (más adelante se verá por qué se hace con un
while y no con un [B]for[/B), para ir completando los casilleros. Cada casillero vacío puede recibir un valor del 1 al 9, siempre y cuando el mismo no haya sido usado ni para la misma fila, ni para la misma columna, ni para el mismo "cuadrado" (ese cuadrado de 3 x 3 que lo contiene)... básicamente, las reglas del sudoku que todos (o al menos, muchos) conocen. Bien, eso es lo que hace la función
completarMatrizSudoku(): tiene nueve
arrays representan cada una de las columnas, nueve
arrays que representan cada una de las filas y otros nueve que representan cada uno de los "cuadrados". Para saber qué número puede ir en un casillero determinado, se obtienen los números que ya están en la fila, los que ya están en la columna, los que ya están en el cuadrado. Para ello, simplemente se "deduce" en qué fila, en qué columna, y en qué "cuadrado" está el casillero; para eso sólo hace falta un poco de matemática básica (división y resto de la división entera), y un par de
arrays extra que nos resultan útiles (sobre todo para saber en qué "cuadrado" estamos parados
); con esos datos, podemos obtener los
arrays en cuestión sin mayor problema gracias a las
variables variables
. Teniendo esos tres
arrays (los números que ya están en la fila, en la columna y en el "cuadrado"), se obtienen los números posibles para el casillero (a partir de otro
array que contiene los números del 1 al 9, gracias a
array_diff), de estos últimos, se elige uno aleatoriamente, luego se guarda el valor en el
array que representa al sudoku y a los que representan la fila, la columna y el "cuadrado". Puede ocurrir, que por una "mala elección" aleatoria, de los números, en un determinado momento no haya números para completar algún casillero. En ese caso (y acá es donde primero habría que tratar de optimizar el código) lo que se hace es volver a empezar con la generación del sudoku desde cero (por eso se pone un límite de tiempo de ejecución del script); en caso contrario, se aumenta el contador de casilleros (por eso la iteración no se hace con un
for). Obviamente, la mayoría de los intentos de armar el sudoku bien fracasan. Para saber cuál era la probabilidad de éxito, hice ciento siete pruebas. Siete de ellas excedieron el tiempo de ejecución máximo (que en ese momento era de 6 segundos), los resultados del resto arrojaron un promedio de 236,29 intentos hasta el éxito (con una desviación estándar de ¡206,24!). Luego le cambié el tiempo máximo de ejecución a 10 segundos y siempre me generó un sudoku (aunque no quiere decir que no pueda arrojar algún error esporádicamente y dependiendo de la carga del servidor).
Para que sea más sencillo de entender el código, subí estas imágenes que ilustran cómo se hace referencia a cada casillero del sudoku:
Ahora sí, las funciones implicadas:
Código PHP:
// Puede llegar a ocurrir que el script demore demasiado,
// por eso ponemos un tiempo límite de 10 segundos.
set_time_limit(10);
// La función shuffle de PHP no tiene una buena aleatoriedad,
// por eso generé esta otra. El array resultante tiene índice numérico ordenado y consecutivo comenzando en 0.
function shuffle2(&$arr)
{
if(empty($arr))
{
return array();
}
$arr2=array();
while(count($arr2)<count($arr))
{
// Alimento (pongo la semillita :D) la aleatoriedad con un número
// que depende de los microsegundos del epoch
srand(ceil(999999999*microtime()));
$i=rand(0, count($arr)-1);
if(!in_array($i, $arr2))
{
array_push($arr2, $i);
}
}
$arr=array_combine($arr2, $arr);
ksort($arr);
$arr=array_values($arr);
}
function completarMatrizSudoku()
{
$A=array();
$B=array();
$C=array();
$D=array();
$E=array();
$F=array();
$G=array();
$H=array();
$I=array();
$_a=array();
$_b=array();
$_c=array();
$_d=array();
$_e=array();
$_f=array();
$_g=array();
$_h=array();
$_i=array();
$_1=array();
$_2=array();
$_3=array();
$_4=array();
$_5=array();
$_6=array();
$_7=array();
$_8=array();
$_9=array();
$j=0;
$original=array(1, 2, 3, 4, 5, 6, 7, 8, 9);
$letras=array(1=>'a', 2=>'b', 3=>'c', 4=>'d', 5=>'e', 6=>'f', 7=>'g', 8=>'h', 0=>'i');
$cuadrado=array(
1=>'A', 2=>'A', 3=>'A', 4=>'B', 5=>'B', 6=>'B', 7=>'C', 8=>'C', 9=>'C',
10=>'A', 11=>'A', 12=>'A', 13=>'B', 14=>'B', 15=>'B', 16=>'C', 17=>'C', 18=>'C',
19=>'A', 20=>'A', 21=>'A', 22=>'B', 23=>'B', 24=>'B', 25=>'C', 26=>'C', 27=>'C',
28=>'D', 29=>'D', 30=>'D', 31=>'E', 32=>'E', 33=>'E', 34=>'F', 35=>'F', 36=>'F',
37=>'D', 38=>'D', 39=>'D', 40=>'E', 41=>'E', 42=>'E', 43=>'F', 44=>'F', 45=>'F',
46=>'D', 47=>'D', 48=>'D', 49=>'E', 50=>'E', 51=>'E', 52=>'F', 53=>'F', 54=>'F',
55=>'G', 56=>'G', 57=>'G', 58=>'H', 59=>'H', 60=>'H', 61=>'I', 62=>'I', 63=>'I',
64=>'G', 65=>'G', 66=>'G', 67=>'H', 68=>'H', 69=>'H', 70=>'I', 71=>'I', 72=>'I',
73=>'G', 74=>'G', 75=>'G', 76=>'H', 77=>'H', 78=>'H', 79=>'I', 80=>'I', 81=>'I');
$resultado=array();
$i=1;
while($i<=81)
{
$idxLetra=$i%9;
$letra='_'.$letras[$idxLetra];
$idxNro=ceil($i/9);
$nro='_'.$idxNro;
$cuadro=$cuadrado[$i];
// Si no sabes lo que significa $$letra, busca "variables variables PHP" en Google
$copia=array_diff($original, $$letra, $$nro, $$cuadro);
shuffle2($copia);
$valor=array_pop($copia);
array_push($$letra, $valor);
array_push($$nro, $valor);
array_push($$cuadro, $valor);
$resultado[$i]=$valor;
if($valor==NULL)
{
// Si algo va saliendo mal, empezamos todo de nuevo
$i=1;
$j++;
$A=array();
$B=array();
$C=array();
$D=array();
$E=array();
$F=array();
$G=array();
$H=array();
$I=array();
$_a=array();
$_b=array();
$_c=array();
$_d=array();
$_e=array();
$_f=array();
$_g=array();
$_h=array();
$_i=array();
$_1=array();
$_2=array();
$_3=array();
$_4=array();
$_5=array();
$_6=array();
$_7=array();
$_8=array();
$_9=array();
}
else
{
$i++;
}
}
# echo "intentos: ".$j;
return $resultado;
}
SIGO EN LAS RESPUESTAS PORQUE EL POST ENTERO ES MUY LARGO