some OT: how to solve this kind of problem in our program?

[John Krukoff]

On Tue, 2006-12-26 at 17:39 -0300, Gabriel Genellina wrote:
> At Monday 25/12/2006 21:24, Paul McGuire wrote:
> 
> >For example, for all the complexity in writing Sudoku solvers, there are
> >fewer than 3.3 million possible permutations of 9 rows of the digits 1-9,
> >and far fewer permutations that match the additional column and box
> >constraints.  Why not just compute the set of valid solutions, and compare
> >an input mask with these?
> 
> Are you sure? There are 9!=362880 rows of digits 1-9; taking 9 of 
> these at random gives about 10**50 possibilities. Of course just a 
> few match the additional constraints. Maybe you can trivially reduce 
> them (just looking for no dupes on the first column) but anyway its a 
> laaaaarge number... (Or I'm wrong computing the possibilities...)
> 
> 
> -- 
> http://mail.python.org/mailman/listinfo/python-list

Fortunately, somebody has already written a paper on the subject:
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf

It looks like the number is actually rather large, and I'd expect even
with a specialized data structure for compression (probably some kind of
tree with bitwise digit packing?) would not fit in memory on any box I
own.

I would wonder if loading that much data isn't slower than solving the
puzzle.
-- 
John Krukoff <jkrukoff at ltgc.com>
Land Title Guarantee Company