Foros del Web » Programando para Internet » PHP »

[APORTE] Generador de sudokus sencillo y explicado

Estas en el tema de [APORTE] Generador de sudokus sencillo y explicado en el foro de PHP en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 26/01/2010, 14:19
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
[APORTE] Generador de sudokus sencillo y explicado

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:
  1. Se genera el sudoku completo, como quedaría una vez resuelto.
  2. 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(0count($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(123456789);
        
$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&#37;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

Última edición por dggluz; 27/01/2010 a las 09:11
  #2 (permalink)  
Antiguo 26/01/2010, 14:20
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

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(128);
        }
        echo 
"<br />Dificultad: $dificultad<br />";
        
$arrPosiciones=array(1234567891011121314151617181920212223242526272829303132

333435363738394041424344454647484950515253545556575859606162636465666768697071

72737475767778798081);
        
$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(123456789);
        
$cols=array(1=>12=>23=>34=>45=>56=>67=>78=>80=>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(123101112192021),
            
'B'=>array(456131415222324),
            
'C'=>array(789161718252627),
            
'D'=>array(282930373839464748),
            
'E'=>array(313233404142495051),
            
'F'=>array(343536434445525354),
            
'G'=>array(555657646566737475),
            
'H'=>array(585960676869767778),
            
'I'=>array(616263707172798081)
        );
    
        
$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;
    } 

Última edición por dggluz; 27/01/2010 a las 09:06
  #3 (permalink)  
Antiguo 26/01/2010, 14:22
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Con eso queda completo el algoritmo de generación de sudokus. Pueden ver en http://www.primolius.com.ar/sudoku.php un ejemplo completo en funcionamiento, cuyo código fuente es el siguiente:
Código PHP:
<?php
    
// Generador de sudokus. Versión original por dggluz (http://www.primolius.com/).
    // Enlace: http://www.forosdelweb.com/f18/aporte-generador-sudokus-sencillo-explicado-772598/
    // De uso libre mientras se cite la fuente y no sea para fines comerciales.
    
    // 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(0count($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(123456789);
        
$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&#37;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;
    }
    
    function 
borrarCasilleros($sudokuOriginal$dificultad=NULL)
    {
        if(
$dificultad==NULL)
        {
            
srand(ceil(999999999*microtime()));
            
$dificultad=rand(128);
        }
        echo 
"<br />Dificultad: $dificultad<br />";
        
$arrPosiciones=array(1234567891011121314151617181920212223242526272829303132

333435363738394041424344454647484950515253545556575859606162636465666768697071

72737475767778798081);
        
$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;
    }
    
    function 
