数独排除法策略。

Question

假设我有数独数组，用于数独求解器，例如：

[[0 0 0 0 0 0 0 5 0]
 [2 0 7 0 0 9 0 0 0]
 [6 0 0 3 5 1 0 0 0]
 [5 0 0 0 0 0 0 1 0]
 [0 0 3 0 0 0 0 0 8]
 [0 0 0 8 2 0 5 3 0]
 [0 0 0 0 7 0 8 0 4]
 [0 0 6 2 0 0 0 0 0]
 [0 8 0 0 0 0 7 0 0]]

我有一个名为nextMove()的方法，目前返回下一个要检查的坐标。

for x in range(9):
    for y in range(9):
        if sudoku[x][y] == 0:
            return [x,y]

在阅读Norwig的算法书时，我偶然发现了一种消除策略，我想尝试将其应用于求解器中。我的基本想法是检查哪个行+列组合具有最少的可能性（周围数字最多）。

我已经尝试过：

def next_move(sudoku):
    row = 0
    current_number_row = 0
    current_number_column = 0
    column = 0
    max_num_col = 0
    max_num_row = 0

    for x in range(9):
        current_number_row = 0
        for y in range(9):
            if sudoku[x][y] != 0:
                current_number_row += 1
        if current_number_row > max_num_row and current_number_row < 9:
            max_num_row = current_number_row
            row = x
    for m in range(9):
        current_number_column = 0
        if sudoku[row][m] == 0:
            for g in range(9):
                if sudoku[g][m] != 0:
                    current_number_column += 1
        if current_number_column > max_num_col and current_number_column < 9:
            max_num_col = current_number_column
            column = m
    return [row, column]

但这并不起作用，因为有时算法会返回已经填充的相同位置。

我如何编写排除策略以提高性能，同时仍能解决数独问题？

- gaming4 mining

---

在 if 块中你赋值了 "column = m"，你也应该检查 sudoku[row][m] 是否等于 0。因为 "row" 是拥有最多数字的行并不意味着该行中每个单元格都为空。 - unlut

我不是在 M 循环中这样做的吗？ - gaming4 mining

是的，那是我的错误，也许如果您检查函数返回无效单元格的状态，会更容易找到错误。 - unlut

