数独回溯算法

Question

可能重复： Sudoku backtracking algorithm

我不知道为什么我现在不能直截了当地思考，但我希望能在为我的sudoku拼图开发算法方面提供一些帮助。在检查了所有的行、列和3x3之后，我有一个可能出现在每个单元格中的数字列表，我有将数字放入每个单元格的代码。然而，我在回溯方面遇到了很多麻烦。有人能帮我解决sudoku难题的回溯部分的psuedocode吗？

谢谢。

Answer 1

像这样吗？

solve_suduko(Puzzle& p)
{
  for (m : all possible moves)
  { 
     p.make_move(m);
     if (p.solved())
     {
       print_solution(p);
     }
     else if (p.partial_solution())
     {
       solve_suduko(p);
     }
     p.unmake_move(m);
  }
}

如果移动生成代码总是生成导致部分解决方案的移动，那么您可能不需要partial_solution。我认为suduko的情况就是这样。

Answer 2

你可以尝试一种基于堆栈的方法。或者通过递归使用调用堆栈，其中回溯返回堆栈上的false：

def solveBoard(partialBoard):
    nextUnsolvedBlock = getNextBlock(partialBoard)
    possibles = generatePossiblePositions(partialBoard)
    for possibility in possibles:
        result = solveBoard(partialBoard)
        if result.valid:
            return result;

这种方法在很大程度上受到堆栈大小的限制；它不是尾回式，所以堆栈必须增长，其最大大小是从空板到完成板的步骤数。

另一种方法是构造自己的堆栈，这将允许更多这样的步骤，因为它将存储在堆中：

def solveBoard(partialBoard):
    stack = [(partialBoard,0,0)] // (board, nextBlock, blockOptionIndex)
    while stack.last[0].valid == false:
        nextBlockOption = getNextBlockOption(stack.last)
        if nextBlockOption == None:
            pop(stack)
            nextBlock = getNextBlock(stack.last)
            if nextBlock = None:
                exit("No solution")
            else:
                stack.last[2] = nextBlock
        else:
            stack.last[1] = nextBlockOption
    return stack.last[0]

为了获得额外的积分，使用生成器(比如generateBoards )重做堆栈方法，它从给定的板开始，并以一致的模式生成新的板。这样你的阿尔法就会是公正的：

def solveBoard(initialBoard):
    for board in generateBoards(initialBoard):
        if isValid(board):
            return board
    return "No solution found"

然后，复杂性就在generateBoards中了：

def generateBoards(partialBoard):
    nextUnsolvedBlock = getNextBlock(partialBoard)
    for possibility in generatePossiblePositions(partialBoard):
        yield possibility

如果你也把generatePossiblePositions写成一个生成器，那么这两者可以一起工作，直到事情完成。因为这使用的是生成器而不是递归，所以堆栈不会增长，新的板是根据需要生成的，而不是预先生成的，所以存储需求也很低。相当优雅，真的，有发电机的力量。