Resolvedor de sudokus

      27 comentarios en Resolvedor de sudokus

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;
}
}

27 pensamiento sobre “Resolvedor de sudokus

  1. Anonymous

    for (int i=superceldacol; i ????

    algo falla??

  2. Makinolo Autor del artículo

    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 🙂

  3. Pepe

    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

  4. Pepe

    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

  5. Makinolo Autor del artículo

    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.

  6. Pepe

    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.

  7. juanca

    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

  8. Makinolo Autor del artículo

    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!

  9. Fillu

    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

  10. Makinolo Autor del artículo

    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?

  11. Francisco

    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??

  12. Makinolo Autor del artículo

    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.

  13. carlos

    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.

  14. Byron Palomeque

    pueden enviarme ejemplo de recursividad para java torres de Hanoi,palindromos etc,etc.

  15. OSVALDO

    tengo problemas para resolver algoritmos de recursividad ayuda emergente

  16. Anónimo

    esta pagina no sirve no esta para nada clara

  17. flavio

    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.

  18. Makinolo Autor del artículo

    & 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.

  19. Lorain

    Yo solo quiero un tonto resolvedor de sudokus q nadie puede poner en Internet ash

Deja una respuesta

Tu dirección de correo electrónico no será publicada.