在那个函数的340万次调用中找到它相当困难 :( - gaming4 mining

你不能只是检测返回的 [行，列] 是否为非空单元格吗？ - unlut

Answer 1

为了使这种排除策略更有效，你需要使用一种数据结构，在你进行移动时将邻居位置记录下来。每次重新计算会减缓速度而非提高性能。

这样的数据结构可以是在每个位置上剩余可用数字的一组不冲突数字，也可以是需要排除的冲突数字。当你放置或撤销一个数字时，你还需要尽可能地有效更新这个数据结构。这可以通过创建第二个结构来完成，该结构将每个位置映射到需要在放置数字时更新的位置。

此外，由于每个位置可能会在3个维度（垂直、水平和块）上发生冲突，因此您需要3个不同的组来处理集合中邻居的加法/减法。因此，放置在给定位置的每个数字都必须以组为基础使其它位置无效。

下面是一个使用此排除方法的小型数独求解器：

def shortSudokuSolve(board):  # expects a list of lists as the board
    size    = len(board)
    block   = int(size**0.5)
    board   = [n for row in board for n in row ]      
    span    = { (n,p): { (g,n)  for g in (n>0)*[p//size, size+p%size,
                                 2*size+p%size//block+p//size//block*block] }
                for p in range(size*size) for n in range(size+1) }
    empties = [i for i,n in enumerate(board) if n==0 ]
    used    = set().union(*(span[n,p] for p,n in enumerate(board) if n))
    empty   = 0
    while empty>=0 and empty<len(empties):       
        pos        = empties[empty]
        used      -= span[board[pos],pos]
        board[pos] = next((n for n in range(board[pos]+1,size+1) 
                          if not span[n,pos]&used),0)
        used      |= span[board[pos],pos]
        empty     += 1 if board[pos] else -1            
    return [board[r:r+size] for r in range(0,size*size,size)]

输出：

test =  [ [8,0,0, 0,0,0, 0,0,0],
          [0,0,3, 6,0,0, 0,0,0],
          [0,7,0, 0,9,0, 2,0,0],

          [0,5,0, 0,0,7, 0,0,0],
          [0,0,0, 0,4,5, 6,0,0],
          [0,0,0, 1,0,0, 0,3,0],

          [0,0,1, 0,0,0, 0,6,8],
          [0,0,8, 5,0,0, 0,1,0],
          [0,9,0, 0,0,0, 4,0,0]
        ]
solution = shortSudokuSolve(test)
printSudoku(test,solution)

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 8 │   │   ║   │   │   ║   │   │   ║ ║ 8 │ 1 │ 2 ║ 7 │ 5 │ 4 ║ 3 │ 9 │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 3 ║ 6 │   │   ║   │   │   ║ ║ 9 │ 4 │ 3 ║ 6 │ 8 │ 2 ║ 1 │ 5 │ 7 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 7 │   ║   │ 9 │   ║ 2 │   │   ║ ║ 6 │ 7 │ 5 ║ 3 │ 9 │ 1 ║ 2 │ 8 │ 4 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │ 5 │   ║   │   │ 7 ║   │   │   ║ ║ 1 │ 5 │ 6 ║ 9 │ 3 │ 7 ║ 8 │ 4 │ 2 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │ 4 │ 5 ║ 6 │   │   ║ ║ 3 │ 8 │ 9 ║ 2 │ 4 │ 5 ║ 6 │ 7 │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║ 1 │   │   ║   │ 3 │   ║ ║ 7 │ 2 │ 4 ║ 1 │ 6 │ 8 ║ 9 │ 3 │ 5 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │ 1 ║   │   │   ║   │ 6 │ 8 ║ ║ 2 │ 3 │ 1 ║ 4 │ 7 │ 9 ║ 5 │ 6 │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 8 ║ 5 │   │   ║   │ 1 │   ║ ║ 4 │ 6 │ 8 ║ 5 │ 2 │ 3 ║ 7 │ 1 │ 9 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 9 │   ║   │   │   ║ 4 │   │   ║ ║ 5 │ 9 │ 7 ║ 8 │ 1 │ 6 ║ 4 │ 2 │ 3 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

请注意，这仅是机制的示例，虽然它可以快速解决9x9数独难题，但为了在合理的时间内处理16x16或更大的数独难题，需要更加微妙的数字选择排除/优先考虑。

我有一个已经优化过的求解器版本（太大了无法在此共享），它确定了空单元格的优先级，及早检测死胡同（任何位置都被排除了所有数字，组中选项少于空单元格），并自动放置单个数字选项。那个版本可以在不到一秒钟的时间内解决16x16数独难题，并且可以在约一分钟内处理一些36x36数独难题。

这是我用于输出的printsudoku函数：

def niceSudo(board):
    side    = len(board)
    base    = int(side**0.5)
    def expandLine(line):
        return line[0]+line[5:9].join([line[1:5]*(base-1)]*base)+line[9:13]
    line0  = expandLine("╔═══╤═══╦═══╗")
    line1  = expandLine("║ . │ . ║ . ║")
    line2  = expandLine("╟───┼───╫───╢")
    line3  = expandLine("╠═══╪═══╬═══╣")
    line4  = expandLine("╚═══╧═══╩═══╝")

    symbol = " 123456789" if base <= 3 else " ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
    nums   = [ [""]+[symbol[n] for n in row] for row in board ]
    lines  = []
    lines.append(line0)
    for r in range(1,side+1):
        lines.append( "".join(n+s for n,s in zip(nums[r-1],line1.split("."))) )
        lines.append([line2,line3,line4][(r%side==0)+(r%base==0)])
    return lines
        
def printSudoku(*boards):
    print(*(" ".join(ss) for ss in zip(*(niceSudo(b) for b in boards))),sep="\n") 

  

- Alain T.

Answer 2

首先，让我们尝试简化您现有的方法 -

def find_best(grid):
    row_counts = [row.count(0) for row in grid]
    col_counts = [col.count(0) for col in zip(*grid)]

    cells_with_scores = ((row_count + col_count, row_idx, col_idx) 
            for row_count, (row_idx, row)  in zip(row_counts, enumerate(grid))
            for col_count, (col_idx, elem) in zip(col_counts, enumerate(row)) 
            if elem)

    score, row_num, col_num = min(cells_with_scores)
    return row_num, col_num

请注意，我们只是计算每行/列上的0的数量，遍历每个单元格，并丢弃任何非零值。然后获取最小元组，其中最小的行数和列数之和为row_count + col_count。

当然，这是O(N*M)，其中N是行数，M是列数。虽然不是很好，但很简单，我们可以改进它。

为此，我们需要从cells_with_scores中的优先级/坐标元组构建一个优先级队列/最小堆（由于稍后将要看到的原因，需要切换到列表）。我们可以使用内置的heapq模块来完成此操作。然后，我们可以在初始构建后的O(1)时间内获得最小值。然而，在进行移动后，我们需要使用新的单元格分数更新此队列，这意味着对于与分配单元格相同行或列中的每个单元格，我们都需要将堆中相应元素的优先级键减1。

你可以自己编写代码实现此功能，或者可以创建一个行号到cells_with_scores条目列表的映射，并为列号做同样的操作。然后，迭代此列表（跳过任何非零单元格），并改变相应的计数/行/列列表以减少计数（就地进行），并恢复堆不变式。你可以创建一个函数来使用它，或者如果你愿意使用heapq中未公开的方法（并且容易更改），则使用heapq._siftdown。无论哪种方式，一旦所有键都被递减并恢复堆不变式，你就可以获得下一个最小值。

总之，这种方法需要O((M + N) * log(N * M)时间。

- Dillon Davis

---

嗨，我尝试了您提供的方法，但是看起来代码无法编译 if elem)) ^ SyntaxError: invalid syntax。 - gaming4 mining

@gaming4mining 啊，我上次的更改（添加 'if elem'）把括号放错了位置。 - Dillon Davis

算法比实际实现更重要-我提供代码作为下一段的参考，其中我解释了一个渐进（远远）更快的算法。 - Dillon Davis