Comunidad de diseño web y desarrollo en internet

Algoritmo para generar y resolver sudokus con código Actionscript 2

Con estas dos funciones podemos generar billones de Sudokus así como solucionar cualquier Sudoku por difícil que sea. Están escritas en Actionscript 2 para Flash. Aunque no es un lenguaje muy apropiado para ello, se obtienen unos resultados de alta calidad, tanto en uso de recursos como en velocidad. Añado, como ejemplo de uso, una pequeña aplicación que las emplea.

GENERAR UN SUDOKU

Las 2 soluciones más comunmente empleadas para presentar sudokus son las bases de datos y los generadores.

Las bases de datos ocupan un volumen y ficheros externos con su tratamiento y, aun siendo una solución sencilla, esta limitada a una cantidad. Los generadores de origen aleatorio + comprobación producen, en general, Sudokus simples y en la mayoría de las ocasiones de solución múltiple.

Debemos recordar que, por definición, un Sudoku debe de tener una y sólo una solución.

El generador que presento produce Sudokus correctos con solución única mezclando ambas características:

Por un lado una compleja mini base de datos comprimida en una cadena Unicode y por otro varios algoritmos de mezcla de dichos datos aplicando Teoría de Grupos.

El resultado es un generador que produce 16.273,534.447,779.840 ( algo mas de 16000 billones) de sudokus distintos y correctos entre 17(mínimo para solución única) y 45 casillas iniciales.

Además, el generador no necesita comprobación de solución para saber si son correctos: Los son por sus propiedades de construcción.

Veamos algunos conceptos simples y sin meternos en profundidades:

Sudokus Matemáticamente semejantes

Parece evidente que el nº 1 y el nº 2 son iguales (semejantes), solo hemos cambiado donde había un 3 por un 4 y viceversa.
La diferencia entre el nº 1 y el nº 3 es simplemente un cambio de filas por columnas.

Entre el nº 1 y el nº 4 las semejanza ya no es tan evidente, no tienen ni siquiera el mismo número de elementos y el orden parece muy distinto, sin embargo son MATEMATICAMENTE SEMEJANTES pues proceden de la misma fuente única y mantiene invariante su nivel de restricción.(eso no lo explico por ser más complejo, pero es así, creedme)

Otra propiedad que usaremos es esta:
“Si un sudoku tiene solución única, al añadir mas elementos de esa misma solución, esta se mantiene única”.

De este modo si tenemos un sudoku base de, por ejemplo, 20 elementos y dificultad 9 y le añadimos 4 elementos más, tendremos otro de 24 elementos y menor o igual dificultad.
Veamos 4 sudokus generados desde la misma fuente y con dificultades iguales o diferentes:


Estos son los sistemas mezclados que usaremos, junto con la eliminación o conmutación de grupos iguales de valores, en la formación de la cadena Unicode que nos sirve de base de datos:

Un primer grupo con un sudoku de un nivel determinado y múltiples subgrupos asociados de elementos que podemos añadir al primero, manteniendo esos valores dentro de la solución única, para “rebajar” su dificultad y añadiendo una mezcla combinatoria congruente.

Consideraciones sobre la dificultad

La cantidad de casillas iniciales ocupadas no es muestra real de la dificultad de un Sudoku.
Algunas bases de datos estás catalogadas de acuerdo a ese concepto y son erróneas en cuanto a la correcta clasificación de su dificultad. Los generadores usan un cálculo de tiempo de solución por algoritmo y adolecen del mismo problema. Un Sudoku que el algoritmo resuelva más rápido que otro no es más fácil para un humano por esa cualidad.

El problema del nivel de dificultad está resuelto al crear la minibase mediante un estudio estadístico de la velocidad de resolución con variaciones de los procesos de deducción (algoritmos de búsqueda diferenciados) y un análisis de regresión sobre los mismos hecho previamente a la selección de la base usada. Están graduados en 9 niveles.

Este es el código

