Backtracking paradigm: is it possible to do it without recursion? [closed]

Question

Example: sudoku solving with backtracking

How do you backtrack without recursion - using loops? I only found solutions when you call backtrack() itself.

Answer 1

You can emulate the recursion with a stack.

Essentially, backtracking does a depth-first search in the tree of candidate solutions. For sudoku, this tree has fully filled grids at the leaves and partially filled grids at the nodes. The root is the provided grid. A grid node is a child of another one if it can be derived from it by filling a number. With this analogy between depth-first search and backtracking, you can easily implement backtracking either recursively or with a stack.

The stack could (conceptually) contain candidate grids. First, the provided (and partially filled) grid is pushed on the stack. Then inside a while loop (checking whether the stack is empty or not), the top grid is popped. One checks whether the grid is fully filled or not. If it is fully filled, the sudoku constraints are verified and the grid is returned it if they are satisfied. If the grid is not fully filled, then other candidate grids are generated from it (possibly none) which are all pushed on the stack. This summarizes the idea of the conversion, but of course as is it is not really efficient.