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

[Paul McGuire]

"Gabriel Genellina" <gagsl-py at yahoo.com.ar> wrote in message 
news:mailman.2030.1167165642.32031.python-list at python.org...
> 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