The New Sudoku Players' Forum

by **dukuso** » Sun Jul 10, 2005 11:53 am

I estimate there are about 9e14 3*3*9 sudokugrids.
If someone wants the exact number - I can send the program
which needs about 3hours.
This is just simple backtracking. With a clever grouping into
classes as in the 9*9 case this can be done much faster
but also harder to implement.

Why is the number smaller than the number of 9*9 grids ?
Simply because we have 36 constraints here to contain {1,2,..,9}
while with the normal sudoku there are only 27.

Now the number of 3*3*9 sudokus can be used to estimate
or even compute the number of 3*9*9 sudokus and this
can be used to estimate the number of 9*9*9 sudokus

by **dukuso** » Sun Jul 10, 2005 1:53 pm

thinking again...

statistically there should be no 3d-sudoku at all.
Too many constraints.
We have 9*9 rows, 9*9 columns, 9*9 piles and 9*9*3 blocks
of size 1*3*3. That's 54*9 subsets of the cells which all
must contain {1,2,..,9}
I calculate there should be about 10^(-50) solutions.
Can someone confirm ?

Probably 50 clues would be sufficient in the puzzle at
http://www.sudoku.org.uk/extreme.htm

by **dukuso** » Mon Jul 11, 2005 12:07 pm

you can start with any sudokugrid as level 1 and than produce
a 3d-sudoku by cyclically shifting in Z_3 for the other levels.

I tried to obfuscate this a bit by rotating and swapping
2 elements in a cycle.
So, here is my best 3d.grid, as unsymmetrical as possible:

265941387
173268945
894753216
357826491
942135678
681479532
728594163
416382759
539617824

948537162
652419873
731682459
816794325
573268914
429351786
395176248
287945631
164823597

317826594
489375621
526194738
294513867
168947253
735682149
641238975
953761482
872459316

652419873
731682459
948537162
573268914
429351786
816794325
287945631
164823597
395176248

489375621
526194738
317826594
168947253
735682149
294513867
953761482
872459316
641238975

173268945
894753216
265941387
942135678
681479532
357826491
416382759
539617824
728594163

526194738
317826594
489375621
735682149
294513867
168947253
872459316
641238975
953761482

894753216
265941387
173268945
681479532
357826491
942135678
539617824
728594163
416382759

731682459
948537162
652419873
429351786
816794325
573268914
164823597
395176248
287945631

---------------------

the chutes are from classes :

23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37
23 42 37 , 37 10 37

35 35 35 , 1 1 1
35 35 35 , 1 1 1
35 35 35 , 1 1 1
33 33 33 , 1 1 1
33 33 33 , 1 1 1
33 33 33 , 1 1 1
33 33 33 , 1 1 1
33 33 33 , 1 1 1
33 33 33 , 1 1 1

38 38 38 , 1 1 1
38 38 38 , 1 1 1
38 38 38 , 1 1 1
37 37 37 , 1 1 1
37 37 37 , 1 1 1
37 37 37 , 1 1 1
36 36 36 , 1 1 1
36 36 36 , 1 1 1
36 36 36 , 1 1 1

----------------------------------------

This looks still rather regular, but a small improvement
versus the chutes in the Daily-Telegraph puzzle
which were from classes :

11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1
11 11 11 , 1 1 1

11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2
11 11 11 , 2 2 2

1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2
1 1 1 , 2 2 2

---------------------------

by **dukuso** » Tue Jul 12, 2005 8:25 am

is there a solver, which can solve 3d-sudokus ?
Preferrably one which can be run from DOS-batch-file
with commandline arguments and which prints the number
of solutions to a file or to stdout and stops after
2 solutions.
Then we can make a nice 3d-puzzle, better than the cube
from the Telegraph, by deleting entries
until the left clues guarantee a unique solution

by **RFB** » Tue Jul 12, 2005 9:57 am

Shortly after its first appearance several people repored that they had adapted 2D solvers to work on the 3D puzzle - check the forums at http://www.sudoku.org.uk/cgi-bin/discus/discus.cgi?pg=topics

If you do create your own 3D puzzles you will need to check that you are not infringing the patents that have been applied for.

by **dukuso** » Tue Jul 12, 2005 1:05 pm

