Sudoku-Algorithmus mit Backtracking - Java

Question

So habe ich diese Universität Aufgabe, Sudoku zu lösen ... Ich las über Algorithmus X und Tanzalgorithmus, aber sie haben mir nicht geholfen.

Ich muss es mit Backtracking machen. Ich habe einige der Indizes in dem zweidimensionalen Array mit Zahlen an Orten, die aus Wikipedia kommen, fest programmiert (also bin ich sicher, dass es lösbar ist).

Der Code, den ich habe ist folgendes:

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

Ich bin immer auf Stackoverflow

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

was bedeutet, dass ich die Rekursion an einem gewissen Punkt zu stoppen, aber ich kann nicht verstehen es raus wie! Wenn Sie weitere Fehler in der solve() Funktion finden - lassen Sie es mich wissen. Denn ich bin nicht sicher, ob ich die „Backtracking“ Ding ganz verstehen ...

Answer 1

Sie Rekursion zum Beispiel stoppen können, wenn Sie den Überblick über die aktuelle Rekursionstiefe

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

---

Und wenn Sie halten Finden Sie weitere Fehler in der Funktion solve() - lassen Sie es mich wissen.

Zu viel Code :)

Answer 2

Das ist in etwa so, wie ich habe dies in der Vergangenheit getan.

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

Ich machte es auf einfachere Art und Weise:

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

Ich bin nicht sicher, warum Sie sagen, dass Tanzen Links and Algorithm X nicht nützlich waren.
Sie meinen, dass Sie Sudoku nicht einer Instanz des Exact Cover-Problems zuordnen konnten, das mit Algorithmus X gelöst werden soll?
Oder dass es ein zu komplizierter Ansatz für das ist, was Sie brauchen ??

Wenn das erste der Fall ist, möchten Sie vielleicht sehen: A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm. Es ist ziemlich klar und erklärt auch die Begründung.

N.B. Algorithmus X ist ein Backtracking-Algorithmus. Wenn dies Ihre einzige Anforderung ist, können Sie diesen Ansatz definitiv verwenden.

Hoffe, das kann helfen.