數獨回溯算法

Question

可能重複：
Sudoku backtracking algorithm

我不知道爲什麼同心難改，但現在作爲的權利，但我希望一些幫助爲我的數獨謎題開發算法。在檢查所有行，列和3x3之後，我會列出每個單元格中可能的數字。我有將數字放入每個單元格的代碼。不過，我在回溯方面遇到了很多麻煩。任何人都可以幫助我解決sudoku難題的回溯部分的一些僞代碼嗎？

謝謝。

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也作爲發電機，那麼這兩個可以一起工作，直到事情是完成。由於這種方式使用的是發電機而不是遞歸，因此堆棧不會增長，而是根據需要生成新的板卡，而不是預先生成，因此存儲要求也很低。真的很優雅，發電機的力量。