How to parallelize Sudoku solver using Grand Central Dispatch?

Question

As a programming exercise, I just finished writing a Sudoku solver that uses the backtracking algorithm (see Wikipedia for a simple example written in C).

To take this a step further, I would like to use Snow Leopard's GCD to parallelize this so that it runs on all of my machine's cores. Can someone give me pointers on how I should go about doing this and what code changes I should make? Thanks!

Matt

Answer 1

Are you sure you want to do that? Like, what problem are you trying to solve? If you want to use all cores, use threads. If you want a fast sudoku solver, I can give you one I wrote, see output below. If you want to make work for yourself, go ahead and use GCD ;).

Update:

I don't think GCD is bad, it just isn't terribly relevant to the task of solving sudoku. GCD is a technology to tie GUI events to code. Essentially, GCD solves two problems, a Quirk in how the MacOS X updates windows, and, it provides an improved method (as compared to threads) of tying code to GUI events.

It doesn't apply to this problem because Sudoku can be solved significantly faster than a person can think (in my humble opinion). That being said, if your goal was to solve Sudoku faster, you would want to use threads, because you would want to directly use more than one processor.

[bear@bear scripts]$ time ./a.out ..1..4.......6.3.5...9.....8.....7.3.......285...7.6..3...8...6..92......4...1... 
[----------------------- Input  Data ------------------------]

*,*,1   *,*,4   *,*,*   
*,*,*   *,6,*   3,*,5   
*,*,*   9,*,*   *,*,*   

8,*,*   *,*,*   7,*,3   
*,*,*   *,*,*   *,2,8   
5,*,*   *,7,*   6,*,*   

3,*,*   *,8,*   *,*,6   
*,*,9   2,*,*   *,*,*   
*,4,*   *,*,1   *,*,*   

[----------------------- Solution 01 ------------------------]

7,6,1   3,5,4   2,8,9   
2,9,8   1,6,7   3,4,5   
4,5,3   9,2,8   1,6,7   

8,1,2   6,4,9   7,5,3   
9,7,6   5,1,3   4,2,8   
5,3,4   8,7,2   6,9,1   

3,2,7   4,8,5   9,1,6   
1,8,9   2,3,6   5,7,4   
6,4,5   7,9,1   8,3,2   


real    0m0.044s
user    0m0.041s
sys 0m0.001s

Answer 2

For one, since backtracking is a depth-first search it is not directly parallelizable, since any newly computed result cannot be used be directly used by another thread. Instead, you must divide the problem early, i.e. thread #1 starts with the first combination for a node in the backtracking graph, and proceeds to search the rest of that subgraph. Thread #2 starts with the second possible combination at the first and so forth. In short, for n threads find the n possible combinations on the top level of the search space (do not "forward-track"), then assign these n starting points to n threads.

However I think the idea is fundamentally flawed: Many sudoku permutations are solved in a matter of a couple thousands of forward+backtracking steps, and are solved within milliseconds on a single thread. This is in fact so fast that even the small coordination required for a few threads (assume that n threads reduce computation time to 1/n of original time) on a multi-core/multi-CPU is not negligible compared to the total running time, thus it is not by any chance a more efficient solution.