c++ - 数独回溯算法

Question

可能重复：
数独回溯算法

我不知道为什么我现在不能直接思考，但到目前为止，但我希望在为我的数独难题开发算法时能得到一些帮助。在检查所有行、列和 3x3 之后，我有一个可以进入每个单元格的可能数字列表。我有将数字放入每个单元格的代码。但是，我在回溯方面遇到了很多麻烦。任何人都可以帮助我为数独难题的回溯部分提供一些伪代码吗？

谢谢。

Answer 1

您可以尝试基于堆栈的方法。通过递归使用调用堆栈，其中回溯返回堆栈错误：

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]

对于奖励积分，使用生成器 say 重做堆栈方法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也写一个生成器，那么这两个可以一起工作直到事情完成。因为这使用了生成器而不是递归，所以堆栈不会增长，并且新板是根据需要而不是提前生成的，因此存储要求也很低。相当优雅，真的，具有发电机的力量。

Answer 2

像这样的东西？

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 就是这种情况。