logoExtra: script.resolver_sudokus

Descripción: Serie de funciones que ayudan a resolver sudokus..


A continuación mostramos los apuntes asociados a este extra:

Resolver sudokus
Para poder resolver sudokus sencillos hemos buscado los números candidatos, discriminando los existentes en el recuadro (grupo de casillas adyacentes mostradas del mismo color), fila y columna de la casilla en cuestión.
// Descripción para sindicación:
/*
    [rss]Serie de funciones que ayudan a resolver sudokus..[/rss]
*/

arr_sudoku = [];
solucion = [];
marcas = [];

function poner_marca()    {
    marcas.push(document.forms.form_sudo.inicio.value);// = sudo;
}

function quitar_marca()    {
    if (marcas.length == 0)
        alert("no hay marcas")
    else    {
        sudo = marcas.pop();
        document.forms.form_sudo.inicio.value = sudo;
        entrar_sudoku(sudo);
    }
}

poner_evento(window, "load", iniciar_sudoku_blanco);

function resolver_casilla_facil(i, j)    {
    cambio = false;
    s = arr_sudoku;
    fila = s[i];
    valor = fila.charAt(j);
    if ("123456789".indexOf(valor) > -1)    {
        //solucion.push("casilla [" + i + ", " + j + "] resuelta: " + valor);
    }
    else    {
        cadena = "";
        for (_i = 0; _i < 9; _i++)
            if ("123456789".indexOf(fila.charAt(_i)) > -1)
                cadena += fila.charAt(_i);
        for (_i = 0; _i < 9; _i++)
            if ((_i != i) && "123456789".indexOf(s[_i].charAt(j)) > -1)
                if (cadena.indexOf(s[_i].charAt(j)) == -1)
                    cadena += s[_i].charAt(j);
        baseX = 3 * parseInt(i / 3);
        baseY = 3 * parseInt(j / 3);
        for (_i = 0; _i < 3; _i++) for (_j = 0; _j < 3; _j++)
            if (((baseX + _i != i) && (baseY + _j != j)) && "123456789".indexOf(s[baseX + _i].charAt(baseY + _j)) > -1)
                if (cadena.indexOf(s[baseX + _i].charAt(baseY + _j)) == -1)
                cadena += s[baseX + _i].charAt(baseY + _j);
        candidatos = "";
        for (_i = 0; _i < 9; _i++)
            if (cadena.indexOf("123456789".charAt(_i)) == -1)
                candidatos += "123456789".charAt(_i);
        if (candidatos.length == 1)    {
            n = candidatos[0];
            arr_sudoku[i] = s[i].substr(0, j) + candidatos + s[i].substr(j + 1);
            tag("form_sudo").elements.inicio.value = arr_sudoku.join("");
            tag("txt_" + i + "_" + j).replaceChild(document.createTextNode(n), tag("txt_" + i + "_" + j).firstChild);
            cambio = true;
            solucion.push("casilla[" + i + ", " + j + "]\nnúmeros: " + cadena + "\ncandidatos: " + candidatos);
        }
    }
    return cambio;
}

function resolver_sudoku_facil()    {
//    solucion = [];

    terminado = false;
    cadena = tag("form_sudo").elements.inicio.value;
    if (cadena.length > 81)
        cadena = cadena.substr(0, 81)
    else
        while (cadena.length < 81)
            cadena += "0";

    for (i = 0; i < 9; i++)
        arr_sudoku[i] = cadena.substr(i * 9, 9);
    do    {
        cambios = 0;
        for (i = 0; i < 9; i++)
            for (j = 0; j < 9; j++)    {
                //cambio = (cambio || resolver_casilla_facil(i, j));
                cambio = resolver_casilla_facil(i, j);
                cambios += (cambio) ? 1:0;
                terminado = terminado || cambio;
        }
    }    while (cambios > 0);
    tag("resolversu").innerHTML = solucion.join("\\n<br/>");
}


//function resolver_sudoku_facil() {alert("Ok")};
function iniciar_sudoku_blanco()    {
    poner_evento(tag("estudiasu"), "click", estudiar_sudoku);
    poner_evento(tag("resolusu"), "click", resolver_sudoku_facil);
    poner_evento(tag("desmarcar_sudoku"), "click", quitar_marca);
    poner_evento(tag("marcar_sudoku"), "click", poner_marca);

    poner_evento(tag("form_sudo"), "reset", reseteando);
    poner_evento(tag("checksudo"), "click", validar_sudoku);
    poner_evento(tag("resolusudo"), "click", resolver_sudoku);
    //for (i = 1; i <= 16; i++)
    //    poner_evento(tag("sudoku_" + i), "click", nuevo_sudoku);

    sudo = document.forms.form_sudo.inicio.value;
    while(sudo.length < 81) sudo += "0";
    document.forms.form_sudo.inicio.value = sudo;

    for (i = 0; i < 9; i++)    for (j = 0; j < 9; j++)    {
        tag("txt_" + i + "_" + j).appendChild(document.createTextNode(""));
        poner_evento(tag("casilla_" + i + "_" + j), "click", entrada);
    }
}

