25

我正在用 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，这将不起作用。

有人可以帮我吗？

4

6 回答 6

7

我不知道您将如何解决数独问题，但即使您使用蛮力方法（在我看来您所描述的内容），您也应该考虑到您的数据结构不合适。

我的意思是每个单元格不应该只是一个数字，而是一组数字（可能放在那里）。

因此，给定的数字将表示为单例集，而您可以使用 {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当在同一行、列或框中已经存在 a 时，我们不会将 a 放置在那里9。

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

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

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

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

于 2012-02-22T23:23:51.640 回答
4

首先，优化建议：在检查您要放入单元格中的数字是否已经存在于同一行、列或小网格中时，您不必运行循环或类似的东西。您可以通过数组索引执行即时检查。

考虑 3 个 9x9 布尔双维数组：

boolean row[9][9], col[9][9], minigrid[9][9]

我们将使用第一个数组检查数字是否存在于同一行中，第二个数组用于检查数字是否存在于同一列中，第三个数组用于迷你网格。

假设您想在单元格i和j中输入一个数字n。您将检查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
}
于 2012-04-09T04:22:42.217 回答
1

我建议将当前行和列都传递给递归方法，然后找到该单元格的所有允许数字，对于每个允许的数字，递归调用下一列的方法（或者如果在最后一列则为下一行）并撤消移动如果它导致到死路

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        
}
于 2012-02-22T23:47:27.450 回答
0

如果找不到解决方案，我会检查每个单元格并返回递归步骤。

更详细：转到下一个单元格，如果值 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

不确定这是否正确，但它应该显示这个想法。

于 2012-02-23T02:00:23.917 回答
0

一些可能有用的想法（关于递归和回溯）

//some attributes you might need for storing e.g. 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
}

编写一个配置类，其中包含输入的数字和其他一些属性（如输入的大小和#numbers）的网格，并考虑还需要什么

于 2012-02-23T03:15:57.387 回答
0

此页面上的其他答案涵盖了回溯算法。有趣的是，只需稍加优化，您就可以显着改进这种回溯算法。这个想法是使用贪婪的最佳优先搜索：不是从上到下，从左到右选择“下一个”单元格，而是选择下一个单元格作为可能性最少的单元格。

例如，如果包含该单元格的行已经有数字 1 2 3，列有 4 5 6，而 3x3 块有 7，那么只剩下 2 种可能性：8 和 9。这看起来像一个很好的单元格选择。

这一改进大大加快了程序的运行速度，使程序运行得足够快，可以满足我的实时数独求解器的需求

您可以在此处查看此算法的动画。

链接到Visualizer 代码和实时求解器代码

Greedy Best First Search的代码如下：

# Keep data about the "Best" cell
class EntryData:
    def __init__(self, r, c, n):
        self.row = r
        self.col = c
        self.choices = n

    def set_data(self, r, c, n):
        self.row = r
        self.col = c
        self.choices = n

# Solve Sudoku using Best-first search
def solve_sudoku(matrix):
    cont = [True]
    # See if it is even possible to have a solution
    for i in range(9):
        for j in range(9):
            if not can_be_correct(matrix, i, j): # If it is not possible, stop
                return
    sudoku_helper(matrix, cont) # Otherwise try to solve the Sudoku puzzle

# Helper function - The heart of Best First Search
def sudoku_helper(matrix, cont):
    if not cont[0]: # Stopping point 1
        return

    # Find the best entry (The one with the least possibilities)
    best_candidate = EntryData(-1, -1, 100)
    for i in range(9):
        for j in range(9):
            if matrix[i][j] == 0: # If it is unfilled
                num_choices = count_choices(matrix, i, j)
                if best_candidate.choices > num_choices:
                    best_candidate.set_data(i, j, num_choices)

    # If didn't find any choices, it means...
    if best_candidate.choices == 100: # Has filled all board, Best-First Search done! Note, whether we have a solution or not depends on whether all Board is non-zero
        cont[0] = False # Set the flag so that the rest of the recursive calls can stop at "stopping points"
        return

    row = best_candidate.row
    col = best_candidate.col

    # If found the best candidate, try to fill 1-9
    for j in range(1, 10):
        if not cont[0]: # Stopping point 2
            return

        matrix[row][col] = j

        if can_be_correct(matrix, row, col):
            sudoku_helper(matrix, cont)

    if not cont[0]: # Stopping point 3
        return
    matrix[row][col] = 0 # Backtrack, mark the current cell empty again
            

# Count the number of choices haven't been used
def count_choices(matrix, i, j):
    can_pick = [True,True,True,True,True,True,True,True,True,True]; # From 0 to 9 - drop 0
    
    # Check row
    for k in range(9):
        can_pick[matrix[i][k]] = False

    # Check col
    for k in range(9):
        can_pick[matrix[k][j]] = False;

    # Check 3x3 square
    r = i // 3
    c = j // 3
    for row in range(r*3, r*3+3):
        for col in range(c*3, c*3+3):
            can_pick[matrix[row][col]] = False

    # Count
    count = 0
    for k in range(1, 10):  # 1 to 9
        if can_pick[k]:
            count += 1

    return count

# Return true if the current cell doesn't create any violation
def can_be_correct(matrix, row, col):
    
    # Check row
    for c in range(9):
        if matrix[row][col] != 0 and col != c and matrix[row][col] == matrix[row][c]:
            return False

    # Check column
    for r in range(9):
        if matrix[row][col] != 0 and row != r and matrix[row][col] == matrix[r][col]:
            return False

    # Check 3x3 square
    r = row // 3
    c = col // 3
    for i in range(r*3, r*3+3):
        for j in range(c*3, c*3+3):
            if row != i and col != j and matrix[i][j] != 0 and matrix[i][j] == matrix[row][col]:
                return False
    
    return True

# Return true if the whole board has been occupied by some non-zero number
# If this happens, the current board is the solution to the original Sudoku
def all_board_non_zero(matrix):
    for i in range(9):
        for j in range(9):
            if matrix[i][j] == 0:
                return False
    return True
于 2020-06-24T14:51:36.300 回答