[Haskell-cafe] Sudoku Solver

Wouter Swierstra wss at cs.nott.ac.uk
Sat Aug 18 14:05:04 EDT 2007


> I'm a little surprised no one's tried a parallel solution yet,  
> actually.
> We've got an SMP runtime for a reason, people!

I hacked up a parallel version of Richard Bird's function pearl solver:

http://www.haskell.org/sitewiki/images/1/12/SudokuWss.hs

It not really optimized, but there are a few neat tricks there.  
Rather than prune the search space by rows, boxes, and columns  
sequentially, it represents the sudoku grid by a [[TVar [Int]]],  
where every cell has a TVar [Int] corresponding to the list of  
possible integers that would 'fit' in that cell. When the search  
space is pruned, we can fork off separate threads to prune by  
columns, rows, and boxes -- the joy of STM!

   Wouter


More information about the Haskell-Cafe mailing list