RFB wrote:Shortly after its first appearance several people repored that they had adapted 2D solvers to work on the 3D puzzle - check the forums at http://www.sudoku.org.uk/cgi-bin/discus/discus.cgi?pg=topics

I found no solver there, but I think I can do it using Knuth's dancing links
program.I'll try to post a 3d-puzzle tomorrow.

RFB wrote:If you do create your own 3D puzzles you will need to check that you are not infringing the patents that have been applied for.

how can creating "my own" 3d-puzzle (and posting it) ever violate any patents ??
Something should be wrong with patent laws, if it would.

by **dukuso** » Tue Jul 12, 2005 5:56 pm

Sorry, I had a bug , so the now deleted 3d-puzzle was nonsense.
Well, nobody complained, so probably not so many people
read it or even tried to solve it. When someone is still
interested, I could try to make a new 3d-sudoku puzzle.

by **sciguy47** » Sun Jul 17, 2005 2:51 pm

cjlt wrote:I already published a 4 dimensional variant.

It's partially 4D, but to be fully 4d you need disjoint rows and columns

Disjoint rows:

a a a | d d d | g g g
b b b | e e e | h h h
c c c | f f f | i i i
------+-------+------
a a a | d d d | g g g
b b b | e e e | h h h
c c c | f f f | i i i
------+-------+------
a a a | d d d | g g g
b b b | e e e | h h h
c c c | f f f | i i i

Disjont columns:
turn the fist grid 90 degrees.

by **AndrewTaylor** » Wed Jul 20, 2005 10:33 am

dukuso wrote:statistically there should be no 3d-sudoku at all.
Too many constraints.
We have 9*9 rows, 9*9 columns, 9*9 piles and 9*9*3 blocks
of size 1*3*3. That's 54*9 subsets of the cells which all
must contain {1,2,..,9}
I calculate there should be about 10^(-50) solutions.
Can someone confirm ?

It seems likely to me that what you've actually found is the fraction of candidate solutions that actually work. If you imagine there are 9*9*9=729 cells then can each contain any of nine figures, that gives 4*10^695 candidates. If 10^-50 of them work that still leaves massively more viable Dion Cubes than there are atoms in the universe.

That sounds like a lot, but we do know there is at least one, and that's already a lot more than 10^-50.

Or, you could do a far simpler 3D Su Doku.

by **Chree55** » Sat Jul 23, 2005 8:27 am

I finally finished the dion cube about a week after I started. I tried doing it on paper and just kept making tiny mistakes in one of the 729 squares that I couldn't get past it on paper. So I made a Ti-83 calculator program that could display the cube slice by slice on all 3 planes and that I could use to edit the cube and solve it. Not really a solver program, more like a tool to help me more quickly find the solution.

I'm going to be using much of the same code to write a program for general sudoku puzzles so I can take them with me wherever I go.

by **Condor** » Mon Aug 08, 2005 11:52 pm

Lardarse wrote:So likely the limit is Bertram^3 ?

Edit: Mis-read your formula. Maybe it's Bertram for a 3x3x3 cube...

Sorry Lardarse, I should have got back sooner to explain things. So here is my overdue reply.

In an attempt to explain what I was trying to say a bit clearer, please consider the following first 3 slices of a Dion Cube as shown here:

Code: Select all: A B C . . . . . . X X X . . . . . . X X X . . . . . . D E F . . . . . . X X X . . . . . . X X X . . . . . . G H I . . . . . . X X X . . . . . . X X X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

This shows 1 block with the position of the digits placed in one slice represented by the letters A - I. What I was trying to say was with the first slice determined there is only 40 ways to place the remaining digits in the other 18 places of the block, as represented by the X's.

From previous analysis I found that there is only 40 disjoint sets, which can be grouped into 3 unique types.

With 9 blocks in the top 3 slices that is 40^9 ways to fill in the second and third slices if one ignores rows and columns. For the whole Dion Cube it is ([Bertram] * 40^9)^3.

Here are the 40 arrangements based on the disjoint sets in the 3 unique groups.

