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

On 12/26/06, Gabriel Genellina <gagsl-py@xxxxxxxxxxxx> 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...)


According to Wikipedia, there are 6,670,903,752,021,072,936,960
possible classical Sudoku layouts. Ref.
http://www.research.att.com/~njas/sequences/A107739
.

Relevant Pages

  • Re: Innate vs. Learned
    ... A combination lock can be too complex which is of course ... complexity reduced to seven items by a process called chunking. ... Which only works if you pre-configure your brain to recognize the ... to solve for there are no constraints. ...
    (comp.ai.philosophy)
  • 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: Run time complexity for the global constraints in SICStus
    ... Today I went through the SICStus global ... constraints and came up with the following estimates: ... Time Complexity of SICStus Global Constraints ... Some complexity expressions are approximate. ...
    (comp.lang.prolog)
  • 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)