para - Solucionador de Sudoku en Java, usando retroceso y recursión

solucionador de sudoku java

Question

Estoy programando un solucionador de Sudoku en Java para una grilla de 9x9.

Tengo métodos para:

• imprimiendo la grilla

• inicializando el tablero con valores dados

• prueba de conflictos (si el mismo número está en la misma línea o subred 3x3)

• un método para colocar los dígitos, uno por uno, que requiere más trabajo.

Antes de entrar en detalles con ese método, tenga en cuenta que tengo que recurrir a la recursión para resolverlo, así como hacer un seguimiento (mire el applet aquí como un ejemplo http://www.heimetli.ch/ffh/simplifiedsudoku.html )

Además, estoy resolviendo este Sudoku moviéndome verticalmente hacia abajo, comenzando desde la parte superior izquierda, a través de la primera columna, y luego a través de la segunda columna, etc.

Hasta ahora, tengo lo siguiente:

public boolean placeNumber(int column){

    if (column == SUDOKU_SIZE){  // we have went through all the columns, game is over

        return true;

    }

    else
    {
        int row=0;  //takes you to the top of the row each time

        while (row < SUDOKU_SIZE)    loops through the column downwards, one by one
        {

            if (puzzle[row][column]==0){  //skips any entries already in there (the given values)

                puzzle[row][column]=1;   //starts with one

                while(conflictsTest(row,column)){   //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number

                    puzzle[row][column] += 1;  

                }


           //BACK TRACKING 

                placeNumber(column);      //recursive call

            }
            else{
              row++;                  // row already has a number given, so skip it
            }
        }

        column++;              // move on to second column
        placeNumber(column);

    }
    return false; // no solutions to this puzzle
}

Donde etiqueté BACKTRACKING es donde creo que debe ir el resto de mi código.

Pensé en algo como:

• si el valor es 10, restablezca ese valor a cero, regrese una fila e incremente ese valor en 1

Esa ''estrategia'' de retroceso no funciona exactamente por varias razones:

1. ¿Y si la fila anterior era un valor dado? (aka, se supone que no debo incrementarla ni tocarla, sino volver al último valor que coloqué allí)

2. ¿Y si el valor anterior fuera 9. y si lo aumentara en 1, ahora estamos en 10, lo que no funcionará.

¿Puede alguien ayudarme?

Answer 1

No sé cómo vas a resolver el sudoku, pero incluso si usas el método de fuerza bruta (y me suena a lo que describes), debes considerar que tu estructura de datos no es apropiada.

Con eso me refiero a que cada celda no debe ser solo un número, sino un conjunto de números (que posiblemente se puedan colocar allí).

Por lo tanto, los números dados se representarán como conjuntos simples, mientras que los vacíos se pueden inicializar con {1,2,3,4,5,6,7,8,9}. Y luego, el objetivo es reducir las células no singleton hasta que todas las células sean singletons.

(Tenga en cuenta que, mientras resuelve un sudoku con lápiz y papel, a menudo escribe números pequeños en las celdas en blanco para realizar un seguimiento de los números posibles allí, siempre que lo haya resuelto).

Y luego, cuando "intenta el próximo número", toma el siguiente número del conjunto. Las celdas dadas no tienen el siguiente número, por lo que no puedes cambiarlas. De esta manera, las dificultades que describes desaparecen (un poco, al menos).

------ EDITAR, DESPUÉS DE HABER APRENDIDO QUE SE NECESITA FUERZA BRUTA.

Tu maestro obviamente quiere enseñarte las maravillas de la recursión. ¡Muy bien!

En ese caso, solo necesitamos saber qué celdas se dan y cuáles no.

Una manera particularmente fácil que podría usarse aquí es colocar un 0 en cualquier celda no dada, dado que las celdas dadas son por definición una de 1,2,3,4,5,6,7,8,9.

Ahora pensemos en cómo hacer funcionar la fuerza bruta recursiva.

Tenemos el objetivo de resolver un sudoku con n celdas vacías. Si tuviéramos una función que resolvería un sudoku con n-1 celdas vacías (o señal de que no se puede resolver), entonces esta tarea sería fácil:

let c be some empty cell.
let f be the function that solves a sudoku with one empty cell less.
for i in 1..9
   check if i can be placed in c without conflict
   if not continue with next i
   place i in c
   if f() == SOLVED then return SOLVED
return NOTSOLVABLE

Este pseudo código selecciona una celda vacía y luego prueba todos los números que se ajustan allí. Debido a que un sudoku tiene, por definición, solo una solución única, solo existen los siguientes casos:

• Elegimos el número correcto. Entonces f () encontrará el resto de la solución y regresará SOLUCIONADO.
• elegimos un número equivocado: f () indicará que el sudoku no se puede resolver con ese número equivocado en nuestra celda.
• revisamos todos los números, pero nadie estaba en lo cierto: entonces nosotros mismos tenemos un sudoku insoluble y le indicamos esto a nuestro interlocutor.

Huelga decir que el algoritmo se basa en la suposición de que solo colocamos números que no están en conflicto con el estado actual. Por ejemplo, no colocamos un 9 allí cuando en la misma fila, columna o recuadro ya hay un 9 .

Si ahora pensamos en cómo funciona nuestra misteriosa pero desconocida función f() , ¡resultará casi igual a lo que ya tenemos!
El único caso que aún no hemos considerado es un sudoku con 0 celdas vacías. Esto significa que, si descubrimos que no hay más celdas vacías, sabemos que acabamos de resolver el sudoku y devolvemos SOLO SOLUCIONADO.

Este es el truco común cuando se escribe una función recursiva que se supone que resuelve un problema. Estamos escribiendo resolve (), y sabemos que el problema se puede resolver en absoluto. Por lo tanto, ya podemos usar la función que estamos escribiendo siempre que nos aseguremos de que con cada recursión, el problema de alguna manera se acerque a la solución. Al final, llegamos al llamado caso base, donde podemos dar la solución sin recurrencia adicional.

En nuestro caso, sabemos que Sudoku es solvente, además, sabemos que tiene exactamente una solución. Al colocar una pieza en una celda vacía, nos acercamos a la solución (o al diagnóstico de que no hay ninguna) y proporcionamos el problema nuevo y más pequeño recursivamente a la función que estamos escribiendo. El caso base es el "Sudoku con 0 celdas vacías", que en realidad es la solución .

(Las cosas se complican un poco si hay muchas soluciones posibles, pero las dejamos para la próxima lección).

Answer 2

Verificaría cada celda y regresaría a un paso de recursión si no se puede encontrar una solución.

Más detalladamente: vaya a la celda siguiente, si el valor es x == 0, verifique si x + 1 sería válido, si es verdadero, vaya a la siguiente celda llamando al método recursivamente con la siguiente celda posible. Si el número no es válido, marque x + 2, etc. si no hay ningún número válido, devuelva falso y repita el paso x + 1 en la llamada anterior. Si tocas una celda con un número dentro, no llames a la recursividad, sino que pasas directamente a la siguiente, por lo tanto, no necesitas marcar ninguna celda previamente ingresada.

Pseudo código:

fillcell cell
 while cell is not 0
  cell = next cell
 while cell value < 10
  increase cell value by one
  if cell is valid 
    if fillcell next cell is true
      return true
return false

No estoy seguro de si esto es correcto, pero debería mostrar la idea.

Answer 3

algunas ideas que pueden ser útiles (sobre recursividad y retroceso)

//some attributes you might need for storing e.g. the configuration to track back to.

boolean legal(Configuration configuration) {

}

int partSolution(Configuration configuration) {
  if (legal(configuration))
    return partSolution(nextConfiguration())
  else
    return partSolution(previousConfiguration())    
}

Configuration nextConfiguration() {
 //based on the current configuration and the previous tried ones,
 //return the next possible configuration:
 //next number to enter, next cell to visit
}

Configuration previousConfiguration() {
 //backtrack
}

solve () {
  call partSolution with start configuration while partSolution < 9x9
}

escriba una clase de configuración que contenga la cuadrícula con los números ingresados ​​y algunos otros atributos como el tamaño y # números ingresados ​​y piense sobre qué más se necesita

Answer 4

sugiero pasar tanto la fila actual como la columna al método recursivo, luego encontrar todos los números permitidos para esa celda, para cada número permitido recursivamente llamar al método para la siguiente columna (o la siguiente fila si en la última columna) y deshacer el movimiento si conduce a una pista muerta

public boolean fillCell(int r, int c) {
    if last row and last cell {
        //report success
        return true
    }
    for i 1 to 9 {
        if can place i on r, c {
            board[r][c] = i
            if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move
                board[r][c] = 0
            }
            /*
            else {
                return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also
            }
            */

        }
    }
    return false        
}

