Java中的数独求解器，使用回溯和递归
2022-09-01 19:31:03
我正在用Java为9x9网格编写一个数独求解器。
我有以下方法：
打印网格
使用给定值初始化电路板
测试冲突（如果相同的数字位于同一行或 3x3 子网格中）
一种逐个放置数字的方法，这需要最多的工作。
在我详细介绍该方法之前，请记住，我必须使用递归来解决它，以及回溯（在这里观看小程序作为示例 http://www.heimetli.ch/ffh/simplifiedsudoku.html )
另外，我正在通过垂直向下移动来解决这个数独，从左上角开始，通过第一列，然后通过第二列，依此类推。
到目前为止，我有以下几点：
public boolean placeNumber(int column){
if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over
return true;
}
else
{
int row=0; //takes you to the top of the row each time
while (row < SUDOKU_SIZE) loops through the column downwards, one by one
{
if (puzzle[row][column]==0){ //skips any entries already in there (the given values)
puzzle[row][column]=1; //starts with one
while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number
puzzle[row][column] += 1;
}
//BACK TRACKING
placeNumber(column); //recursive call
}
else{
row++; // row already has a number given, so skip it
}
}
column++; // move on to second column
placeNumber(column);
}
return false; // no solutions to this puzzle
}
我标记BACKTRACKING的地方是我认为我的代码的其余部分需要去的地方。
我想到了一些事情：
- 如果值为 10，请将该值设置回零，返回一行，然后将该值递增 1
这种回溯“策略”并不完全有效，原因如下：
如果前一行是给定值怎么办（也就是说，我不应该增加它或触摸它，而是回到我放在那里的最后一个值）
如果以前的值为 9，该怎么办？如果我把它加1，现在我们是10，这是行不通的。
有人可以帮我吗？
