Algoritmo di Sudoku con backtracking - java

Question

Quindi ho questo incarico universitario per risolvere il Sudoku ... Ho letto dell'algoritmo X e dell'algoritmo Ballare, ma non mi hanno aiutato.

Ho bisogno di farlo con il backtracking. Ho hard-coded alcuni degli indici nella matrice bidimensionale con i numeri sui posti dati da Wikipedia (quindi sono sicuro che sia risolvibile).

Il codice ho ottenuto è il seguente:

public void solveSudoku(int row, int col) 
    { 
     // clears the temporary storage array that is use to check if there are 
     // dublicates on the row/col 
     for (int k = 0; k < 9; k++) 
     { 
     dublicates[k] = 0; 
     } 
     // checks if the index is free and changes the input number by looping 
     // until suitable 
     if (available(row, col)) 
     { 
     for (int i = 1; i < 10; i++) 
     { 
      if (checkIfDublicates(i) == true) 
      { 
       board[row][col] = i; 
       if (row == 8) 
        solveSudoku(0, col + 1); 
       else if (col == 8) 
        solveSudoku(row + 1, 0); 
       else 
        solveSudoku(row, col + 1); 

       board[row][col] = 0; 
      } 
     } 
     } 
     // goes to the next row/col 
     else 
     { 
     if (row == 8) 
      solveSudoku(0, col + 1); 
     else if (col == 8) 
      solveSudoku(row + 1, 0); 
     else 
      solveSudoku(row, col + 1); 
     } 
    } 

    /** 
    * Checks if the spot on the certain row-col index is free of element 
    * 
    * @param row 
    * @param col 
    * @return 
    */ 
    private boolean available(int row, int col) 
    { 
     if (board[row][col] != 0) 
     return false; 
     else 
     return true; 
    } 

    /** 
    * Checks if the number given is not already used in this row/col 
    * 
    * @param numberToCheck 
    * @return 
    */ 
    private boolean checkIfDublicates(int numberToCheck) 
    { 
     boolean temp = true; 
     for (int i = 0; i < dublicates.length; i++) 
     { 
     if (numberToCheck == dublicates[i]) 
     { 
      temp = false; 
      return false; 
     } 
     else if (dublicates[i] == 0) 
     { 
      dublicates[i] = numberToCheck; 
      temp = true; 
      return true; 
     } 
     } 
     return temp; 
    } 

sto ottenendo StackOverflow su

// goes to the next row/col 
      else 
      { 
      if (row == 8) 
       solveSudoku(0, col + 1); 
      else if (col == 8) 
       solveSudoku(row + 1, 0); 
      else 
       solveSudoku(row, col + 1); 
      } 

il che significa che mi devo fermare la ricorsione ad un certo punto, ma non riesco a capire fuori come! Se trovi altri errori nella funzione solve() - fammi sapere. Perché io non sono sicuro di aver capito la cosa "backtracking" del tutto ...

Answer 1

si può fermare la ricorsione per esempio se tenere traccia della profondità di ricorsione corrente

public void solveSudoku(int row, int col, int recursionDepth) { 
    // get out of here if too much 
    if (recursionDepth > 15) return; 

    // regular code... 
    // at some point call self with increased depth 
    solveSudoku(0, col + 1, recursionDepth + 1); 
} 

---

E se si trova altri errori nella funzione solve() - fammi sapere.

troppo codice :)

Answer 2

Questo è più o meno il modo in cui ho fatto questo in passato.

Whenever all the definite moves have been taken and there is a choice of equally good next moves: 
    copy your grid data structure and push it onto a stack. 
    take the first candidate move and continue solving recursively 
    Whereever you get stuck: 
     pop the saved grid off the stack 
     take the next candidate move. 

Answer 3

ho fatta in un modo più semplice:

public void solve(int row, int col) 
    { 
     if (row > 8) 
     { 
     printBoard(); 
     System.out.println(); 
     return; 
     } 
     if (board[row][col] != 0) 
     { 
     if (col < 8) 
      solve(row, col + 1); 
     else 
      solve(row + 1, 0); 
     } 
     else 
     { 
     for (int i = 0; i < 10; i++) 
      if (checkRow(row, i) && checkCol(col, i)) 
        //&& checkSquare(row, col, i)) 
      { 
       board[row][col] = i; 
       if (col < 8) 
        solve(row, col + 1); 
       else 
        solve(row + 1, 0); 
      } 
     board[row][col] = 0; 
     } 
    } 

    private boolean checkRow(int row, int numberToCheck) 
    { 
     for (int i = 0; i < 9; i++) 
     if (board[row][i] == numberToCheck) 
      return false; 

     return true; 
    } 

    private boolean checkCol(int col, int numberToCheck) 
    { 
     for (int i = 0; i < 9; i++) 
     if (board[i][col] == numberToCheck) 
      return false; 

     return true; 
    } 

Answer 4

io non sono sicuro perché dici che la danza Link e Algoritmo X non erano utili.
Intendi dire che non sei riuscito a mappare Sudoku su un'istanza del problema Exact Cover che Algorithm X è stato progettato per risolvere?
O che è un approccio troppo complicato per quello che ti serve ??

Se il primo è il caso, si potrebbe voler guardare: A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm. E 'abbastanza chiaro e spiega anche il ragionamento dietro.

N.B. Algorithm X è un algoritmo di backtracking quindi, se questo è il tuo unico requisito, puoi sicuramente usare questo approccio.

Spero che questo possa essere d'aiuto.