python - 数独消除策略

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]

在阅读 norwigs 关于算法的书时，我偶然发现了我想尝试在求解器中应用的消除策略。我的基本想法是检查哪个行+列组合的可能性最小(周围数字最多)

我试过:

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]

然而，这不起作用，因为有时算法会继续返回相同的位置，尽管它已经被填满。

如何编写消除策略来提高性能，同时仍然能够解决数独问题？

Answer 1

为了使这种消除策略有效，您需要有一个数据结构来在您移动时跟踪邻居。每次都为每个位置重新计算它们会减慢速度而不是提高性能。

这样的结构可以是一组不冲突的数字，在移动后在每个位置仍然可用，或者它可以是要排除的冲突数字。当您移动或收回时，您还需要尽可能高效地更新此结构。这可以通过创建第二个结构来完成，该结构将每个位置映射到放置数字时需要更新的位置。

除此之外，由于每个位置都可能在 3 个维度(垂直、水平和 block )上发生冲突，因此您需要 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")