"Gabriel Genellina" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > 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...) > > > -- > Gabriel Genellina > Softlab SRL Der, I was thinking 9 times 362880, not 326880 P 9. Thanks for straightening me out!
10**50 was a good ballpark guess. My permutation calculator says that 362880 items taken 9 at a time yields 109099864394915605737486658299863377337267988480000 permutations (~10**50). I assume the smaller Wikipedia number (6.7*10**21) factors in the additional column and box constraints. So I guess we can rule out brute force as a viable strategy after all. -- Paul -- http://mail.python.org/mailman/listinfo/python-list
