我正在用 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

由于以下几个原因，这种回溯“策略”并不完全奏效:

1. 如果上一行是一个给定的值(也就是说，我不应该增加或触摸它，而是返回到我放置在那里的最后一个值)

2. 如果之前的值是 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 时，我们不会在其中放置 9。

如果我们现在想一想我们神秘却不为人知的函数 f() 的样子，原来它和我们已经拥有的几乎一样!
我们尚未考虑的唯一情况是具有 0 个空单元格的数独。这意味着，如果我们发现没有更多的空单元格，我们就知道我们刚刚解决了数独问题并返回了刚刚解决的问题。

这是编写旨在解决问题的递归函数时的常见技巧。我们正在编写solve()，而且我们知道，这个问题是完全可以解决的。因此，我们已经可以使用我们刚刚编写的函数，只要我们确保在每次递归时，问题都会以某种方式更接近解决方案。最后，我们达到了所谓的基本情况，在这种情况下，我们可以在不进一步递归的情况下给出解决方案。

在我们的例子中，我们知道数独是可解的，此外，我们知道它只有一个解。通过将一 block 放在一个空单元格中，我们更接近解决方案(或接近没有解决方案的诊断)，并将新的、更小的问题递归地提供给我们正在编写的函数。基本情况是“具有 0 个空单元格的数独”，实际上 是解决方案。

(如果有很多可能的解决方案，事情会变得有点复杂，但我们将其留到下一课。)

关于java - Java中的数独求解器，使用回溯和递归，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9404673/