Answer 5

En primer lugar , una sugerencia para la optimización: mientras compruebas si el número que vas a colocar en una celda ya está presente en la misma fila, columna o minigrid, no tienes que ejecutar un bucle o algo así. Puede realizar una comprobación instantánea por indexación de matriz.

Considere 3 matrices dimensionales dobles booleanas de 9x9:

boolean row[9][9], col[9][9], minigrid[9][9]

Utilizaremos el primer conjunto para verificar si hay un número presente en la misma fila, el segundo para verificar si hay un número presente en la misma columna y el tercero para la mini cuadrícula.

Supongamos que quiere poner un número n en su celda i , j . Verificará si la fila [i] [n-1] es verdadera. Si es así, entonces ^la fila ya contiene n. De forma similar, comprobará si col [j] [n-1] y minigrid [gridnum] [n-1] es verdadero.

Aquí gridnum es el índice de la mini cuadrícula, donde se encuentra la celda en la que desea insertar un número. Para calcular el número de la mini cuadrícula para la celda i, j , divida i & j por 3, multiplique la parte integral de former por 3, y agréguelo a la parte integral de este último.

Así es como se ve:

gridnum = (i/3)*3 + j/3

Al observar los valores de i / 3 y j / 3 para todos los i y j, obtendrá una idea de cómo funciona esto. Además, si coloca un número en una celda, actualice las matrices también. Ej fila [i] [n-1] = verdadero

Si hay una parte que no comprende, publique un comentario y editaré mi respuesta para explicarlo.

En segundo lugar , usar recursividad y retroceso para resolver esto es bastante fácil.

boolean F( i, j) // invoke this function with i = j = 0
{
If i > 8: return true // solved

for n in 1..9
 {
 check if n exists in row, column, or mini grid by the method I described

 if it does: pass ( skip this iteration )

 if it doesn''t
  {
   grid[i][j] = n
   update row[][], col[][], minigrid[][]

   if F( if j is 8 then i+1 else i, if j is 8 then 0 else j+1 ) return true // solved
  }
 }
 return false // no number could be entered in cell i,j
}