solucionUnica($sudoku, &$posibles$idx)
    {
        
$original=array(123456789);
        
$cols=array(1=>12=>23=>34=>45=>56=>67=>78=>80=>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(123101112192021),
            
'B'=>array(456131415222324),
            
'C'=>array(789161718252627),
            
'D'=>array(282930373839464748),
            
'E'=>array(313233404142495051),
            
'F'=>array(343536434445525354),
            
'G'=>array(555657646566737475),
            
'H'=>array(585960676869767778),
            
'I'=>array(616263707172798081)
        );
    
        
$posibles[$idx]=array();
        
        for(
$i=1$i<=81$i++)
        {
            if(
$sudoku[$i]==NULL)
            {
                
$idxColumna=$cols[$i%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;
    }
?>
Continúa el código fuente abajo...

Última edición por dggluz; 26/01/2010 a las 15:09
  #4 (permalink)  
Antiguo 26/01/2010, 14:22
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Continuación del código fuente completo:
Código PHP:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>Sudoku</title>
    <style>
        .sudoku
        {
            border-style:solid;
            border-width:2px;
            border-color:#000000;
            border-collapse:collapse;
        }
        .sudoku TD
        {
            border-style:solid;
            border-width:1px;
            border-color:#000000;
            width:1.5em;
            height:1.5em;
            text-align:center;
        }
    </style>
    <script type="text/javascript">
        function toogle(id)
        {
            var elm=document.getElementById(id);
            if(elm.style.display=='none')
            {
                elm.style.display='block';
            }
            else
            {
                elm.style.display='none';
            }
        }
    </script>
</head>
<body>
    <?php
        $sudokuCompleto
=completarMatrizSudoku();
        if(isset(
$_GET['dificultad']) && ((int)$_GET['dificultad'])<=28 && ((int)$_GET['dificultad'])>=1)
        {
            
$dificultad=$_GET['dificultad'];
        }
        else
        {
            
$dificultad=NULL;
        }
        
$sudoku=borrarCasilleros($sudokuCompleto$dificultad);
    
?>
    <br />
    <table class="sudoku">
        <?php
            
foreach($sudoku as $idx=>$valor)
            {
                if(
$idx&#37;9==1)
                
{
                    echo 
"<tr>";
                }
                echo 
"<td style=\"";
                if(
$idx%3==0)
                {
                    echo 
"border-right-width:2px;";
                }
                if(
ceil($idx/9)%3==0)
                {
                    echo 
"border-bottom-width:2px;";
                }
                echo 
"\">";
                echo 
$valor."</td>";
                if(
$idx%9==0)
                {
                    echo 
"</tr>";
                }
            }
        
?>
    </table>
    <br />
    <form action="<?php echo $_SERVER['SCRIPT_NAME'];?>" method="get">
        Dificultad (de 1 a 28):&nbsp;<input type="text" size="2" name="dificultad" maxlength="2" />&nbsp;&nbsp;&nbsp;&nbsp;<input type="submit" 

value="&iexcl;Generar!" />
    </form>
    <br />
    <input type="button" onclick="toogle('resultado');" value="Mostrar/Ocultar resultado" />
    <br />
    <div id="resultado" style="display:none;">
        <br />
        <table class="sudoku">
            <?php
                
foreach($sudokuCompleto as $idx=>$valor)
                {
                    if(
$idx%9==1)
                    {
                        echo 
"<tr>";
                    }
                    echo 
"<td style=\"";
                    if(
$idx%3==0)
                    {
                        echo 
"border-right-width:2px;";
                    }
                    if(
ceil($idx/9)%3==0)
                    {
                        echo 
"border-bottom-width:2px;";
                    }
                    echo 
"\">";
                    echo 
$valor."</td>";
                    if(
$idx%9==0)
                    {
                        echo 
"</tr>";
                    }
                }
            
?>
        </table>
    </div>
</body>
</html>
Bueno, eso es todo. Espero que lo hayan disfrutado tanto como yo. ¡Suerte!
  #5 (permalink)  
Antiguo 26/01/2010, 14:28
Avatar de maycolalvarez
Colaborador
 
Fecha de Ingreso: julio-2008
Ubicación: Caracas
Mensajes: 12.120
Antigüedad: 16 años
Puntos: 1532
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

felicidades!, por cierto, ¿no utilizas recursión en este código?, si contemplas esa posibilidad, puedes diseñar un algoritmo que no dependa de una matriz 9x9, aún así, fenomenal código
  #6 (permalink)  
Antiguo 26/01/2010, 14:39
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Cita:
Iniciado por maycolalvarez Ver Mensaje
felicidades!, por cierto, ¿no utilizas recursión en este código?, si contemplas esa posibilidad, puedes diseñar un algoritmo que no dependa de una matriz 9x9, aún así, fenomenal código
El código es sencillo porque es sólo experimental, sin embargo lo que dices es cierto. Pensaré en ello. ¡Suerte!
  #7 (permalink)  
Antiguo 26/01/2010, 17:53
Avatar de pato12  
Fecha de Ingreso: septiembre-2007
Ubicación: Salta
Mensajes: 1.620
Antigüedad: 16 años, 9 meses
Puntos: 101
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Wow... esta muy bueno y me encanta ese juego xD... enseguida lo pruebo :P
__________________
Half Music - www.halfmusic.com
  #8 (permalink)  
Antiguo 26/01/2010, 18:26
Avatar de pateketrueke
Modernizr
 
Fecha de Ingreso: abril-2008
Ubicación: Mexihco-Tenochtitlan
Mensajes: 26.399
Antigüedad: 16 años, 3 meses
Puntos: 2534
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

¡genial!!
__________________
Y U NO RTFM? щ(ºдºщ)

No atiendo por MP nada que no sea personal.
  #9 (permalink)  
Antiguo 26/01/2010, 19:24
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado


Acabo de resolver un sudoku con solución no única... Y además acabo de darme cuenta de que es un error conceptual... voy a tener que seguir trabajando en eso. Tendría que "no haber cantado victoria antes de tiempo". Quien quiera ayudarme puede hacerlo. ¡Suerte!

PD: para los que quieran ayudarme, el problema está en que un solo casillero que pueda completarse con solución única, puede "salvar" a otro montón que no, de modo que no se detecte el momento en que el sudoku deja de tener solución única. Sin embargo, debe haber una forma de comprobar que el sudoku sea de solución única sin tener que resolverlo todo, sobre todo partiendo de un sudoku completo. Lo que realmente habría que probar con cada cambio (lo difícil ahora es descubrir cómo), es que este último cambio no hizo que el sudoku dejara de tener solución única; sino descartarlo.

Última edición por dggluz; 26/01/2010 a las 19:40
  #10 (permalink)  
Antiguo 27/01/2010, 07:49
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Edito: este script tiene un error de implementación, está en la respuesta 11 corregido
------------------
Creo haber descubierto la forma de arreglar el error que describo: la función solucionUnica debe comprobar que el último casillero en vaciarse tenga solución única, no que lo tengan los demás. De este modo, en el orden exactamente inverso que como se van sacando los casilleros, puede resolverse el sudoku, siempre completando los casilleros con soluciones únicas, lo que garantiza que el sudoku entero tiene solución única. La nueva implementación de la función es ésta:
Código PHP:
#'%'
    
function solucionUnica($sudoku, &$posibles$idx)
    {
        
$original=array(123456789);
        
$cols=array(1=>12=>23=>34=>45=>56=>67=>78=>80=>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(123101112192021),
            
'B'=>array(456131415222324),
            
'C'=>array(789161718252627),
            
'D'=>array(282930373839464748),
            
'E'=>array(313233404142495051),
            
'F'=>array(343536434445525354),
            
'G'=>array(555657646566737475),
            
'H'=>array(585960676869767778),
            
'I'=>array(616263707172798081)
        );
    
        
$idxColumna=$cols[$idx%9];
        
$idxFila=ceil($idx/9);
        
$idxCuadrado=$cuadrado[$idx];
        
        
$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[$idx]=array_diff($original$columna$fila$cuadro);
        if(
count($posibles[$idx])==0)
        {
            echo 
"ERROR.";
        }
        elseif(
count($posibles[$idx])==1)
        {
            return 
true;
        }
        return 
true;
    } 
Espero que ahora sí funcione bien. ¡Suerte!

Última edición por dggluz; 27/01/2010 a las 08:52
  #11 (permalink)  
Antiguo 27/01/2010, 08:52
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Nuevo error en el script, pero esta vez fue error de implementación. Ahora sí que tengo la certeza de que funciona bien, pero ya no genera sudokus muy difíciles. Intenta generar con la dificultad que se le indica, pero va sacando sólo los números de los casilleros que puede sin perder la solución única, y a veces da toda la vuelta y no puede sacar muchos números. A continuación, las funciones corregidas:
Código PHP:
    function borrarCasilleros($sudokuOriginal$dificultad=NULL)
    {
        if(
$dificultad==NULL)
        {
            
srand(ceil(999999999*microtime()));
            
$dificultad=rand(128);
        }
        
$arrPosiciones=array(123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081);
        
$arrOrden=$arrPosiciones;
        
shuffle2($arrOrden);
        
$quitados=0;
        
$sudokuResultante=$sudokuOriginal;
        
$limite=$dificultad+35;
        
$i=1;
        while(
$quitados<$limite && $i<81)
        {
            
$sudokuAnt=$sudokuResultante;
            
$quitadosAnt=$quitados;
            
$idx=$arrOrden[$i];
            
$sudokuResultante[$idx]=NULL;
            if(!
solucionUnica($sudokuResultante$quitados$idx))
            {
                
$quitados=$quitadosAnt;
                
$sudokuResultante=$sudokuAnt;
            }
            
$i++;
        }
        
$dificultad=$quitados-35;
        echo 
"<br />Dificultad: $dificultad<br />";
        return 
$sudokuResultante;
    }
    
    function 
solucionUnica($sudoku, &$quitados$idx)
    {
        
$original=array(123456789);
        
$cols=array(1=>12=>23=>34=>45=>56=>67=>78=>80=>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(123101112192021),
            
'B'=>array(456131415222324),
            
'C'=>array(789161718252627),
            
'D'=>array(282930373839464748),
            
'E'=>array(313233404142495051),
            
'F'=>array(343536434445525354),
            
'G'=>array(555657646566737475),
            
'H'=>array(585960676869767778),
            
'I'=>array(616263707172798081)
        );
    
        
$idxColumna=$cols[$idx&#37;9];
        
$idxFila=ceil($idx/9);
        
$idxCuadrado=$cuadrado[$idx];
        
        
$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);
        
        
$opciones=array_diff($original$columna$fila$cuadro);
        if(
count($opciones)==0)
        {
            echo 
"ERROR.";
        }
        elseif(
count($opciones)==1)
        {
            
$quitados++;
            return 
true;
        }
        else
        {
            return 
false;
        }
    } 
Disculpen las molestias (de andar cambiando tantas veces el código ). ¡Suerte!
  #12 (permalink)  
Antiguo 27/01/2010, 09:09
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Debido a todas las idas y vueltas, dejo el script completo como quedó finalizado (tener en cuenta que no logra sudokus muy complicados, y si bien intenta llegar a la dificultad que se le pide, no siempre lo consigue):
Código PHP:
<?php
    
// Generador de sudokus. Versión original por dggluz (http://www.primolius.com/).
    // Enlace: 
    // De uso libre mientras se cite la fuente y no sea para fines comerciales.
    
    // Puede llegar a ocurrir que el script demore demasiado,
    // por eso ponemos un tiempo límite de 10 segundos.
    
set_time_limit(30);
    
    
    
// 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(0count($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(123456789);
        
$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&#37;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;
    }
    
    function 
borrarCasilleros($sudokuOriginal$dificultad=NULL)
    {
        if(
$dificultad==NULL)
        {
            
srand(ceil(999999999*microtime()));
            
$dificultad=rand(128);
        }
        
$arrPosiciones=array(123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081);
        
$arrOrden=$arrPosiciones;
        
shuffle2($arrOrden);
        
$quitados=0;
        
$sudokuResultante=$sudokuOriginal;
        
$limite=$dificultad+35;
        
$i=1;
        while(
$quitados<$limite && $i<81)
        {
            
$sudokuAnt=$sudokuResultante;
            
$quitadosAnt=$quitados;
            
$idx=$arrOrden[$i];
            
$sudokuResultante[$idx]=NULL;
            if(!
solucionUnica($sudokuResultante$quitados$idx))
            {
                
$quitados=$quitadosAnt;
                
$sudokuResultante=$sudokuAnt;
            }
            
$i++;
        }
        
$dificultad=$quitados-35;
        echo 
"<br />Dificultad: $dificultad<br />";
        return 
$sudokuResultante;
    }
    
    function 
solucionUnica($sudoku, &$quitados$idx)
    {
        
$original=array(123456789);
        
$cols=array(1=>12=>23=>34=>45=>56=>67=>78=>80=>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(123101112192021),
            
'B'=>array(456131415222324),
            
'C'=>array(789161718252627),
            
'D'=>array(282930373839464748),
            
'E'=>array(313233404142495051),
            
'F'=>array(343536434445525354),
            
'G'=>array(555657646566737475),
            
'H'=>array(585960676869767778),
            
'I'=>array(616263707172798081)
        );
    
        
$idxColumna=$cols[$idx%9];
        
$idxFila=ceil($idx/9);
        
$idxCuadrado=$cuadrado[$idx];
        
        
$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);
        
        
$opciones=array_diff($original$columna$fila$cuadro);
        if(
count($opciones)==0)
        {
            echo 
"ERROR.";
        }
        elseif(
count($opciones)==1)
        {
            
$quitados++;
            return 
true;
        }
        else
        {
            return 
false;
        }
    }
    
    function 
obtenerPorcion($arrOriginal$arrIdx)
    {
        
$arr=array();
        foreach(
$arrIdx as $idx)
        {
            
array_push($arr$arrOriginal[$idx]);
        }
        return 
$arr;
    }
?>
En la respuesta siguiente está el resto del código del ejemplo completo (se puede probar la implementación de ese ejemplo en http://www.primolius.com.ar/sudoku.php.

Última edición por dggluz; 27/01/2010 a las 09:16
  #13 (permalink)  
Antiguo 27/01/2010, 09:09
Avatar de dggluz  
Fecha de Ingreso: abril-2009
Ubicación: Buenos Aires, Argentina
Mensajes: 525
Antigüedad: 15 años, 2 meses
Puntos: 50
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Resto del código del ejemplo completo:
Código PHP:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>Sudoku</title>
    <style>
        .sudoku
        {
            border-style:solid;
            border-width:2px;
            border-color:#000000;
            border-collapse:collapse;
        }
        .sudoku TD
        {
            border-style:solid;
            border-width:1px;
            border-color:#000000;
            width:1.5em;
            height:1.5em;
            text-align:center;
        }
    </style>
    <script type="text/javascript">
        function toogle(id)
        {
            var elm=document.getElementById(id);
            if(elm.style.display=='none')
            {
                elm.style.display='block';
            }
            else
            {
                elm.style.display='none';
            }
        }
    </script>
</head>
<body>
    <?php
        $sudokuCompleto
=completarMatrizSudoku();
        if(isset(
$_GET['dificultad']) && ((int)$_GET['dificultad'])<=28 && ((int)$_GET['dificultad'])>=1)
        {
            
$dificultad=$_GET['dificultad'];
        }
        else
        {
            
$dificultad=NULL;
        }
        
$sudoku=borrarCasilleros($sudokuCompleto$dificultad);
    
?>
    <br />
    <table class="sudoku">
        <?php
            
foreach($sudoku as $idx=>$valor)
            {
                if(
$idx&#37;9==1)
                
{
                    echo 
"<tr>";
                }
                echo 
"<td style=\"";
                if(
$idx%3==0)
                {
                    echo 
"border-right-width:2px;";
                }
                if(
ceil($idx/9)%3==0)
                {
                    echo 
"border-bottom-width:2px;";
                }
                echo 
"\">";
                echo 
$valor."</td>";
                if(
$idx%9==0)
                {
                    echo 
"</tr>";
                }
            }
        
?>
    </table>
    <br />
    <form action="<?php echo $_SERVER['SCRIPT_NAME'];?>" method="get">
        Dificultad (de 1 a 28):&nbsp;<input type="text" size="2" name="dificultad" maxlength="2" />&nbsp;&nbsp;&nbsp;&nbsp;<input type="submit" value="&iexcl;Generar!" />
    </form>
    <br />
    <input type="button" onclick="toogle('resultado');" value="Mostrar/Ocultar resultado" />
    <br />
    <div id="resultado" style="display:none;">
        <br />
        <table class="sudoku">
            <?php
                
foreach($sudokuCompleto as $idx=>$valor)
                {
                    if(
$idx%9==1)
                    {
                        echo 
"<tr>";
                    }
                    echo 
"<td style=\"";
                    if(
$idx%3==0)
                    {
                        echo 
"border-right-width:2px;";
                    }
                    if(
ceil($idx/9)%3==0)
                    {
                        echo 
"border-bottom-width:2px;";
                    }
                    echo 
"\">";
                    echo 
$valor."</td>";
                    if(
$idx%9==0)
                    {
                        echo 
"</tr>";
                    }
                }
            
?>
        </table>
    </div>
</body>
</html>
¡Suerte!
  #14 (permalink)  
Antiguo 15/04/2012, 22:23
 
Fecha de Ingreso: abril-2012
Mensajes: 1
Antigüedad: 12 años, 2 meses
Puntos: 0
Respuesta: [APORTE] Generador de sudokus sencillo y explicado

Buenas noches! He estado analizando el codigo y me parece super interesante. He probado la pagina donde esta y sale perfecto. Pero no he podido echarlo a andar en un server para ver como funciona.
me manda error Parse error: en esta parte del programa
<?php
foreach($sudoku as $idx=>$valor)
{
if($idx%9==1)
{
echo "<tr>";
}
echo "<td style=\"";
if($idx%3==0)
{
echo "border-right-width:2px;";
}
if(ceil($idx/9)%3==0)
{
echo "border-bottom-width:2px;";
}
echo "\">";
echo $valor."</td>";
if($idx%9==0)
{
echo "</tr>";
}
}
?>
en especial la linea if($idx%9==1).
Como puedo corregirlo??
Gracias

Etiquetas: aportes
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 4 personas




La zona horaria es GMT -6. Ahora son las 01:51.