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

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@xxxxxxxx>
Land Title Guarantee Company

.

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, ... 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: 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, ... additional constraints. ... Gabriel Genellina ...
    (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)
  • Re: Recursive function to develop permutations
    ... the recursion in, then removing it by explicitly introducing a stack; ... definition of "permutations of length N out of a list of X values". ... This is like saying that (if the X values are digits in base X) the ... So, we have reduced the problem to one of counting in an arbitrary base, ...
    (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)