Nothing to worry about!!

Everything about Sudoku that doesn't fit in one of the other sections

Nothing to worry about!!

Postby QBasicMac » Fri Apr 07, 2006 7:23 pm

Imagine you take a SuDoku solution and rename the digits so that Box 1 is
123
456
789

You then shuffle columns 456 to get the digits "in order".
Same for columns 789.
Now swap, if necessary 456 with 789 so the r1c4=4.

Do the same with the rows so that r4c1=4.

You will obtain, for example

123 456 789
456 xxx xxx
789 xxx xxx

2xx xxx xxx
3xx xxx xxx
5xx xxx xxx

6xx xxx xxx
8xx xxx xxx
9xx xxx xxx

If we define Solution Class A,B as such a transformation where A is the values for r1c456 and B is the values for r456c1, then

Values for A (Solution class A,B)
456 457 458 459
467 468 469
478 479
489

Values for B (Solution class A,B)
235 236 238 239
256 258 259
268 269
289

This would give 100 solution classes.

Having picked a solution class, there are six cases of what goes into each of r2c456, r2c789, r3c456 and r3c789.

6*6*6*6 subclasses of Solution class A

It is more complicated in B, but probably the same number.

So total 12960x12960 = 167,961,600 Solution subclasses.

Lets look at a subclass of Solution Class (456, 235):

Code: Select all
+---------+----------------------+---------------------+
| 1  2  3 | 4       5      6     | 7      8      9     |
| 4  5  6 | 9       8      7     | 2      1      3     |
| 7  8  9 | 3       1      2     | 6      4      5     |
+---------+----------------------+---------------------+
| 2  6  1 | 578     3479   34589 | 34589  3579   478   |
| 3  9  4 | 125678  267    158   | 158    2567   12678 |
| 5  7  8 | 126     23469  1349  | 1349   2369   1246  |
+---------+----------------------+---------------------+
| 6  3  7 | 1258    249    14589 | 14589  259    1248  |
| 8  4  2 | 1567    3679   1359  | 1359   35679  167   |
| 9  1  5 | 2678    23467  348   | 348    2367   24678 |
+---------+----------------------+---------------------+


Find the cell with the most candidates: r5c4, and check each one:

r5c4=1 gives 443 solutions
r5c4=2 gives 412 solutions
r5c4=5 gives 348 solutions
r5c4=6 gives 363 solutions
r5c4=7 gives 443 solutions
r5c4=8 gives 518 solutions

My guess is that on average, each Solution Subclass has about that many solutions: 2,500

This would made the total unique solutions in SuDoku
167,961,600 x 2,500 = 419,904,000,000

Rounding off: 420,000,000,000

Now if you take one of the unique solutions as defined above, you can reverse the process (re-assign the digit values at random, shuffle legally the rows, columns, and triplets). This looks like another solution, but it is just a restatement of the unique solution.

OK, now suppose we take each unique solution and create a puzzle. We have a stack of 420,000,000,000 puzzles to solve.

I've heard some guys here brag they can solve puzzles in, say, 3 minutes (on average). Assuming such guys can keep it up 8 hours a day for 300 days per year, it looks like about 900,000 years. Whew! Just wanted to let you know there is no fear of solving all possible puzzles in the near future.

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: Nothing to worry about!!

Postby coloin » Fri Apr 07, 2006 8:16 pm

QBasicMac wrote:OK, now suppose we take each unique solution and create a puzzle. We have a stack of 420,000,000,000 puzzles to solve.


Your approximations do in some way go to show just how many grids there are. Lest there are be any doubters around.

However its much worse, leaving out the relabelling and box swapping row switching you can do to make equivalent grids, there is the small matter of the number of puzzles per grid.

The number of puzzles per individual grid, excluding symmetry, may well be more than 1,000,000. - and that would be for 24 clues. Exactly 25 clues would have a similar number. Adding non vital clues increases this even furthur.

I have an idea to count up / approximate the number of minimal puzzles for a single grid with 24 clues, but its a big job. !

C
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Re: Nothing to worry about!!

Postby QBasicMac » Fri Apr 07, 2006 9:17 pm

coloin wrote:there is the small matter of the number of puzzles per grid....1,000,000


Great! That means that even if a milllion gurus started working it would still take 900,000 years to finish them all.

I was getting a bit nervous, but no more. We will never run out.

(Well, with my memory, you could actually start recycling. I wouldn't notice I did it before. Especially if you rename the digits.

:D

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005


Return to General