algorithm - 迭代数独算法

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