//n: nivel de dificultad (de 1 a 9);
function generar(n) {
    if (!nini) {
 z=" -aquí va la cadena unicode, debereis bajar el FLA pues solo copiando NO funcionará- ";
        nini = true;
    }
    f = Math.floor;
    r = Math.random;
    B = 4096;
    d1 = [];
    d2 = [];
    m = [];
    s0 = "";
    kr = [];
    kf = [];
    ks = [];
    kt = [];
    rd = r()<.5;
    al = z.length;
    rg = f(al*r());
    for (var j = 0; j<10; j += 9) {
        for (var h = 0; h<3; h++) {
            if (!h) {
                m2(j);
            }
            m1(m, j+3*h, 3*h+3+j);
        }
    }
    for (var j = 0; j<3; j++) {
        m[j] = m[9+j*3].concat(m[10+j*3].concat(m[11+j*3]));
    }
    m1(m, 0, 3);
    m[3] = m[0].concat(m[1].concat(m[2]));
    for (var j = 0; j<9; j++) {
        d1[j] = j+1;
        for (var h = 0; h<3; h++) {
            v = j*3+h;
            w = 9*(v%9)+f(v/9);
            m[0][v] = m[3][w];
            m[1][v] = m[3][w+3];
            m[2][v] = m[3][w+6];
        }
    }
    m1(m, 0, 3);
    m1(d1, 0, 9);
    sl = m[0].concat(m[1].concat(m[2]));
    for (var v = 0; v<al; v++) {
        t = (rg+v)%al;
        k0 = z.charCodeAt(t);
        nv = (15 & k0)-n;
        if (k0<=B && nv>=0 && nv<6) {
            cn = 0;
            d = k0 >> 8;
            s = (240 & k0) >> 4;
            for (var h = 1+t; h<=s+t; h++) {
                k1 = z.charCodeAt(h)-B;
                kf[0] = 15 & k1;
                kf[1] = (240 & k1) >> 4;
                kf[2] = (3840 & k1) >> 8;
                kf[3] = k1 >> 12;
                for (var j = 0; j<4; j += 2) {
                    cn += kf[j];
                    if (kf[j+1]) {
                        ks.push(cn, kf[j+1]);
                        cn++;
                    }
                }
            }
            q = f(r()*2)+nv*2+f(r()*(nv+1));
            for (var h = s+1+t; h<=s+d+t; h++) {
                kt[h-s-1-t] = z.charCodeAt(h)-B;
            }
            for (var h = 0; h<kt.length-1; h += 3) {
                m1(kt, 2, h+3);
            }
            for (var h = 0; h<q; h++) {
                k3 = f(kt[h]/10);
                ks.push(k3, kt[h]-k3*10);
            }
            lg = ks.length;
            break;
        }
    }
    for (var h = 0; h<lg-1; h += 2) {
        kr[sl[ks[h]]] = d1[ks[h+1]-1];
    }
    for (var j = 0; j<81; j++) {
        s0 += kr[j] ? kr[j] : ".";
    }
    return s0;
    function m1(b, a, c) {
        for (var i = c-a; i>1; i--) {
            e = a+f(i*r());
            o = b[i-1+a];
            b[i-1+a] = b[e];
            b[e] = o;
        }
        return (b);
    }
    function m2(a) {
        for (var j = 0; j<9; j++) {
            m[j+a] = [];
            for (var h = 0; h<9; h++) {
                m[j+a][h] = a == 0 ? rd ? j*9+h : h*9+j : m[h][j];
            }
        }
    }
}
//Ejemplo:
trace(generar(6));
//Manda la panel de salida el sudoku generado con dificultad 6(media-superior) y solución única.
//Tipo de salida: 8..56...14..9...8......83.2.2...1....8..2.7....3.....46.....2..3.524....2.9.5..6.
//Los puntos son casillas vacias.(cadena de las 81 casillas) 

Nota:
Abajo encontrarás link de descarga a los archivos del tutorial.

Para usar el generador, simplemente llamaremos a la función usando como parámetro el nivel deseado:
generar(nivel).

La salida se entrega como una cadena de 81 elementos denotando con ".", las casillas vacías y con su número, las ocupadas.

Ejemplo:
...6.3.5.......2.95....4...34......578.......2..89..1..18....7..32.6.........2.3.
Podemos aplicarle un split("") para convertirlo en array y usar los datos en nuestro programa.
Para copiar la función deberéis tomar el código desde archivo FLA siguiente pues es posible que la cadena unicode simplemente copiada no os sea útil.

RESOLVER UN SUDOKU

También para encontrar la solución de un Sudoku se emplean diversas técnicas, cada una con sus ventajas e inconvenientes.

  • Fuerza Bruta: Eficaz, pero si solo se usa un sistema de condición para poder resolver Sudokus extremos es realmente tedioso y lento.
  • Backtracking de fuerza bruta: Mejor, pero hay que considerar que el nivel de recursividad de AS2 esta en 256 de profundidad y puede si no se toman muchas precauciones alcanzarse fácilmente. AlgoritmoX y DLX.
  • Devorador: Usando heurísticos, saltamos muchas ramas del árbol. Tiene el peligro que, si no se programan muy atinadamente dichos heurísticos, podemos no encontrar la solución al terminar el ciclo de búsqueda.
  • Devorador+Backtracking: si el Devorador no dio solución, pasamos al Backtracking para asegurar la solución.
  • Ramificación y poda: Es un tipo de devorador donde los heurísticos tienden a eliminar, más que a encontrar, las no soluciones.

