0

重複の可能性:
数独バックトラッキング アルゴリズム

なぜ今すぐに考えられないのかわかりませんが、今のところ、数独パズルのアルゴリズムを開発するのに役立つことを望んでいました. すべての行、列、および 3x3 をチェックした後、各セルに入れることができる可能な数字のリストがあります。各セルに数字を配置するコードがあります。ただし、バックトラックの側面で多くの問題を抱えています。数独パズルのバックトラック部分の疑似コードを手伝ってくれる人はいますか?

ありがとう。

4

2 に答える 2

0

スタックベースのアプローチを試すことができます。再帰を介してコールスタックを使用するか、バックトラッキングがスタックに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]

ボーナスポイントについては、ジェネレーター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、これら2つは、処理が完了するまで連携して機能します。これは再帰ではなくジェネレーターを使用するため、スタックは拡大せず、新しいボードはすべてではなく必要に応じて事前に生成されるため、ストレージ要件も低くなります。かなりエレガントで、本当に、発電機の力を持っています。

于 2012-10-18T21:06:44.553 に答える
0

このようなもの？

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手番生成コードが常に部分的なソリューションにつながる手番を生成する場合は、必要ないかもしれません。すず子もそうだと思います。

于 2012-10-18T20:34:20.847 に答える