迭代數獨算法

Question

我已經在過去創建了一個非常簡單的算法來蠻力數獨解決方案。只要沒有不一致性（例如同一行中具有相同值的兩個單元格），通過將每個單元格中的每個可能值放入每個單一組合中，這都非常容易以遞歸方式完成。

遞歸（在僞代碼）：

solve_sudoku(int[][] cell, int x, int y) 
if (isSolution) 
{ 
    return field; 
} 
else 
{ 
    for (int i=1; i<9; i++) 
    { 
    if (legal_move(x,y,i)) 
     cell[x][y] = i; 
     solve_sudoku(cell,x+1,y); 
    } 
} 

我不知道是否有暴力破解的數獨的解決方案的迭代方法？我不認爲這是可能的，但我不確定。如果存在，那將如何？

埃克托

Answer 1

使用堆棧遞歸代碼轉換爲迭代代碼最簡單的方法。無論如何，這就是遞歸如何工作（使用函數調用堆棧）。

這裏是迭代僞代碼，它是遞歸的粗略翻譯。

while(!isSolution(head_of_stack) && stack_not_empty) 
{ 
    current = pop_head_of_stack 
    for(move in legal_moves(current)){ 
     stack.push(move) // move is your x,y passed recursively 
         // or the whole board - depending how you 'undo' moves 
         // at the recursive backtracking now 
    } 

} 
return head_of_stack