El otro día me invitaron a una fiesta: la fiesta del sudoku.
Ya había oido hablar del pasatiempo del verano y tal, pero nunca me había molestado en examinar el dichoso juego. Hasta el otro día.
Aparte de la fiesta en si, que la verdad estuvo bastante cachonda (gracias a la anfitriona Ana de Benavente ;-), la invitación contenía en su reverso un Sudoku que había que resolver. Tuve que buscar las reglas del juego por internet y al verlo no pude menos que recordad mis viejos tiempos de la universidad, y aquellos manidos ejemplos de problemas de recursividad que se estudiaban en algoritmia.
El sudoku puede parecer entretenido a algunos, a mi me pareció un problema de examen de algoritmia :), así que me puse a resolverlo.
Las reglas:
- El numero colocado no puede estar repetido en ninguna celda de la misma columna
- El numero colocado no puede estar repetido en ninguna celda de la misma fila
- El numero no puede estar repetido en ninguna celda del mismo grupo de 3×3
Método elegido :
Fuerza bruta, recursividad con Backtracking, cortando las ramas que no llevan a soluciones.
Me arranqué el Intellij Idea de JetBrains, mi entorno de programación en Java, y empezé a engrasar mis oxidados conceptos de recursividad hasta que di con el algoritmo que resuelve cualquier Sudoku que tenga solución.
Esta muy basto, no tiene ni un mal interfaz de usuario, pero funciona :). Para el que lo quiera, aqui está.
public class Sudoku
{
private static int[][] tablero;
private static int pasadas=0;
public static void main(String[] args)
{
tablero = new int[11][11];
// Inicializacion del tablero
for (int col=0; col<11; col++)
for (int fil=0; fil<11 ; fil++)
tablero[fil][col] = 0;
// Colocación de las celdas fijas, a rellenar por el interesado
tablero[1][1] = 1;
tablero[2][2] = 3;
tablero[4][2] = 2;
tablero[6][2] = 7;
tablero[7][1] = 2;
tablero[7][2] = 9;
tablero[7][3] = 5;
tablero[8][3] = 4;
tablero[2][4] = 8;
tablero[1][5] = 6;
tablero[2][5] = 7;
tablero[3][5] = 3;
tablero[2][6] = 9;
tablero[4][4] = 9;
tablero[5][4] = 3;
tablero[6][4] = 6;
tablero[5][5] = 4;
tablero[5][6] = 8;
tablero[1][7] = 8;
tablero[3][7] = 9;
tablero[5][7] = 7;
tablero[4][8] = 8;
tablero[9][7] = 5;
tablero[9][8] = 1;
tablero[8][9] = 2;
tablero[9][9] = 4;
pintaTablero();
resuelve(1,1);
pintaTablero();
System.out.println("Resuelto en "+pasadas+" pasadas");
}
public static void pintaTablero()
{
for (int col=1; col<10; col++)
{
if ((col-1)%3==0)
System.out.println("======================================");
else
System.out.println("--------------------------------------");
for (int fil=1; fil<10 ; fil++)
{
if ((fil-1)%3==0)
System.out.print(" H ");
else
System.out.print(" | ");
System.out.print(tablero[fil][col]);
}
System.out.print(" | ");
System.out.println();
}
System.out.println("*********************************");
}
private static boolean resuelve(int fil, int col)
{
boolean resuelto = false,celdafija=false;
int num = 1;
pasadas++;
if (tablero[fil][col] !=0)
{
celdafija = true;
num=9;
}
while (!resuelto && num<10)
{
// Si la celda no es fija
if (!celdafija)
tablero[fil][col] = num;
if (celdaValida(fil,col))
{
if (fil==9 && col==9)
resuelto = true;
else if (fil<9)
resuelto = resuelve(fil+1, col);
else if(fil==9)
resuelto = resuelve(1, col+1);
}
num++;
}
if (!resuelto && !celdafija)
tablero[fil][col] = 0;
return resuelto;
}
private static boolean celdaValida(int fil, int col)
{
// El numero no puede estar repetido en ninguna celda de la misma columna
for (int i=1; i<10; i++)
if (fil!=i && tablero[fil][col] == tablero[i][col] )
return false;
// El numero no puede estar repetido en ninguna celda de la misma fila
for (int i=1; i<10; i++)
if (col!=i && tablero[fil][col] == tablero[fil][i] )
return false;
// El numero no puede estar repetido en ninguna celda de la misma celda de 3x3
int superceldacol = (int)(Math.floor((col-1)/3)3)+1,
superceldafil = (int)(Math.floor((fil-1)/3)3)+1;
for (int i=superceldacol; i<superceldacol +3; i++)
for (int j=superceldafil; j<superceldafil+3; j++)
if (col!=i && fil!=j && tablero[fil][col] == tablero[j][i] )
return false;
return true;
}
}
for (int i=superceldacol; i ????
algo falla??
Tienes razon, el WordPress esta muy bien, pero de vez en cuando comete tropelías como esta. Obviamente le falta un trozo, por culpa de los < >, tambien le pasa al otro bucle de abajo. En cuanto pueda lo arreglo 🙂
Haciendo pruebas con estas datos no me funciona, me pinta el tablero igual que el inicial.
tablero[0][4] = 5;
tablero[0][7] = 2;
tablero[1][2] = 3;
tablero[1][4] = 9;
tablero[1][6] = 8;
tablero[2][1] = 4;
tablero[2][5] = 7;
tablero[2][8] = 9;
tablero[3][2] = 1;
tablero[3][3] = 5;
tablero[3][4] = 2;
tablero[4][0] = 9;
tablero[4][3] = 3;
tablero[4][5] = 8;
tablero[4][8] = 4;
tablero[5][4] = 7;
tablero[5][5] = 6;
tablero[5][6] = 3;
tablero[6][0] = 1;
tablero[6][3] = 2;
tablero[6][7] = 6;
tablero[7][2] = 5;
tablero[7][4] = 3;
tablero[7][6] = 2;
tablero[8][1] = 7;
tablero[8][4] = 8;
Saludos
El resualtado tendria que ser
7 9 6 8 5 3 4 2 1
5 1 3 4 9 2 8 7 6
2 4 8 1 6 7 5 3 9
6 3 1 5 2 4 9 8 7
9 2 7 3 1 8 6 5 4
8 5 4 9 7 6 3 1 2
1 8 9 2 4 5 7 6 3
4 6 5 7 3 1 2 9 8
3 7 2 6 8 9 1 4 5
El problema está en que empiezas el array en 0. Para poder hacer el algoritmo mas sencillo el array que contiene el sudoku tiene un “margen” por lo que la fila 0 y la columna 0 deben estar vacias, al igual que la columna y fila 10. Si te das cuenta el tablero es de 11×11 (de 0 a 10) y es precisamente para poder dejar ese margen de filas a 0.
Simplemente sumale 1 a todos los indices de tu array inicial y debería funcionar.
Perfecto, muy eficiente tu algoritmo.
En pintaTablero he intercambiado las columnas y las filas ya que me las pintaba al contrario.
Enhorabuena, gracias por tus ideas.
tenemos de clase de programacion un problema a resolver, tenemos que rellenar un array de dos dimensiones, pero te lo pregunto para un array simple:
tenemos que rellenar usando recursividad un array, por ejemplo de tamnaño 4, con numeros del 1 al 4, y tenemos que conseguir todas las convinaciones posibles sin que se repitan los numeros, habiendo hecho el programa de arriba, para ti esto será una tontería, haber si me dices como se hace, gracias
No expones demasiado claramente el problema, pero entiendo que los numeros no se pueden repetir en las celdas adyacentes, norte, sur, este y oeste.
Si ese es el problema se puede resolver con este mismo algoritmo, solo tienes que cambiar el tamaño del array para adaptarlo al tamaño que necesitas y reprogramar el método celdaValida() para que cumpla la regla que necesitas, algo como
if (tablero[fil][col] != tablero[fil+1][col] && tablero[fil][col] != tablero[fil][col+1] && tablero[fil][col] != tablero[fil-1][col] && tablero[fil][col] != tablero[fil][col-1])
return true;
else
return false;
Aparte de que el algoritmo no es ni por asomo el mas eficiente para resolver ese problema, por supuesto no voy a escribir ni probar la solución, eso te lo dejo a ti, que el dia del examen yo no estaré alli para ayudarte 😀
Un saludo y suerte!
Me parece un trabajo buenisimo tu sudoku. me gustaria q me ayudaras xq yo tengo q hacer uno en caml, tengo hechas un monton de funciones basicas y no se seguir.
Agradeceria cualquier apoyo. gracias
Lo cierto es que es la primera vez que oigo hablar del caml, así que no creo que pueda ser de gran ayuda.
He estado echando una ojeada al lenguaje y asi a primera vista no le he apreciado ninguna ventaja espectacular sobre mi querido java. Quizas es que simplemente soy demasiado viejo como para apreciar las bondades del cambio :D.
¿con que proposito principal lo usas? ¿es solo para ámbito academico? ¿hemos cambiado el ADA y el Pascal por el CAML?
Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 11
at sudoku.main(sudoku.java:13)
Press any key to continue…
Hola baje el codigo… y lo compile y despues de sacarle todos los errores que obtuve al “copiar y pegar”, lo pude ejecutar pero me aparece este error…
como lo arreglo??
La linea 13 es la de inicialización, no deberia tener ningun problema al no ser que no hayas inicializado correctamente a 11 el array, si pones exactamente lo que has escrito lo te podré ayudar mejor. Mandame el codigo makinolo arroba gmail.com para que vea que te falla.
no compila me sale estos errores
——————–Configuration: sudoku – JDK version 1.6.0 – ——————–
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:9: not a statement
for (int col=0; col<11; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:9: ‘)’ expected
for (int col=0; col<11; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:9: ‘;’ expected
for (int col=0; col<11; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:46: not a statement
for (int col=1; col<10; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:46: ‘)’ expected
for (int col=1; col<10; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:46: ‘;’ expected
for (int col=1; col<10; col++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:75: ‘)’ expected
while (!resuelto && num<10)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:75: not a statement
while (!resuelto && num<10)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:75: ‘;’ expected
while (!resuelto && num<10)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:98: not a statement
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:98: ‘)’ expected
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:98: ‘;’ expected
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:102: not a statement
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:102: ‘)’ expected
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:102: ‘;’ expected
for (int i=1; i<10; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:108: not a statement
for (int i=superceldacol; i<superceldacol +3; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:108: ‘)’ expected
for (int i=superceldacol; i<superceldacol +3; i++)
^
C:\Documents and Settings\Administrador\Escritorio\sudoku\sudoku\src\Sudoku.java:108: ‘;’ expected
for (int i=superceldacol; i<superceldacol +3; i++)
^
18 errors
Process completed.
pueden enviarme ejemplo de recursividad para java torres de Hanoi,palindromos etc,etc.
proyecto de sudoku
COMO SE PUEDE PASAR A pascaal!!!???
QUE ONDA
tengo problemas para resolver algoritmos de recursividad ayuda emergente
esta pagina no sirve no esta para nada clara
alguien puede arreglar el codigo por favor ya q me marca mucchos errores q no puedo corregir
mi mail es damianminniti@hotmail.com
porfa lo necesito
Excelente trabajo, muchas gracias Makinolo. les cuento que el operador < me estaba sacando error y lo cambie por < resultado cero errores y ejecucion perfecta, ahhh tbn inverti fil por col en pintaTablero.
tilin de mono
en el primer for q significa lt
& l t ; es el sÃmbolo “lower than” osea “menor que” es decir “<". El software que uso para publicar el blog lo cambia de manera automatica por seguridad, no puedo ponerlo correctamente.
Yo solo quiero un tonto resolvedor de sudokus q nadie puede poner en Internet ash
: /
Graicas