Code: Select all: Type A: #1 #14 #40 #27 ABC IGH EFD ABC HIG FDE ABC EFD IGH ABC FDE HIG DEF CAB HIG DEF BCA IGH DEF HIG CAB DEF IGH BCA GHI FDE BCA GHI EFD CAB GHI BCA FDE GHI CAB EFD Type B: #10 #11 #16 #39 ABC FGE HID ABC IGH EFD ABC HFG IDE ABC EFD HIG DEF IAH BCG DEF BCA HIG DEF BIA CGH DEF IGH CAB GHI CDB EFA GHI FDE CAB GHI ECD FAB GHI BCA FDE #8 #26 #33 #15 ABC IFD EGH ABC FDG HIE ABC EGH IFD ABC HIE FDG DEF HAG CIB DEF ICH BGA DEF CIB HAG DEF BGA ICH GHI BCE FDA GHI EAB CFD GHI FDA BCE GHI CFD EAB #4 #36 #28 #23 ABC HIG FDE ABC EID FGH ABC FDE IGH ABC IDH EFG DEF CAB IGH DEF HCG IAB DEF HIG BCA DEF CGB HIA GHI EFD BCA GHI BFA CDE GHI CAB EFD GHI FAE BCD Type C: #9 #12 #32 #29 ABC IGE HFD ABC HIG EFD ABC HFD IGE ABC EFD HIG DEF CAH BIG DEF BCA IGH DEF BIG CAH DEF IGH BCA GHI FDB ECA GHI FDE CAB GHI ECA FDB GHI CAB FDE #6 #19 #34 #20 ABC IGD EFH ABC HDG FIE ABC EGD IFH ABC HDE FIG DEF HAB CIG DEF ICA BGH DEF HIB CAG DEF IGA BCH GHI FCE BDA GHI EFB CAD GHI FCA BDE GHI CFB EAD #2 #31 #30 #25 ABC HIG EFD ABC HID FGE ABC EFD IGH ABC IDE HFG DEF CAB IGH DEF BCG IAH DEF HIG BCA DEF CGH BIA GHI FDE BCA GHI EFA CDB GHI CAB FDE GHI FAB ECD #3 #17 #38 #24 ABC IGH FDE ABC EIG FDH ABC FDE IGH ABC FDH EIG DEF CAB HIG DEF HCA IGB DEF HIG CAB DEF IGB HCA GHI EFD BCA GHI BFD CAE GHI BCA EFD GHI CAE BFD #7 #21 #35 #22 ABC IFH EGD ABC FIG HDE ABC EFH IGD ABC FIE HDG DEF CAG HIB DEF BCH IGA DEF CIG HAB DEF BGH ICA GHI BDE FCA GHI EAD CFB GHI BDA FCE GHI CAD EFB #5 #13 #18 #37 ABC FGH EID ABC IGH FDE ABC EFG IDH ABC FDE HIG DEF IAB HCG DEF BCA HIG DEF HIA CGB DEF IGH CAB GHI CDE BFA GHI EFD CAB GHI BCD FAE GHI BCA EFD

To understand the sets note - each letter represents a different digit. The letters show the position of the digits within the block.

by **Lardarse** » Thu Aug 11, 2005 3:27 pm

Very useful. But I still don't exactly understand which units are are supposed to follow the sudoku rule of "only 1 of each number", neither in the original puzzle, nor in your explaination.

LA

by **Condor** » Mon Aug 15, 2005 2:12 am

Lardarse wrote:Very useful. But I still don't exactly understand which units are are supposed to follow the sudoku rule of "only 1 of each number", neither in the original puzzle, nor in your explaination.

LA

A 9x9x9 cube (also known as a Dion Cube) is made up of 27 normal sudokus, each of which has 9 rows, 9 columns, and 9 boxes in which the digits 1 to 9 must be placed once. 3 boxes in a row is called a band, and 3 boxes in a column is called a stack.

I stated that for the sake of completeness, must readers of this forum will already be familiar with those terms.

When we look at a Dion Cube there is another entity worth considering. This is a 3x3x3 cube. It is made up of 9 boxes. More importantly it has the same boundaries as the boxes it is composed of.

I refer to this as a block in my postings to distinguish it from a box. In normal 2-D sudokus it may not be as important, but I think we need to be more careful with Dion cubes. I hope other people will do the same.

