[Haskell-cafe] Sudoku Solver
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,
> We've got an SMP runtime for a reason, people!
I hacked up a parallel version of Richard Bird's function pearl solver:
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!
More information about the Haskell-Cafe