function entrada() {
    id = this.id;
    coleta = id.substr(8);
    xy = coleta.split("_");
    n_actual = tag("txt_" + coleta).firstChild.data;
    n = prompt("nuevo valor para la casilla [" + xy + "] : ", n_actual);
    if ("0123456789".indexOf(n) != -1)    {
        sudoku = document.forms.form_sudo.inicio.value;
        valores = sudoku.split("");
        posi = parseInt(xy[0]) * 9 + parseInt(xy[1]);
        valores[posi] = n;
        document.forms.form_sudo.inicio.value = valores.join("");
        poner = (n == 0) ? " ":n;
        tag("txt_" + coleta).replaceChild(document.createTextNode(poner), tag("txt_" + coleta).firstChild);
    }
}

function reseteo()    {
    sudo = document.forms.form_sudo.inicio.value;
    while(sudo.length < 81) sudo += "0";
    document.forms.form_sudo.inicio.value = sudo;
}

function reseteando()    {
    setTimeout(reseteo, 100);
    for (i = 0; i < 9; i++)    for (j = 0; j < 9; j++)
        tag("txt_" + i + "_" + j).replaceChild(document.createTextNode(""),
            tag("txt_" + i + "_" + j).firstChild);
}

function entrar_sudoku(cadena) {
    enes = cadena.split("");
    for (var i = 0; i < 9; i++)    for (var j = 0; j < 9; j++)    {
        n = enes.shift();
        poner = ("123456789".indexOf(n) == -1) ? " ": n;
        tag("txt_" + i + "_" + j).replaceChild(document.createTextNode(poner),
            tag("txt_" + i + "_" + j).firstChild);
    }
}

function nuevo_sudoku()    {
    sudo = this.src.split("=")[1];
    document.forms.form_sudo.inicio.value = sudo;
    entrar_sudoku(sudo);
}

svgns = "http://www.w3.org/2000/svg";
xlinkns = "http://www.w3.org/1999/xlink";

function estudiar_casilla(i, j)    {
    s = arr_sudoku;
    fila = s[i];
    valor = fila.charAt(j);
    if ("123456789".indexOf(valor) > -1)    {
        //solucion.push("casilla [" + i + ", " + j + "] resuelta: " + valor);
    }
    else    {
        cadena = "";
        for (_i = 0; _i < 9; _i++)
            if ("123456789".indexOf(fila.charAt(_i)) > -1)
                cadena += fila.charAt(_i);
        for (_i = 0; _i < 9; _i++)
            if ((_i != i) && "123456789".indexOf(s[_i].charAt(j)) > -1)
                if (cadena.indexOf(s[_i].charAt(j)) == -1)
                    cadena += s[_i].charAt(j);
        baseX = 3 * parseInt(i / 3);
        baseY = 3 * parseInt(j / 3);
        for (_i = 0; _i < 3; _i++) for (_j = 0; _j < 3; _j++)
            if (((baseX + _i != i) && (baseY + _j != j)) && "123456789".indexOf(s[baseX + _i].charAt(baseY + _j)) > -1)
                if (cadena.indexOf(s[baseX + _i].charAt(baseY + _j)) == -1)
                cadena += s[baseX + _i].charAt(baseY + _j);
        candidatos = "";
        for (_i = 0; _i < 9; _i++)
            if (cadena.indexOf("123456789".charAt(_i)) == -1)
                candidatos += "123456789".charAt(_i);
        //tag("txt_" + i + "_" + j).setAttributeNS("http://www.w3.org/1999/xlink", "title", candidatos);
        tag("casilla_" + i + "_" + j).setAttributeNS("http://www.w3.org/1999/xlink", "title", "candidatos: " + candidatos);
        c = (candidatos == "") ? "red" : "black";
        solucion.push("<span style='color: " + c + "'>casilla[" + i + ", " + j + "]\nnúmeros: " + cadena + "\ncandidatos: " + candidatos + "</span>");
        return (candidatos != "");
    }
}

