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

"Gabriel Genellina" <gagsl-py@xxxxxxxxxxxx> wrote in message
news:mailman.2030.1167165642.32031.python-list@xxxxxxxxxxxxx
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


.

Relevant Pages

  • Re: some OT: how to solve this kind of problem in our program?
    ... fewer than 3.3 million possible permutations of 9 rows of the digits 1-9, ... few match the additional constraints. ...
    (comp.lang.python)
  • Re: some OT: how to solve this kind of problem in our program?
    ... fewer than 3.3 million possible permutations of 9 rows of the digits 1-9, ... Of course just a few match the additional constraints. ... Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! ...
    (comp.lang.python)
  • Re: Combinatorial design?
    ... A latin square can be thought of as a ... XxY to Z, from XxZ to Y, and YxZ to X. ... Z are called the constraints. ... be obtained from the other by applying permutations to ...
    (sci.math)
  • Re: some OT: how to solve this kind of problem in our program?
    ... >For example, for all the complexity in writing Sudoku solvers, there are ... >and far fewer permutations that match the additional column and box ... few match the additional constraints. ...
    (comp.lang.python)
  • [SUMMARY] Getting to 100 (#119)
    ... puts "#possible equations tested" ... they can come up in and Dennis chose to just hardcode those in the OPS constant. ... Dennis just counts off some number of digits from the front of the ... works by recursively combining smaller and smaller permutations until it has ...
    (comp.lang.ruby)