title: Multi-threaded algorithm for solving sudoku?
body: <p>I have a homework assignment to write a multi-threaded sudoku solver, which finds all solutions to a given puzzle.  I have previously written a very fast single-threaded backtracking sudoku solver, so I don't need any help with the sudoku solving aspect.  </p>
  
  <p>My problem is probably related to not really grokking concurrency, but I don't see how this problem benefits from multi-threading.  I don't understand how you can find different solutions to the same problem at the same time without maintaining multiple copies of the puzzle.  Given this assumption (please prove it wrong), I don't see how the multi-threaded solution is any more efficient than a single-threaded.  </p>
  
  <p>I would appreciate it if anyone could give me some starting suggestions for the algorithm (please, no code...)</p>
  
  <hr>
  
  <p>I forgot to mention, the number of threads to be used is specified as an argument to the program, so as far as I can tell it's not related to the state of the puzzle in any way...</p>
  
  <p>Also, there may not be a unique solution - a valid input may be a totally empty board.  I have to report <code>min(1000, number of solutions)</code> and display one of them (if it exists)</p>