function estudiar_sudoku()    {
    solucion = [];
    sin_errores = true;
    cadena = tag("form_sudo").elements.inicio.value;
    if (cadena.length > 81)
        cadena = cadena.substr(0, 81)
    else
        while (cadena.length < 81)
            cadena += "0";

    for (i = 0; i < 9; i++)
        arr_sudoku[i] = cadena.substr(i * 9, 9);

    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++)    {
            if (estudiar_casilla(i, j) == false)
                sin_errores = false;
    }
    if (!sin_errores) alert("El sudoku actual no es válido...");
    tag("resolversu").innerHTML = solucion.join("\\n<br/>");
}

function in_array(n, a)    {
    existe = false;
    for (var i = 0, ti = a.length; i < ti; i++)
        if (a[i] == n)    existe = true;
    return existe;
}

function chequear_sudoku()    {
    repes = [];
    sin_errores = true;
    cadena = tag("form_sudo").elements.inicio.value;
    if (cadena.length > 81)
        cadena = cadena.substr(0, 81)
    else
        while (cadena.length < 81)
            cadena += "0";

    for (i = 0; i < 9; i++)
        arr_sudoku[i] = cadena.substr(i * 9, 9);

    // buscamos repes en filas...
    for (i = 0; i < 9; i++)    {
        n = arr_sudoku[i].charAt(0);
        repes[i] = (n == 0) ? []:[n];
        for (j = 1; j < 9; j++)    {
            m = arr_sudoku[i].charAt(j);
            if (in_array(m, repes[i]))
                sin_errores = false;
            else    if (m != 0)
                repes[i].push(m);
        }
    }

    // Ahora buscamos repes en columnas...
    if (sin_errores)
    for (i = 0; i < 9; i++)    {
        n = arr_sudoku[0].charAt(i);
        repes[i] = (n == 0) ? []:[n];
        for (j = 1; j < 9; j++)    {
            m = arr_sudoku[j].charAt(i);
            if (in_array(m, repes[i]))
                sin_errores = false;
            else    if (m != 0)
                repes[i].push(m);
        }
    }

    // Y por último, buscamos repes en zonas...
    if (sin_errores)    {
        for (i = 0; i < 9; i++)    {
            posi = 27 * parseInt(i / 3) + (3 * (i % 3));
            n = cadena.charAt(posi);
            repes[i] = (n == 0) ? []:[n];
        }
        for (j = 1; j < 9; j++)    for (i = 0; i < 9; i++)    {
            posi = (27 * parseInt(i / 3) + (3 * (i % 3))) + (9 * parseInt(j / 3) + (j % 3));
            m = cadena.charAt(posi);
                if (in_array(m, repes[i]))
                    sin_errores = false;
                else    if (m != 0)
                    repes[i].push(m);
        }
    }
/*
    if (sin_errores)
        for (i = 0; i < 9; i++)    for (j = 0; j < 9; j++)    {
            if (estudiar_casilla(i, j) == false)
                sin_errores = false;
        }
*/
    return sin_errores;
}

function validar_sudoku()    {
    resultado = chequear_sudoku();
    if (resultado)
        alert("sudoku válido")
    else
        alert("sudoku NO válido")
}