Aparece además otra necesidad: Si deseamos determinar si la solución es única, tenemos que agotar el algoritmo y no salirnos del mismo al encontrar una solución posible.

Es entonces claro que el mejor camino para el estudio de Sudokus es el último citado.

En general existe mucha bibliografía de scripts para resolver sudokus donde básicamente se busca un condicional de tipo "vale ahí o no se puede poner ahí".(FN) En el Sudoku es más fácil descartar que encontrar.
Por eso propongo este código.
Esta basado en la rápida eliminación de lo no posible (poda) y almacenamiento al mismo tiempo (mismo ciclo de función) de lo posible.

El tiempo medio de resolución obtenido en un muestreo de 100.000 sudokus distintos es de 0.124ms.(en un ordenador 64Dual4700) y de 0.335ms. en un vetusto 386! (que todavía mantengo vivo para estos casos)
No utiliza recursividad de llamada (por lo que no es problema los 256 niveles) y resuelve el 89% de los sudokus en un solo ciclo y el 97% en solo 2 ciclos.

Para algunos Sudokus extremos de nivel 9 y con una ordenación realmente desafortunada para el algoritmo( realmente muy difíciles, el 0.0000000000000000001% del total) puede tardar hasta 120 ciclos (sobre 2,6 segundos en el mismo referente).

Podríamos ampliar el algoritmo para reducir drásticamente ese tiempo en los extremos pero aumentaría en el resto y sería contraproducente en el valor medio. No creo necesario usar un Concorde para ir a fumigar.

En cuanto al consumo de recursos, tanto de micro como de memoria, este es realmente mínimo.

En Actionscript 3 y gracias a las nuevas clases de manejo de arrays, el poder usar enteros declarados y el superior manejo a nivel de bit, el código se vuelve unas doce veces más rápido y compite con el mismo código formulado en C o en Phyton. Lo pondré como clase AS3 más adelante pues estoy afinándolo todo lo que sé y voy aprendiendo (me divierte un montón el asunto).

El script determina asimismo si la solución es única o si existe más de una. En ese sentido la búsqueda es exhaustiva (aunque se podría modificar fácilmente para encontrar y dar salida a todas, basta con saber que no es un Sudoku válido al tener más de una solución).

Este es el código:

function resolver(m) {
    if (!ini) {
        tablas();
        ini = true;
    }
    s = []; q = []; ct = 0; act = []; aq = []; // inicializando o creando arrays
    for (var j = 0; j<81; j++) {
        s[j] = 511;
    }
    e = m.split("");
    for (var h = 0; h<e.length; h++) {
        if (e[h]>="1" && e[h]<="9") {
            colocar(s, h, e[h]);
        }
    }
    q[0] = resolver2(s).slice();
    cons(q[0]);
    while (ct<81 && ct>-1) {
        if (ct2<0) {
            return q[ct].slice(81, 162).join("");
        }
        colocar(q[ct], ct2, act[ct].pop());
        if (!resolver2(q[ct])) {
            q[ct] = aq[ct].slice();
            while (!act[ct][0] && ct>-1) {
                ct--;
                ct2 = q[ct][162];
                q[ct] = aq[ct].slice();
            }
        } else {
            ct++;
            q[ct] = q[ct-1].slice();
            cons(q[ct]);
        }
    }
    return "sin solución";
    function resolver2(s) {
        do {
            sp = [];
            for (var j = 0; j<81; j++) {
                if (!s[j+81]) {
                    if (t4[s[j]] == 0) {
                        return false;
                    }
                    if (t4[s[j]] == 1) {
                        sp.push(j, t3[s[j]]);
                    }
                }
            }
            for (var j = 0; j<27; j++) {
                s1 = [];
                s2 = 0;
                for (var h = 0; h<9; h++) {
                    if (!s[t1[j][h]+81]) {
                        s1[s2] = t1[j][h];
                        s2++;
                    }
                }
                s5 = s1.length;
                if (!s5) {
                    continue;
                }
                r1 = 0;
                r2 = s[s1[0]];
                for (var h = 1; h<s5; h++) {
                    r1 = (s[s1[h]] & r2) | r1;
                    r2 = (s[s1[h]] ^ r2) & ~r1;
                }
                if (s5 != t4[r1]+t4[r2]) {
                    return false;
                }
                if (r2) {
                    for (var h = 0; h<9; h++) {
                        if (s[s1[h]] & r2) {
                            s3 = s1[h];
                            s4 = t3[s[s1[h]] & r2];
                            if (s4.length>1) {
                                return false;
                            }
                            if (s3) {
                                sp.push(s3, s4);
                            }
                        }
                    }
                }
            }
            for (var v = 0; v<sp.length; v += 2) {
                for (var j = 0; j<21; j++) {
                    sa = t[sp[v]][j];
                    if (sa != sp[v] && s[sa+81] == sp[v+1]) {
                        return false;
                    }
                }
                colocar(s, sp[v], sp[v+1]);
            }
        } while (sp[0]);
        return s;
    }
    function cons(s) {
        min = 9;
        ct2 = -1;
        for (var j = 0; j<81; j++) {
            if (!s[j+81] && t4[s[j]]<min) {
                min = t4[s[j]];
                ct2 = j;
            }
            if (min == 2) {
                break;
            }
        }
        s[162] = ct2;
        aq[ct] = s.slice();
        act[ct] = t3[s[ct2]].split("");
    }
    function colocar(s, a, b) {
        s[81+a] = b;
        for (var h = 0; h<21; h++) {
            s[t[a][h]] &= ~(1 << (b-1));
        }
    }
    function tablas() {
        t = [];
        t1 = [];
        t2 = [];
        t3 = [];
        t4 = [];
        for (var j = 0; j<512; j++) {
            rt = "";
            for (var h = 0; h<9; h++) {
                if (j & (1 << h)) {
                    rt += h+1;
                }
            }
            t3[j] = rt;
            t4[j] = t3[j].length;
        }
        for (var j = 0; j<81; j++) {
            t[j] = [];
            t2[j] = [Math.floor(j/9), 9+j%9, 3*Math.floor(j/27)+Math.floor(j%9/3)+18];
            for (var v = 0; v<3; v++) {
                if (!t1[t2[j][v]]) {
                    t1[t2[j][v]] = [];
                }
                t1[t2[j][v]].push(j);
            }
        }
        for (var j = 0; j<81; j++) {
            t[j] = t1[t2[j][0]].concat(t1[t2[j][1]]).concat(t1[t2[j][2]]);
            n = 0;
            t[j].sort(16);
            while (n<t[j].length-1) {
                t[j][n+1] == t[j][n] ? t[j].splice(n, 1) : n++;
            }
        }
    }
}
//Ejemplo: 
m1 = "...6.3.5.......2.95....4...34......578.......2..89..1..18....7..32.6.........2.3.";
trace(m1);
b = resolver(m1);
trace(b);
// salida 1 :194623857863571249527984163349216785781435926256897314618359472432768591975142638
for (var j = 0; j<81; j += 9) {
    trace(b.substr(j, 9));
}
/*
Salida 2 :
    194623857
    863571249
    527984163
    349216785
    781435926
    256897314
    618359472
    432768591
    975142638
*/

Nota:
Abajo encontrarás link de descarga a los archivos del tutorial.

Como base usa un array de 162 elementos donde almacenamos los datos de cada posición-estado del Sudoku.
Los primeros 81 (0 a 80) contienen un valor binario que nos dice los números válidos para cada casilla, también numeradas de (0 a 80), y del modo siguiente:

Inicialimente todos los valores valen y su correspondencia es 511, segun algunos valores no son válidos almacenamos el número asociado a su estado:

Los 81 valores siguientes del mismo array son los números ya asignados en cada casilla de modo que un valor en el array Q[100]=6; nos indica que en la casilla 19 (100-81) tenemos colocado un 6.
El usar un array no multidimensional tiene en este caso sus ventajas:

Para clonar o copiar un array Q en otro nuevo S podemos utilizar la igualación:

S = Q;
Esto hace que si en Q se modifica algún elemento en S también se modifique y eso no es lo deseado.
S = Q.slice();
De este modo solo hacemos una copia del puntero de Q rápidamente. Si modificamos algún valor en Q, en S no cambiará…..en su primer nivel solamente! Esto quiere decir que si Q es un array multidimensional, solo los elementos del array inicial (luego creamos la/las siguientes dimensiones “colgándolas“ de la inicial) quedan desligados, el resto de niveles mantendrá el valor de Q y si los variamos, cambiará S.

Para conseguir hacer una copia S desligada de Q, siendo este un array multidimensional, tendremos que hacer una copia o clon elemento a elemento. Por eso es mejor en este caso, por cuestiones de velocidad y sencillez, usar un array simple con doble tipo de datos:

  • En Q[n] tenemos los 81 valores binarios de números posibles y en Q[81+n] los 81 números colocados en cada casilla.
  • El centro del algoritmo se encuentra en esta instrucción:
    for(var h=1;h<s5;h++){r1=(s[s1[h]]&r2)|r1;r2=(s[s1[h]]^r2)&~r1;}
  • Y que trabaja con operaciones de bit para mayor velocidad. El script produce inicialmente, y solo en su primera llamada, una tabla (no confundir con la DLX) para crear 4 arrays de comprobación.

