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是一种回溯算法，所以如果这是您唯一的要求，您绝对可以使用这种方法。

希望这可以帮助。