function resolver_sudoku()    {

    function exito()    {
        alert("éxito");
        entrar_sudoku(sudoku);
        tag("form_sudo").elements.inicio.value = sudoku;
    }

    function fracaso()    {
        alert("fracaso");
        entrar_sudoku(sudoku);
        tag("form_sudo").elements.inicio.value = sudoku;
    }

    function resolver_casilla(i, j)    {
        cambio = false;
        s = arr_sudoku;
        fila = s[i];
        valor = fila.charAt(j);
        if ("123456789".indexOf(valor) == -1)    {
            cadena = "";
            for (_i = 0; _i < 9; _i++)
                if ("123456789".indexOf(fila.charAt(_i)) > -1)
                    cadena += fila.charAt(_i);
            for (_i = 0; _i < 9; _i++)
                if ((_i != i) && "123456789".indexOf(s[_i].charAt(j)) > -1)
                    if (cadena.indexOf(s[_i].charAt(j)) == -1)
                        cadena += s[_i].charAt(j);
            baseX = 3 * parseInt(i / 3);
            baseY = 3 * parseInt(j / 3);
            for (_i = 0; _i < 3; _i++) for (_j = 0; _j < 3; _j++)
                if (((baseX + _i != i) && (baseY + _j != j)) && "123456789".indexOf(s[baseX + _i].charAt(baseY + _j)) > -1)
                    if (cadena.indexOf(s[baseX + _i].charAt(baseY + _j)) == -1)
                    cadena += s[baseX + _i].charAt(baseY + _j);
            candidatos = [];
            for (_i = 0; _i < 9; _i++)
                if (cadena.indexOf("123456789".charAt(_i)) == -1)
                    candidatos.push("123456789".charAt(_i));
            if (candidatos.length == 1)    {
                n = candidatos[0];
                arr_sudoku[i] = s[i].substr(0, j) + candidatos + s[i].substr(j + 1);
                tag("form_sudo").elements.inicio.value = arr_sudoku.join("");
                tag("txt_" + i + "_" + j).replaceChild(document.createTextNode(n), tag("txt_" + i + "_" + j).firstChild);
                cambio = true;
                _solucion_.push({"x": i, "y": j, "números": candidatos});
            }
            else    {
                _descarte_.push({"x": i, "y": j, "números": candidatos});
            }
        }
        return cambio;
    } // function resolver_casilla(i, j)

    // resolver_sudoku()
    _marcas_ = [];

    terminado = false;
    sudoku = cadena = tag("form_sudo").elements.inicio.value;
    if (cadena.length > 81)
        cadena = cadena.substr(0, 81)
    else
        while (cadena.length < 81)
            cadena += "0";

    for (i = 0; i < 9; i++)
        arr_sudoku[i] = cadena.substr(i * 9, 9);

    do    {
        _solucion_ = [];
        _descarte_ = [];
        do    {
            cambios = 0;
            for (i = 0; i < 9; i++)
                for (j = 0; j < 9; j++)    {
                    cambio = resolver_casilla(i, j);
                    cambios += (cambio) ? 1 : 0;
                    //terminado = terminado || cambio;
            }
        }    while (cambios > 0);
        if (tag("form_sudo").elements.inicio.value.indexOf("0") == -1)    {
            terminado = true;
            exito();
        }
        else    {
            vale = true;
            for (i = 0, total = _descarte_.length; i < total; i++)
                if (_descarte_[i]["números"].length == 0)
                    vale = false;
            if (vale)    {
                _prueba_ = _descarte_.pop();
                _ns_ = _prueba_["números"];
                _n_ = _ns_.pop();
                s = arr_sudoku;
                i = _prueba_.x;
                j = _prueba_.y;
                arr_sudoku[i] = s[i].substr(0, j) + _n_ + s[i].substr(j + 1);
                estado = arr_sudoku.join("");
                tag("form_sudo").elements.inicio.value = estado;
                tag("txt_" + i + "_" + j).replaceChild(document.createTextNode(_n_), tag("txt_" + i + "_" + j).firstChild);
                //alert("probando en (" + i + "," + j + ") valor: " + _n_);
                if (_ns_.length > 0)    {
                    _marcas_.push({"estado": estado, "x": i, "y": j, "números": _ns_});
                    //alert("i: " + i + "\nj: " + j);
                }
            }
            else    {
                if (_marcas_.length > 0)    { // probamos con otro candidato
                    _prueba_ = _marcas_.pop();
                    _ns_ = _prueba_["números"];
                    _n_ = _ns_.pop();
                    estado = _prueba_.estado;
                    for (i = 0; i < 9; i++)
                        arr_sudoku[i] = estado.substr(i * 9, 9);

                    s = arr_sudoku;
                    i = _prueba_.x;
                    j = _prueba_.y;
                    arr_sudoku[i] = s[i].substr(0, j) + _n_ + s[i].substr(j + 1);
                    estado = arr_sudoku.join("");

                    entrar_sudoku(estado);

                    if (_ns_.length > 0)        
                        _marcas_.push({"estado": estado, "x": i, "y": j, "números": _ns_});

                    tag("form_sudo").elements.inicio.value = estado;
                    //terminado = confirm("Sudoku tal vez no válido...\ni: " + i + "\nj: " + j);
                }
                else    {
                    fracaso();
                    terminado = true;            }
                }
            }

    }    while (!terminado);
}

Este código ha sido leído en 15 ocasiones.

Zona de comentarios

Esta extra aún no tiene comentarios.

Evaluación

Valoración de esta página: (extra.script.resolver_sudokus) valor

Valoración evaluar evaluar evaluar evaluar evaluar evaluar evaluar evaluar evaluar evaluar

Respuesta: Zona de mensajes (proceso de evaluación)

Listados: imágenes, categorías, etiquetas, extras | Anuarios: 2010, 2011, 2012, 2013, 2014 | Otros enlaces: buscador