Divide backtracking into parallel processes

Question

I am trying to solve sudoku 25*25 using the backtracking process in c. Is there any way to divide backtracking into multiple parallel processes so that I could use them as threads?

Answer 1

Backtracking implies a depth-first search.

A DFS will take on the following form:

1. Create a stack of states.
2. Push the initial state onto the stack.
3. While the stack isn't empty,
   1. Pop a state from the stack.
   2. If the search is satisfied by the state,
      1. Return the state.
   3. For each possible derived state,
      1. Push the derived state onto the stack.
4. Return a failure.

(Recursion is often used to provide the stack, but that's no requirement.)

In the context of a Sudoku solver,

1. Create a stack of states.
2. Push the initial state onto the stack.
3. While the stack isn't empty,
   1. Pop a state from the stack.
   2. If the search is satisfied by the state,
      1. Return the state.
   3. Find an empty square.
   4. For each possible value in the square,
      1. Clone the current state.
      2. Set the value for the square in the cloned state.
      3. Push the cloned state onto the stack.
4. Invalid Sudoku

I would use a breadth-first search, though. It's identical to the above, except a queue is used instead of a stack.

We can easily convert that to a worker-based model. Just use a thread-safe queue, and a bunch of threads executing the loop.