Thuật toán Sudoku với backtracking - java

Question

Vì vậy, tôi có nhiệm vụ đại học này để giải quyết Sudoku ... Tôi đọc về thuật toán X và thuật toán Khiêu vũ, nhưng họ đã không giúp tôi.

Tôi cần thực hiện việc này với tính năng quay lại. Tôi đã mã hóa cứng một số chỉ mục trong mảng hai chiều với các số ở các vị trí được cung cấp từ Wikipedia (vì vậy tôi chắc chắn rằng nó có thể giải được).

Mã tôi nhận được như sau:

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

Tôi nhận StackOverflow trên

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

có nghĩa là tôi phải ngăn chặn sự đệ quy tại một số điểm, nhưng tôi không thể hình nó ra làm thế nào! Nếu bạn tìm thấy bất kỳ sai lầm nào khác trong hàm solve() - hãy cho tôi biết. Bởi vì tôi không chắc chắn tôi hiểu được "quay lui" điều hoàn toàn ...

Answer 1

Bạn có thể ngừng đệ quy ví dụ nếu bạn theo dõi độ sâu đệ quy hiện hành

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

---

Và nếu bạn tìm thấy bất kỳ sai lầm nào khác trong hàm resolve() - cho tôi biết.

Quá nhiều mã :)

Answer 2

này được khoảng cách tôi đã làm điều này trong quá khứ.

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

tôi đã làm cho nó một cách đơn giản hơn:

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

Tôi không chắc chắn lý do tại sao bạn nói rằng Liên kết Dancing và Thuật toán X là không hữu ích.
Bạn có nghĩa là bạn không thể ánh xạ Sudoku đến một thể hiện của vấn đề Cover chính xác mà Thuật toán X được thiết kế để giải quyết không?
Hoặc đó là một cách tiếp cận quá phức tạp cho những gì bạn cần?

Nếu trường hợp cũ xảy ra, bạn có thể muốn xem: A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm. Nó khá rõ ràng và giải thích cũng là lý do đằng sau.

N.B. Thuật toán X là một thuật toán backtracking vì vậy, nếu đó là yêu cầu duy nhất của bạn, bạn chắc chắn có thể sử dụng phương pháp này.

Hy vọng điều này có thể hữu ích.