[APORTE] Generador de sudokus sencillo y explicado

[dggluz]

Extracción de números:
Bueno, una vez tenemos el sudoku completo debemos quitarle números de forma aleatoria. Pero hay que tener cierto cuidado con ello, puesto que el sudoku debe
tener siempre solución única. Ese es uno de los retos más grandes al que me enfrenté cuando hice este programa. Para ello me baso en la inducción y la recursividad: si dada una situación determinada en el sudoku no completo, éste tiene solución única, entonces debe poder inferirse en por lo menos un casillero vacío cuál es el número correspondiente en forma unívoca (sólo puede haber un número que cumpla las condiciones). Es decir, que si en un sudoku no podemos encontrar ningún casillero vacío que podamos completar unívocamente, entonces el sudoku NO tiene solución única; pero ello no quiere decir que si podemos encontrar uno necesesariamente el sudoku tenga solución única. Por ejemplo, puede darse el caso de que luego de completar ese casillero, el sudoku aún no esté completo y sin embargo no haya ningún otro casillero vacío al que podamos completar unívocamente.

El siguiente texto pertenecía al POST original, pero tiene un error conceptual:
"Pero por suerte, partiendo de un sudoku de solución única, podemos asegurar que si al sacarle el valor a un casillero, seguimos teniendo casilleros vaciós con solución única, entonces el sudoku sigue teniendo solución única. Entonces todo se reduce a partir de un sudoku con solución única para ir sacándole valores siempre comprobando que haya al menos un casillero que se pueda completar unívocamente."
En lugar de eso, debe decir:
"Pero por suerte, partiendo de un sudoku de solución única, podemos asegurar que si al sacarle el valor a un casillero, ese casillero tiene solución única, entonces el sudoku sigue teniendo solución única. Entonces todo se reduce a partir de un sudoku con solución única para ir sacándole valores siempre comprobando que el último en ser sacado se pueda completar unívocamente".
A lo largo de las respuestas se puede ver cómo evolucionó el desarrollo del problema. Sigue el resto del texto original del post:

¿Pero existe un sudoku que podamos saber a priori que tiene solución única?: ¡desde luego: el sudoku completo! Ahora entonces nos queda saber cuándo un casillero tiene solución única. Si bien hay distintos métodos deductivos para resolver un sudoku, para no complicar demasiado las cosas decidí corroborar las soluciones posibles solamente basándome en las reglas (que no se repitan números en las filas, columnas y cuadrados); por lo tanto, ese es el método que se usa en este programa para saber si un casillero tiene solución única. Veamos el algoritmo entonces: la función borrarCasilleros() recibe el sudoku original (y optativamente un nivel de dificultad) y le empieza a quitar casilleros. Para ello desordena un array con los números del 1 al 81 y en ese orden empieza a retirarlos, comprobando siempre (con ayuda de la función solucionUnica) que tenga solución única, en caso de que no la tenga, da un paso atrás y sigue quitando números salteándose el número problemático. La cantidad de números a quitar depende del nivel de dificultad (si éste no es pasado como parámetro, se calcula aleatoriamente). Leí (cuando investigaba para hacer este programa) que el número mínimo de casilleros completos que debe tener un sudoku para tener solución única es de 17. Un sudoku que tenga más de la mitad de casilleros puede considerarse un sudoku fácil, de modo que la cantidad de casilleros a quitar está en el rango de [36 - 64], para que el sudoku quede con un cantidad de casilleros completos que está en el rango de [17-45]; es decir que disponemos de 28 niveles de dificultad.

Acá está entonces la función que quita números al sudoku completo:

Código PHP:

      function borrarCasilleros($sudokuOriginal, $dificultad=NULL)
    {
        if($dificultad==NULL)
        {
            srand(ceil(999999999*microtime()));
            $dificultad=rand(1, 28);
        }
        echo "<br />Dificultad: $dificultad<br />";
        $arrPosiciones=array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 

33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 

72, 73, 74, 75, 76, 77, 78, 79, 80, 81);
        $arrOrden=$arrPosiciones;
        shuffle2($arrOrden);
        $quitados=array();
        $sudokuResultante=$sudokuOriginal;
        $limite=$dificultad+35;
        $i=1;
        while(count($quitados)<$limite && $i<81)
        {
            $sudokuAnt=$sudokuResultante;
            $quitadosAnt=$quitados;
            $idx=$arrOrden[$i];
            $sudokuResultante[$idx]=NULL;
            if(!solucionUnica($sudokuResultante, $quitados, $idx))
            {
                $quitados=$quitadosAnt;
                $sudokuResultante=$sudokuAnt;
            }
            else
            {
                $i++;
            }
        }
        return $sudokuResultante;
    } 
   

