I won't explain what backtracking is, Wikipedia article does it well enough.
Backtracking solver is usually implemented using recursive function that traverses a tree of potential candidates that is discovered at the same time.
Now that function can return early when it finds the first solution or traverse the whole tree and return all solutions at the same time.
But what if I want to find first solution and then maybe ask for the next one later?
As far as I know there is no feature in common programming languages that would allow function to return and at the same time give the possibility to resume it execution later.
I guess it could be quite easily emulated with threads:
- Solving function is run on separate thread.
- When it finds a solution it stores it in some external variable and pauses the thread (basically thread is used to store a call stack).
- When user needs next solution he simply resumes the thread.
Sadly not every environment is multi-threaded. What can I do when threads are not available? Do I have to modify my function to explicitly store the copy of a call stack which is then returned with the solution, and to manually recreate the recursion tree when function is called for a next solution?
Best Answer
Fortunately, there is a much simpler approach than your multi-threading alternative: implement your backtracking using queues or stacks, instead of recursivity.
In this case, when your top state is a solution, you can return it. And you can resume backtracking to find the next solution by processing the next state in the queue/on the stack.
This article could interest you: "Backtracking" It describes the recursive and non recursive version.