Java中的数独求解器,使用回溯和递归

Question

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

我有方法:

• 打印网格

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

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

• 一种逐个放置数字的方法,这需要最多的工作.

在我详细介绍该方法之前,请记住我必须使用递归来解决它,以及回溯(在这里观看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

由于以下几个原因,这种回溯"策略"并不完全有效:

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

2. 如果之前的值为9,如果我将其递增1,那么现在我们处于10,这将无效.

有人可以帮帮我吗？

Answer 1

我不知道你将如何解决数独,但即使你使用蛮力方法(因此听起来你所描述的内容),你应该考虑你的数据结构是不合适的.

我的意思是每个单元格不应该只是一个数字,而是一组数字(可能放在那里).

因此,给定的数字将表示为单例集,而空的表示可以用{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(),我们知道,这个问题是可以解决的.因此,我们已经可以使用我们正在编写的函数,只要我们确保每次递归时,问题都会更接近解决方案.最后,我们达到了所谓的基本情况,我们可以在没有进一步递归的情况下给出解决方案.

在我们的例子中,我们知道Sudoku是可以解决的,而且,我们知道它只有一个解决方案.通过在空单元格中放置一个部分,我们更接近解决方案(或诊断没有),并将新的,较小的问题递归地提供给我们正在编写的函数.基本情况是"Sudoku with 0 empty cells",实际上是解决方案.

(如果有许多可能的解决方案,情况会变得复杂一些,但我们将其留给下一课.)