Como vemos, esta función se vale de otra: solucionUnica. Esta última se fija para todos los casilleros (vacios), si cada uno tiene solución única, valiéndose únicamente de las reglas del juego (como mencioné más arriba). Para ello usa un sistema muy similar al que se usó para generar el sudoku completo: se obtienen todos los números de la columna, de la fila y del cuadrado y se fija cuántos quedan disponibles: si no queda ninguno es que hay un error en el programa (hasta ahora no paso, y si eso de los 17 casilleros es cierto, no pasará jamás), si queda exactamente uno, el casillero tiene solución única, y (suponiendo que se partía de un sudoku de solución única al que se le quitó un casillero) significa que el sudoku tiene solución única (y como no tiene por qué seguir buscando, simplemente devuelve true), si queda más de un número disponible, se sigue buscando en el resto de los casilleros, hasta que aparezca alguno con solución única o se termine el sudoku. Esta misma función recibe por referencia un array que sirve al mismo tiempo para saber cuáles son los casilleros que se van quitando y para contarlos. Además, se vale de una pequeña función (que me extraña no haberla encontrado en php.netque dados dos arrays devuelve un terero que contiene los elementos del primer array cuyo índice es un elemento del segundo. Aquí están esas dos funciones:

Código PHP:

      function solucionUnica($sudoku, &$posibles, $idx)
    {
        $original=array(1, 2, 3, 4, 5, 6, 7, 8, 9);
        $cols=array(1=>1, 2=>2, 3=>3, 4=>4, 5=>5, 6=>6, 7=>7, 8=>8, 0=>9);
        $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');
        $cuadrados=array(
            'A'=>array(1, 2, 3, 10, 11, 12, 19, 20, 21),
            'B'=>array(4, 5, 6, 13, 14, 15, 22, 23, 24),
            'C'=>array(7, 8, 9, 16, 17, 18, 25, 26, 27),
            'D'=>array(28, 29, 30, 37, 38, 39, 46, 47, 48),
            'E'=>array(31, 32, 33, 40, 41, 42, 49, 50, 51),
            'F'=>array(34, 35, 36, 43, 44, 45, 52, 53, 54),
            'G'=>array(55, 56, 57, 64, 65, 66, 73, 74, 75),
            'H'=>array(58, 59, 60, 67, 68, 69, 76, 77, 78),
            'I'=>array(61, 62, 63, 70, 71, 72, 79, 80, 81)
        );
    
        $posibles[$idx]=array();
        
        for($i=1; $i<=81; $i++)
        {
            if($sudoku[$i]==NULL)
            {
                $idxColumna=$cols[$i&#37;9];
                $idxFila=ceil($i/9);
                $idxCuadrado=$cuadrado[$i];
                
                $idxsColumna=array();
                $idxsFila=array();
                for($j=1; $j<=9; $j++)
                {
                    array_push($idxsColumna, ($idxColumna+9*($j-1)));
                    array_push($idxsFila, ($j+($idxFila-1)*9));
                }
                $idxsCuadrado=$cuadrados[$idxCuadrado];
                
                $columna=obtenerPorcion($sudoku, $idxsColumna);
                $fila=obtenerPorcion($sudoku, $idxsFila);
                $cuadro=obtenerPorcion($sudoku, $idxsCuadrado);
                
                $posibles[$i]=array_diff($original, $columna, $fila, $cuadro);
                if(count($posibles[$i])==0)
                {
                    echo "ERROR.";
                }
                elseif(count($posibles[$i])==1)
                {
                    return true;
                }
            }
        }
        return true;
    }
    
    function obtenerPorcion($arrOriginal, $arrIdx)
    {
        $arr=array();
        foreach($arrIdx as $idx)
        {
            array_push($arr, $arrOriginal[$idx]);
        }
        return $arr;
    }