Java中的数独求解器，使用回溯和递归 [英] Sudoku solver in Java, using backtracking and recursion

问题描述

我正在使用Java编写一个用于9x9网格的数独求解器。

我有以下方法：

• 打印网格




• 使用给定值初始化电路板




• 测试冲突（如果相同的数字在同一行或3x3子网格中）




• 放置数字的方法，一个一，这需要最多的工作。

在我详细介绍这种方法之前，请记住我有使用递归来解决它，以及回溯（在这里观看applet作为示例 http：// www.heimetli.ch/ffh/simplifiedsudoku.html ）

此外，我通过垂直向下移动解决这个数独，从左上角开始，直到第一列，然后通过第二列等。

到目前为止，我有以下内容：

  public boolean placeNumber（int列）{
 
 if（column == SUDOKU_SIZE）{//我们已经浏览了所有列，游戏超过
 
返回true; 
 
} 
 
 else 
 {
 int row = 0; //每次
 
时将你带到行的顶部，而（row< SUDOKU_SIZE）在列中向下循环，逐个
 {
 
 if （puzzle [row] [column] == 0）{//跳过那里已经存在的任何条目（给定值）
 
 puzzle [row] [column] = 1; //以
 
开头，而（conflictTest（row，column））{// conflictsTest是我写的方法，它检查给定参数是否与另一个数字冲突
 
 puzzle [row] [column] + = 1; 
 
} 
 
 
 //返回跟踪
 
 placeNumber（列）; //递归调用
 
} 
 else {
 row ++; // row已经给出了一个数字，所以跳过它
} 
} 
 
 column ++; //继续前进到第二列
 placeNumber（column）; 
 
} 
返回false; //没有这个拼图的解决方案
} 
  

我标记为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中的一个。 / p>

现在让我们考虑如何让递归蛮力工作。

我们的目标是解决数独有n个空单元格。 如果我们有一个函数可以解决带有n-1个空单元格的数据（或表示它不可解决），那么这个任务很简单：

 让c为空单元格。 
让f成为解决数据减少一个空单元格的数据的函数。 $ 1 
 for i in 1..9 
检查我是否可以放入c而不冲突
如果没有继续下一个i 
我在c 
如果f（ ）==已解决然后返回已解决
返回NOTSOLVABLE 
  

此伪代码选取一些空单元格，然后尝试适合那里的所有数字。
因为根据定义，数独只有一个解决方案，所以只有以下几种情况：

• 我们选择了正确的数。然后f（）将找到解决方案的其余部分并返回SOLVED。


• 我们选择了一个错误的数字：f（）将表示数据在我们的单元格中无法用错误的数字解决。


• 我们检查了所有数字，但是没有人是正确的：然后我们自己有一个无法解决的数据，我们向我们的来电者发出信号。

毋庸置疑，该算法基于这样的假设：我们只会将不是
的数字与当前状态冲突。例如，我们不会在同一行，列或框中放置 9 那里已经有 9 。

如果我们现在想一想我们神秘但未知的函数 f（）是怎样的，事实证明它将与我们已经拥有的几乎相同！

我们尚未考虑的唯一案例是具有0个空单元格的数独。这意味着，如果我们发现没有更多的空单元格，我们知道我们刚刚解决了数独并返回刚刚解决的问题。

这是写作时的常见技巧一个应该解决问题的递归函数。我们正在编写solve（），我们知道，这个问题是可以解决的。因此，我们已经可以使用我们正在编写的函数，只要我们确保每次递归时，问题都会更接近解决方案。最后，我们达到了所谓的基本情况，我们可以在没有进一步递归的情况下给出解决方案。

在我们的例子中，我们知道数独是可解的，而且，我们知道它只有一个解决方案。通过将一个片段放在一个空单元格中，我们更接近解决方案（或者没有的诊断），并将新的，较小的问题递归地提供给我们刚刚编写的函数。基本情况是Sudoku with 0 empty cells，实际上是解决方案。

（如果有很多可能的解决方案，事情会变得复杂一点，但我们会在下一课中留下它。）

