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 <[EMAIL PROTECTED]> Land Title Guarantee Company -- http://mail.python.org/mailman/listinfo/python-list