Java中的数独求解器，使用回溯和递归
我正在用Java编写一个用于9×9网格的数独求解器。
我有方法：
-
打印网格
-
用给定的值初始化电路板
-
测试冲突（如果相同的数字在同一行或3×3子网格中）
-
一种逐个放置数字的方法，这需要最多的工作。
在我详细介绍该方法之前，请记住我必须使用递归来解决它，以及回溯（在这里观看applet作为示例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，这将无效。
有人可以帮帮我吗？
我不知道你将如何解决数独，但即使你使用蛮力方法（所以它听起来你所描述的）你应该考虑你的数据结构是不合适的。
我的意思是每个单元格不应该只是一个数字，而是一组数字（可能放在那里）。
因此，给定的数字将表示为单例集，而空的表示可以用{1,2,3,4,5,6,7,8,9}初始化。 然后目标是减少非单体细胞，直到所有细胞都是单体。
（注意，在使用铅笔和纸张解决数独时，人们经常在空白单元格中写入小数字，以便跟踪那里可能存在的数字，只要有人解决了它。）
然后，当“尝试下一个号码”时，你从集合中取下一个号码。 给定单元格没有下一个数字，因此您无法更改它们。 这样，你所描述的困难就会消失（至少有点）。
——编辑，在学习了必须要有强制力之后。
你的老师显然想教你递归的奇迹。 很好！
在这种情况下，我们只需要知道哪些细胞被给予，哪些不是。
这里可以使用的一种特别简单的方法是在任何非给定的单元格中放置0，因为给定的单元格是1,2,3,4,5,6,7,8,9中的一个。
现在让我们考虑如何使递归蛮力工作。
我们的目标是用n个空单元解决数独。 如果我们有一个函数可以解决带有n-1个空单元格的数据（或表示它不可解决），那么这个任务就很简单了：
let c be some empty cell. let f be the function that solves a sudoku with one empty cell less. for i in 1..9 check if i can be placed in c without conflict if not continue with next i place i in c if f() == SOLVED then return SOLVED return NOTSOLVABLE
这个伪代码选择一些空单元格，然后尝试适合那里的所有数字。 因为根据定义，数独只有一个解决方案，所以只有以下情况：
- 我们选择了正确的号码。 然后f（）将找到解决方案的其余部分并返回SOLVED。
- 我们选择了一个错误的数字：f（）将发信号通知我们的单元格中数字错误的数字无法解决数独。
- 我们检查了所有数字，但没有人是正确的：然后我们自己有一个无法解决的数据，我们向我们的来电者发出信号。
不用说，算法依赖于我们只放置与当前状态不冲突的数字的假设。 例如，当在同一行，列或框中时，我们不会在那里放置9 。
如果我们现在想一想我们神秘但未知的函数f()是什么样的，事实certificate它几乎和我们已经拥有的一样！
我们尚未考虑的唯一案例是数独有0个空单元格。 这意味着，如果我们发现没有更多的空单元格，我们知道我们刚刚解决了数独并返回刚刚解决的问题。
这是编写应该解决问题的递归函数时的常见技巧。 我们正在编写solve（），我们知道，这个问题是可以解决的。 因此，我们已经可以使用我们正在编写的函数，只要我们确保每次递归时，问题都会更接近解决方案。 最后，我们达到了所谓的基本情况，我们可以在没有进一步递归的情况下给出解决方案。
在我们的例子中，我们知道Sudoku是可以解决的，而且，我们知道它只有一个解决方案。 通过将一个片段放在一个空单元格中，我们更接近解决方案（或诊断没有），并将新的，较小的问题递归地提供给我们正在编写的函数。 基本情况是“Sudoku with 0 empty cells”，实际上是解决方案 。
（如果有许多可能的解决方案，情况会变得复杂一点，但我们将其留给下一课。）
首先 ，建议优化：在检查您要放入单元格中的数字是否已经存在于同一行，列或小型网格中时，您不必运行循环或类似的东西。 您可以通过数组索引执行即时检查。
考虑3个9×9布尔双维数组：
boolean row[9][9], col[9][9], minigrid[9][9]
我们将使用第一个数组来检查同一行中是否存在数字，第二个数组用于检查同一列中是否存在数字，第三个数组用于迷你网格。
假设你想在你的单元格中放入一个数字i ， j 。 您将检查row [i] [n-1]是否为真。 如果是，那么第 i行已经包含n。 同样，您将检查col [j] [n-1]和minigrid [gridnum] [n-1]是否为真。
这里， gridnum是迷你网格的索引，其中要插入数字的单元格位于。要计算单元格i的迷你网格数，j ，将i＆j除以3，将前者的整数部分乘以3，将它添加到后者的组成部分。
这看起来如何：
gridnum = (i/3)*3 + j/3
通过查看所有i和j的i / 3和j / 3值，您将了解其工作原理。 此外，如果您在单元格中放置一个数字，也要更新数组。 例如row [i] [n-1] = true
如果有一部分你不理解，发表评论，我会编辑我的答案来解释它。
其次 ，使用递归和回溯来解决这个问题非常简单。
boolean F( i, j) // invoke this function with i = j = 0 { If i > 8: return true // solved for n in 1..9 { check if n exists in row, column, or mini grid by the method I described if it does: pass ( skip this iteration ) if it doesn't { grid[i][j] = n update row[][], col[][], minigrid[][] if F( if j is 8 then i+1 else i, if j is 8 then 0 else j+1 ) return true // solved } } return false // no number could be entered in cell i,j }
我建议将当前行和列传递给递归方法，然后找到THAT单元格的所有允许数字，对于每个允许的数字，递归调用下一列的方法（如果在最后一列，则调用下一行），如果它导致则撤消移动走向死路
public boolean fillCell(int r, int c) { if last row and last cell { //report success return true } for i 1 to 9 { if can place i on r, c { board[r][c] = i if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move board[r][c] = 0 } /* else { return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also } */ } } return false }
如果找不到解决方案，我会检查每个单元格并返回递归步骤。
更详细：转到下一个单元格，如果值x == 0，检查x + 1是否有效，如果为真，则通过下一个可能的单元格递归调用该方法转到下一个单元格。 如果数字无效，请检查x + 2等。如果没有数字有效，则返回false并重复上一次呼叫中的x + 1步骤。 如果您在内部有一个数字的单元格，请不要调用递归，而是直接转到下一个，因此您不需要标记任何预先输入的单元格。
伪代码：
fillcell cell while cell is not 0 cell = next cell while cell value < 10 increase cell value by one if cell is valid if fillcell next cell is true return true return false
不确定这是否正确，但它应该显示的想法。
一些可能有用的想法（关于递归和回溯）
//some attributes you might need for storing eg the configuration to track back to. boolean legal(Configuration configuration) { } int partSolution(Configuration configuration) { if (legal(configuration)) return partSolution(nextConfiguration()) else return partSolution(previousConfiguration()) } Configuration nextConfiguration() { //based on the current configuration and the previous tried ones, //return the next possible configuration: //next number to enter, next cell to visit } Configuration previousConfiguration() { //backtrack } solve () { call partSolution with start configuration while partSolution < 9x9 }
编写一个Configuration类，它使用输入的数字保存网格，并输入一些其他属性，如输入的大小和#numbers，并考虑还需要什么