[pm-h] Sudoku

Mike Flannigan mikeflan at earthlink.net
Sun Feb 12 07:11:52 PST 2006


Paul Archer wrote:

> I doubt it would take that long. A human can solve even a hard one in less
> than 20 minutes. Check out www.websudoku.com to play some.
>
> I figure the easiest way to solve a puzzle (from a programmatic point of
> view) is to mark all the possibilities for each square. Then, for the
> squares that only have one possibility, mark them as final. Then remove that
> number from the other squares. Repeat as necessary.
>
> Paul

I still haven't finished one yet, but from the little that I
have done I suspect the starting point is arranged such
that there is only one solution, or if not just one, then
under 10 or so.  So I guess it wouldn't take that long
to come up with all possible solutions.

On the one I am doing, 30 of the 82 squares already
have numbers.  So 52 square don't have numbers.  By
my calculations, there are only about - well never mind -
there are a huge number of possible combinations.  I
still say it's easy to find a solution, but to find all possible
solutions could be daunting.

I think the total number of possible solutions is up
around 1.5E12.  Maybe it's not that high, but that is
probably within 2 orders of magnitude

I see now that the websuboku site gives odds.  Real easy
puzzles have 4E9 combinations.  Really hard ones have
1E10 solutions.

It's interesting that some medium puzzles have 6E9
combination, while some "evil" puzzles only have
6E8 combinations.

They indicate that there is only one solution to each
puzzle.  Interesting.

I looked around some and this is the best page I found
on our topic:
http://www.americanscientist.org/template/AssetDetail/assetid/48550?&print=yes
I suspect we would use this article in our endeavor.
I suspect the project is still a big one.  We would
learn a lot doing it, but I don't know that we are
likely to complete the project.

Here is another, less valuable page:
http://forums.dreamincode.net/showtopic14486.htm


Mike




More information about the Houston mailing list