A Dion Cube has 27 blocks arranged in a 3x3x3 pattern. Each block has the digits 1 to 9 occurring 3 times. This may be the thing that confused you in my previous posting.

To show all the boxes in a block I will use disjoint set #1. I chose this set because all 27 blocks in the Dion Cube puzzle at www.sudoku.org.uk was this one. First the complete arrangement:

#1
ABC IGH EFD
DEF CAB HIG
GHI FDE BCA

And now each box:

ABC ... ...
DEF ... ...
GHI ... ...

... IGH ...
... CAB ...
... FDE ...

... ... EFD
... ... HIG
... ... BCA

ABC IGH EFD
... ... ...
... ... ...

... ... ...
DEF CAB HIG
... ... ...

... ... ...
... ... ...
GHI FDE BCA

A.. I.. E..
D.. C.. H..
G.. F.. B..

.B. .G. .F.
.E. .A. .I.
.H. .D. .C.

..C ..H ..D
..F ..B ..G
..I ..E ..A

Looking at each box you will see that all the letters A to I are used once.

Looking at the Dion Cube, we see in the boxes that the rows have the digits in 3 triplets 254, 196, 873 and just cycled each triplet around with the digits in that order. Likewise, the columns had these triplets 218, 597, 463 - also just cycling them. Likewise, across the slices the triplets were 239, 586 and 471. This is a characteristic of a Type A block.

There is 2 reasons why I have made postings about blocks in this thread.

1 This can help anyone who would like to work out the number of possible Dion Cubes. First, ignoring blocks:
[Bertram]^9 = 2.602,717,775 * 10^196

And now taking blocks into account:
([Bertram] * 40^9)^3 = 5.338,617,336 * 10^108

2 To help anyone who would like to make a Dion Cube with a far less predictable pattern.

BTW, at the www.sudoku.org.uk website forum people are making the same complaint about the cycling of the digits.

by **Condor** » Mon Nov 14, 2005 4:00 am

This posting is in response to a posting in Fruitless Sudoku Discoveries. I consider it more appropiate here.

To understand this posting you will need to read my posting on naming templates first.

By knowing the template name, the possible templates for that digit in the other 2 slices in the group can be worked out. The groups being slices 1-3, or 4-6, or 7-9.

The permutation numbers are divided into 2 groups. The groups are 1 4 5 and 2 3 6.

The process is to change all the permutation numbers to one of the others in the groups mentions above. To show this, I will use the template 315264 and write it with the other 2 permutation numbers in the group below it.

315264
241321
654635

There is 2 choices for each digit giving a total of 64 possible templates. So a possible template for slice 2 is 254331. The remaining digits makes up the template name for the third slice - 641625.

To show this, I will use the first 3 slices of dusuko's 3D cube reproduced here. (horozontally)

Code: Select all: 265 941 387 948 537 162 317 826 594 173 268 945 652 419 873 489 375 621 894 753 216 731 682 459 526 194 738 357 826 491 816 794 325 294 513 867 942 135 678 573 268 914 168 947 253 681 479 532 429 351 786 735 682 149 728 594 163 395 176 248 641 238 975 416 382 759 287 945 631 953 761 482 539 617 824 164 823 597 872 459 316

Now by blanking out all but one of the digits, the templates can be identified easily. For the first digit I will reproduce the template names vertically to make it eaiser to see.

