Ultimamente por
Microsiervos publican mucho un tipo de crucigrama numerico. El Sodoku.
Empezó anunciándose en este articulo y ya ha tomado fama en la web:
Han hecho
consejos1 ,
consejos2,
consejos3, y
consejos4 para resolverlos.
La explicación de como se fabrican es facil para un humano. Para una maquina... He intentado hacer uno en javascript, pero me es algo complicado.
Cita: Rellena la matriz de modo que:
cada fila,
cada columna
y cada caja de 3x3
contenga los números del 1 al 9.
Lo de los cuadrantes de 3x3 ya lo he pasado por alto, y ya me encuentro con dificultades. Es decir, mi script es solo para colocar numeros en un tablero. El numero en la casilla de columna Y y fila X no puede estar repetido ni en la columna Y, ni en la fila X. Tan sencillo como eso.
El script funciona, salvo en ciertas ocasiones, que se encuentra con casillas que no tiene la posibilidad de poner ningun numero.
El programa va fila por fila, y dentro de cada fila poniendo un numero en cada celda. Cuando va a empezar con la celda, tiene todas las posibilidades (si hablamos de un sodoku de 10x10 tiene las posibilidades 0,1,2,3,4,5,6,7,8,9). A partir de aqui elimina las no validas: Elimina todos los numeros que se encuentren en su fila, y todos los numeros que se encuentren en su columna. De manera que ya las posibilidades son por ejemplo 3,4,5,7,9. Aquí se escoge aleatoriamente un numero, se coloca y se pasa a la siguiente celda de la fila. Cuando acabemos con la fila, escogeremos otra fila para trabajar.
Hay ocasiones que el programa anula Todas las posibilidades, no puede poner numero, y entonces pone un '-1'.
Tengo la duda de qué hacer con esos -1. He pensado en intercambiar celdas, teniendo cuidado de no estropear nada pero... complicado.
El script es este:
Código PHP:
<style>
.fila {
height:20px;
clear:both;
}
.celda {
border: solid 1px black;
text-align:center;
width: 20px; height:20px;
font-size:10px;
font-family:tahoma;
float:left;
margin:2px;
}
</style>
Código PHP:
//dimension del Sodoku
var X=9;
//creamos el Sodoku rellenandolo con -1 todas sus casillas
var sodoku=new Array(X);
for(var a=0;a<X;a++) {
sodoku[a]=new Array(X);
for(var b=0; b<X; b++)
sodoku[a][b]=-1;
}
//inicializamos nums_posibles y filas. Serviran para escoger aleatoriamente las filas y los numeros
var nums_posibles=new Array(X);
for(var a=0; a<X; a++) nums_posibles[a]=a;
var filas=new Array(X);
for(var a=0; a<X; a++) filas[a]=a;
//busca un numero dentro de un array de numero
// y devuelve su indice. Si no lo encuentra devuelve -1
function numAt(arr,num,excepto) {
for(var a=0; a<arr.length; a++)
if( arr[a]==num )
return a;
return -1;
}
//sin mas, mostrarlo por pantalla
function imprime_sodoku() {
document.write("<br>");
for(var a=0;a<X;a++) {
document.write('<div class="fila">');
for(var b=0;b<X;b++) {
document.write('<div class="celda" id="sodoku_'+a+'_'+b+'">'+sodoku[a][b]+'</div>');
}
document.write('</div>');
}
}
// EMPEZAMOS A RELLENAR
// recorreremos cada fila aleatoriamente, y la eliminaremos de la lista hasta que no queden filas:
while(filas.length>0) {
//Escogemos la fila actual: indice aleatorio de 'filas'
var i= parseInt(Math.random()*filas.length);
var fila=filas[i];
//eliminamos la fila de la lista para que no se repita
filas.splice(i,1);
//en cada celda de la fila actual coloquemos un numero, aleatorio de una lista, que no se encuentre ni en su fila ni en su columna
for(var a=0;a<X;a++) { //por cada celda
//hacemos una copia de nums_posibles para ir quitandole elementos
var nums=new Array(X);
for(var b=0;b<X;b++) nums[b]=nums_posibles[b];
//quitemosle a nums todos los elementos de esta misma FILA (son todos los de su izquierda, a la dcha no hay elementos)
for(var b=0; b<a; b++) {
//indice del numero que vamos mirando (celda a celda) en nums
var esta=numAt(nums, sodoku[fila][b]);
//si esta lo borramos de la lista nums
if(esta!=-1)
nums.splice(esta,1);
}
//quitemosle a nums todos los elementos de esta misma COLUMNA
for(var b=0; b<X; b++) {
//indice del numero que vamos mirando (celda a celda) en nums
var esta=numAt(nums, sodoku[b][a]);
//si esta lo borramos de la lista nums
if(esta!=-1)
nums.splice(esta,1);
}
//ahora en nums estan todos los numeros que realmente se podrian poner. Escogemos uno al azar:
var num= nums[ parseInt(Math.random()*nums.length) ];
if(num==undefined) num=-1; //es una coincidencia, un error de probabilidad que debemos paliar.
sodoku[fila][a]=num;
}
}
imprime_sodoku();
function rojo_los_menosUno() {
for(var a=0;a<X;a++) {
for(var b=0;b<X;b++) {
if(sodoku[a][b]==-1)
document.getElementById("sodoku_"+a+"_"+b).style.backgroundColor="red";
}
}
}
rojo_los_menosUno();
Lo que hago al final con rojo_los_menosUno(), es colorear los '-1' para que se vean mejor, simplemente.
Está comentado, si hay alguna duda, posteadla.
¿Alguna idea para los '-1'? Y, mas importante, ¿Alguna idea para los cuadrantes de 3x3?
Es complicado... ¿verdad?