Vamos a rellenar unos arrays con los valores y datos que necesitamos:

Un array t3[ ] donde almacenamos los 512 valores (2^9 binario) posibles de cada casilla pero expresados como cadena de elementos que quedan:

Ejemplos:
t3[ 511] contiene 123456789 (todos valen, inicio) luego guardamos la cadena “123456789”
t3[25] contiene 145 (valen, está su flag, el 1 2^0=1 el 4 2^3=8 y el 5 2^4=16, 1+8+16=25) guardamos “145”;
En t4[ ] guardamos la longitud de cada t[3] para saber el número de elementos que valen en cada casilla, en cada momento.

Ejemplos: t4[511] = 9 y t4[25] = 3
En t2[ ][ ] vamos a almacenar tres valores por elemento. Cada una de las 81 casillas pertenece a una fila(9), una columna(9) y un bloque(9). Esos 3 valores son los que guardamos teniendo en cuenta que esos 27 elementos los ordenamos así: 0 a 8 las filas, 9 a 17 las columnas y 18 a 26 los bloques.

Ejemplos: t2[27] = [ 3,9,21]
Es decir, la casilla 27 esta en la fila 3 , en la columna 9 y en el bloque 21.
En t[ ][ ] finalmente almacenaremos para cada casilla su “casa” es decir las 21 casillas(incluida ella misma) a las que afecta una variación en esa casilla.

Ejemplo: tomemos la “casa” de la casilla 43 (usar el sudoku aplicación de más abajo)
La casilla 43 se encuentra en la fila 4 que está formada por las casillas: 36,37,38,39,40,41,42,43,44
En la columna 16 casillas: 7,16,25,34,43,52,61,70,79
En el bloque 24 casillas: 33,34,35,42,43,44,51,52,53
Eliminando los duplicados, tenemos:
t[43]=[7,16,25,33,34,35,36,37,38,39,40,41,42,43,44,51,52,53,61,70,79]

Que nos es muy útil tanto para asignar un valor a una casilla como para comprobar, pues cuando cambia un valor de válidos (o candidatos) esas son las 21 casillas que también cambiaran o han de actualizarse.

Consultando esos arrays que conforman las tablas y el array principal de estado tendremos, mediante condicionales, el control del estado del sudoku en todo momento.

Para utilizar la función hay que enviar a la misma como parámetro una cadena del mismo tipo que empleamos en la salida del generador: Una cadena de 81 elementos (0 a 80) donde las casillas vacías se representen por cualquier elemento, que no sea un número, y las válidas por el número.

Ejemplo:
...6.3.5.......2.95....4...34......578.......2..89..1..18....7..32.6.........2.3.

La salida será la misma cadena completada de 81 números o "sin solución".

Salida del ejemplo:
194623857863571249527984163349216785781435926256897314618359472432768591975142638

CREAR UN PROGRAMA GENERADOR Y RESOLVEDOR DE SUDOKUS

Con esas 2 funciones, y aunque no las comprendáis en profundidad, podréis crear, con vuestro propio diseño, una aplicación sobre Sudokus de muy buen nivel.

Yo he compuesto esta como ejemplo:

La he concebido en plan minimalista (el SWF tiene solamente 8Kb.). Aunque parece algo "espartana" es muy potente para analizar sudokus. Tiene nueve niveles de ayuda con tags, avance y retroceso de operaciones, indicador de permitidos, uso de entrada con la rueda del ratón o botones, nueve niveles de dificultad, entrada, análisis y resolución de sudokus externos, etc…

Las funciones principales (generar y resolver) están algo modificadas para permitir extraer datos de ayuda.
Cuatro de las ayudas están sin implementar... (¿Alguna idea para otra versión?) .

Todo ello con solo código, como veréis en el FLA. No utiliza ningún MC, solo y exclusivamente un campo de texto polivalente como array y creado con en el script.

Descargar Archivo

Publica tu comentario

El autor de este artículo ha cerrado los comentarios. Si tienes preguntas o comentarios, puedes hacerlos en el foro

Entra al foro y participa en la discusión

o puedes...

¿Estás registrado en Cristalab y quieres
publicar tu URL y avatar?

¿No estás registrado aún pero quieres hacerlo antes de publicar tu comentario?

Registrate