Code: Select all: ... ..1 ... ... ... 1.. .1. ... ... 1.. ... ... ... .1. ... ... ... ..1 ... ... .1. ..1 ... ... ... 1.. ... ... ... ..1 .1. ... ... ... .1. ... ... 1.. ... ... ... .1. 1.. ... ... ..1 ... ... ... ..1 ... ... ... 1.. ... ... 1.. ... 1.. ... ..1 ... ... .1. ... ... ... ... ..1 ... ..1 ... ... .1. ... 1.. ... ... ... ... .1. 365245 624651 231314 365245 624651 231314 2.. ... ... ... ... ..2 ... .2. ... ... 2.. ... ..2 ... ... ... ... .2. ... ... 2.. ... ..2 ... .2. ... ... ... .2. ... ... ... .2. 2.. ... ... ..2 ... ... ... 2.. ... ... ... 2.. ... ... ..2 .2. ... ... ... ..2 ... .2. ... ... ... ... 2.. ... 2.. ... ... ..2 ... 2.. ... ... ... ... ..2 ... ... .2. ... .2. ... ..2 ... ... 131212 565646 424353 ... ... 3.. ... .3. ... 3.. ... ... ..3 ... ... ... ... ..3 ... 3.. ... ... ..3 ... .3. ... ... ... ... .3. 3.. ... ... ... ... 3.. ... ..3 ... ... .3. ... ..3 ... ... ... ... ..3 ... ... .3. ... 3.. ... .3. ... ... ... ... ..3 3.. ... ... ... .3. ... ... 3.. ... ... ... .3. ..3 ... ... .3. ... ... ... ..3 ... ... ... 3.. 516461 452534 143125 ... .4. ... .4. ... ... ... ... ..4 ... ... .4. ... 4.. ... 4.. ... ... ..4 ... ... ... ... 4.. ... ..4 ... ... ... 4.. ... ..4 ... ..4 ... ... .4. ... ... ... ... ..4 ... .4. ... ... 4.. ... 4.. ... ... ... ... .4. ... ..4 ... ... ... .4. .4. ... ... 4.. ... ... ... .4. ... ... ... 4.. ... ... ..4 ..4 ... ... ... 4.. ... 453633 146322 512266 ..5 ... ... ... 5.. ... ... ... 5.. ... ... ..5 .5. ... ... ... ..5 ... ... .5. ... ... ... .5. 5.. ... ... .5. ... ... ... ... ..5 ... 5.. ... ... ..5 ... 5.. ... ... ... ... .5. ... ... 5.. ... .5. ... ..5 ... ... ... 5.. ... ..5 ... ... ... ... ..5 ... ... .5. ... ..5 ... .5. ... ... 5.. ... ... ... ... 5.. ... .5. ... 214654 351315 645241 .6. ... ... ... ... .6. ... ..6 ... ... .6. ... 6.. ... ... ... ... 6.. ... ... ..6 ... 6.. ... ..6 ... ... ... ..6 ... ..6 ... ... ... ... .6. ... ... 6.. ... .6. ... .6. ... ... 6.. ... ... ... ... ..6 ... 6.. ... ... ... .6. ... ..6 ... 6.. ... ... ..6 ... ... ... ... 6.. ... .6. ... ... 6.. ... .6. ... ... ... ... ..6 145354 514215 451641 ... ... ..7 ... ..7 ... ..7 ... ... .7. ... ... ... ... .7. ... .7. ... ... 7.. ... 7.. ... ... ... ... 7.. ..7 ... ... ... 7.. ... ... ... ..7 ... ... .7. .7. ... ... ... ..7 ... ... .7. ... ... ... 7.. 7.. ... ... 7.. ... ... ... .7. ... ... ... .7. ... ... 7.. ..7 ... ... ... 7.. ... ... ..7 ... ... ... ..7 .7. ... ... 522516 433143 166452 ... ... .8. ..8 ... ... ... 8.. ... ... ..8 ... ... ... 8.. .8. ... ... 8.. ... ... ... .8. ... ... ... ..8 ... 8.. ... 8.. ... ... ... ... 8.. ... ... ..8 ... ..8 ... ..8 ... ... .8. ... ... ... ... .8. ... .8. ... ..8 ... ... ... ... ..8 ... ..8 ... ... .8. ... .8. ... ... ... ... .8. ... ... 8.. ... 8.. ... 8.. ... ... 641145 215451 354514 ... 9.. ... 9.. ... ... ... ... .9. ... ... 9.. ... ..9 ... ..9 ... ... .9. ... ... ... ... ..9 ... .9. ... ... ... .9. ... .9. ... .9. ... ... 9.. ... ... ... ... 9.. ... 9.. ... ... ..9 ... ..9 ... ... ... ... ..9 ... .9. ... .9. ... ... ... ... 9.. ... ... ..9 ... 9.. ... 9.. ... ... ..9 ... ... ... ... .9. ... ..9 ... 454321 141264 515635

The New Sudoku Players' Forum

3 D puzzle

Re: 4 D