Sudoku algorithm with backtracking - java

Question

所以我有這個大學的任務來解決Sudoku ...我讀了關於算法X和跳舞算法，但他們沒有幫助我。

我需要使它回溯。我用二維數組中的一些索引對Wikipedia提供的地方進行了硬編碼（所以我相信它是可以解決的）。

我得到的代碼如下：

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

我正在上

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

這意味着我必須停止在某一點上遞歸的StackOverflow，但我想不通它如何！ 如果您在solve()功能中發現任何其他錯誤 - 請告訴我。因爲我不知道我完全理解的「回溯」的事情......

Answer 1

如果保持目前的遞歸深度

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

---

如果你的軌跡，可以停止例如遞歸在solve（）函數中發現任何其他錯誤 - 讓我知道。

太多的代碼:)

Answer 2

這大致是這樣，我已經在過去做到了這一點。

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

我在一個更簡單的方式做它：

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

我不知道爲什麼你說，跳舞的鏈接和算法X是沒有用的。
您的意思是說您無法將Sudoku映射到算法X旨在解決的Exact Cover問題的實例？
或者這是一個太複雜的方法，你需要什麼？

如果前者是這種情況，您可能需要查看：A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm。這很清楚，也解釋了背後的原因。

N.B.算法X是一種回溯算法，所以如果這是您唯一的要求，您絕對可以使用這種方法。

希望這可以幫助。