I am programming a Sudoku solver in Java for a 9x9 grid.

I have methods for:

• printing the grid

• initializing the board with given values

• testing for conflicts (if same number is in same line or 3x3 sub-grid)

• a method to place the digits, one by one, which requires the most work.

Before I go into detail with that method, keep in mind that I have to use recursion to solve it, as well as backtracking (watch the applet here as an example http://www.heimetli.ch/ffh/simplifiedsudoku.html )

Also, I am solving this Sudoku by moving vertically downwards, starting from the top left, through the first column, and then through the second column, etc.

So far, I have the following:

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
}

Where I labeled BACKTRACKING is where I believe the remainder of my code needs to go.

I thought up of something along the lines of:

• if the value is 10, set that value back to zero, go back a row, and increment that value by 1

That backtracking 'strategy' doesn't exactly work for several reasons:

1. what if the previous row, was a given value (aka I'm not supposed to increment it or touch it, but instead, go back to the last value that I placed there)

2. what if the previous value was a 9. and if I incremented that by 1, now we're at 10, which won't work.

Can someone please help me out?

解决方案

I do not know how you're going to solve the sudoku, but even if you use the brute force method (and so it sounds to me what you describe) you should consider that your data structure is not appropriate.

With that I mean that every cell should not just be a number, but a set of numbers (that may be possibly placed there).

Hence, the given numbers will be represented as singleton sets, while the empty ones you can initialize with {1,2,3,4,5,6,7,8,9}. And then the goal is to reduce the non-singleton cells until all cells are singletons.

(Note that, while solving a sudoku with pencil and paper, one often writes small numbers in the blank cells to keep track of what numbers are possible there, as far as one has solved it.)

And then, when "trying the next number" you take the next number from the set. Given cells have no next number, so you can't change them. This way, the difficulties you describe vanish (a bit, at least).

------ EDIT, AFTER HAVING LEARNED THAT BRUTE FORCE IS REQUIRED.

Your teacher obviously wants to teach you the wonders of recursion. Very good!

In that case, we just need to know which cells are given, and which are not.

A particular easy way that could be used here is to place a 0 in any non-given cell, as given cells are by definition one of 1,2,3,4,5,6,7,8,9.

Now lets think about how to make the recursive brute force working.

We have the goal to solve a sudoku with n empty cells. If we had a function that would solve a sudoku with n-1 empty cells (or signal that it is not solvable), then this task would be easy:

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

This pseudo code picks some empty cell, and then tries all numbers that fit there. Because a sudoku has - by definition - only a single solution, there are only the following cases:

• we picked the correct number. Then f() will find the rest of the solution and return SOLVED.
• we picked a wrong number: f() will signal that the sudoku is not solvable with that wrong number in our cell.
• we checked all numbers, but no one was correct: Then we have got an unsolvable sudoku ourselves and we signal this to our caller.

Needless to say, the algorithm rests on the assumption that we only ever place numbers that are not conflicting with the current state. For example, we do not place a 9 there when in the same row, column or box there is already a 9.

If we now think about how our mysterious, yet unknown function f() looks like, it turns out that it will be almost the same as what we already have!
The only case we have not yet considered is a sudoku with 0 empty cells. This means, if we find that there are no more empty cells, we know that we have just solved the sudoku and return just SOLVED.

This is the common trick when writing a recursive function that is supposed to solve a problem. We We are writing solve(), and we know, that the problem is solvable at all. Hence, we can already use the function we are just writing as long as we make sure that with every recursion, the problem somehow gets closer to the solution. At the end, we reach the so called base case, where we can give the solution without further recursion.

In our case we know that Sudoku is solvable, moreover, we know it has exactly one solution. By placing a piece in an empty cell, we come closer to the solution (or to the diagnosis that there is none) and give the new, smaller problem recursively to the function we are just writing. The base case is the "Sudoku with 0 empty cells" which actually is the solution.

(Things get a bit more complicated if there are many possible solutions, but we leave that for the next lesson.)

这篇关于Java中的数独求解器，使用回溯和递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！