数独淘汰策略

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上关于algos的书时，我偶然发现了消除策略，我想试着在求解器中应用它。我的基本想法是检查哪个row+column组合的可能性最小(周围的数字最多)。

我试过了：

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个维度(垂直、水平和块)上发生冲突，因此您需要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") 

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条目的row_num ->列表进行映射，对col_num也是如此。然后，迭代此列表(跳过任何非零单元格)，并改变相应的count/row/col列表以减少计数(就地)，并恢复堆不变量。您可以创建一个函数来使用它，或者如果您愿意使用heapq中的私有/无文档(且易于更改)的方法，那么可以使用heapq._siftdown。无论哪种方式，一旦所有键都递减并恢复了堆不变量，您就可以获得下一个min了。

总而言之，这种方法将占用O((M + N) * log(N * M)时间。