## 3 D puzzle

Everything about Sudoku that doesn't fit in one of the other sections
I estimate there are about 9e14 3*3*9 sudokugrids.
If someone wants the exact number - I can send the program
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
dukuso

Posts: 479
Joined: 25 June 2005

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
Last edited by dukuso on Sat Jul 16, 2005 4:27 pm, edited 4 times in total.
dukuso

Posts: 479
Joined: 25 June 2005

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

---------------------------
dukuso

Posts: 479
Joined: 25 June 2005

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
dukuso

Posts: 479
Joined: 25 June 2005

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.
RFB

Posts: 43
Joined: 03 April 2005

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.
dukuso

Posts: 479
Joined: 25 June 2005

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.
dukuso

Posts: 479
Joined: 25 June 2005

### Re: 4 D

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.
sciguy47

Posts: 9
Joined: 17 July 2005

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.
AndrewTaylor

Posts: 2
Joined: 20 July 2005

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.
Chree55

Posts: 1
Joined: 23 July 2005

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

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              #27ABC IGH EFD      ABC HIG FDE      ABC EFD IGH      ABC FDE HIGDEF CAB HIG      DEF BCA IGH      DEF HIG CAB      DEF IGH BCAGHI FDE BCA      GHI EFD CAB      GHI BCA FDE      GHI CAB EFDType B:#10              #11              #16              #39ABC FGE HID      ABC IGH EFD      ABC HFG IDE      ABC EFD HIGDEF IAH BCG      DEF BCA HIG      DEF BIA CGH      DEF IGH CABGHI CDB EFA      GHI FDE CAB      GHI ECD FAB      GHI BCA FDE#8               #26              #33              #15ABC IFD EGH      ABC FDG HIE      ABC EGH IFD      ABC HIE FDGDEF HAG CIB      DEF ICH BGA      DEF CIB HAG      DEF BGA ICHGHI BCE FDA      GHI EAB CFD      GHI FDA BCE      GHI CFD EAB#4               #36              #28              #23ABC HIG FDE      ABC EID FGH      ABC FDE IGH      ABC IDH EFGDEF CAB IGH      DEF HCG IAB      DEF HIG BCA      DEF CGB HIAGHI EFD BCA      GHI BFA CDE      GHI CAB EFD      GHI FAE BCDType C:#9               #12              #32              #29ABC IGE HFD      ABC HIG EFD      ABC HFD IGE      ABC EFD HIGDEF CAH BIG      DEF BCA IGH      DEF BIG CAH      DEF IGH BCAGHI FDB ECA      GHI FDE CAB      GHI ECA FDB      GHI CAB FDE#6               #19              #34              #20ABC IGD EFH      ABC HDG FIE      ABC EGD IFH      ABC HDE FIGDEF HAB CIG      DEF ICA BGH      DEF HIB CAG      DEF IGA BCHGHI FCE BDA      GHI EFB CAD      GHI FCA BDE      GHI CFB EAD#2               #31              #30              #25ABC HIG EFD      ABC HID FGE      ABC EFD IGH      ABC IDE HFGDEF CAB IGH      DEF BCG IAH      DEF HIG BCA      DEF CGH BIAGHI FDE BCA      GHI EFA CDB      GHI CAB FDE      GHI FAB ECD#3               #17              #38              #24ABC IGH FDE      ABC EIG FDH      ABC FDE IGH      ABC FDH EIGDEF CAB HIG      DEF HCA IGB      DEF HIG CAB      DEF IGB HCAGHI EFD BCA      GHI BFD CAE      GHI BCA EFD      GHI CAE BFD#7               #21              #35              #22ABC IFH EGD      ABC FIG HDE      ABC EFH IGD      ABC FIE HDGDEF CAG HIB      DEF BCH IGA      DEF CIG HAB      DEF BGH ICAGHI BDE FCA      GHI EAD CFB      GHI BDA FCE      GHI CAD EFB#5               #13              #18              #37ABC FGH EID      ABC IGH FDE      ABC EFG IDH      ABC FDE HIGDEF IAB HCG      DEF BCA HIG      DEF HIA CGB      DEF IGH CABGHI 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.
Last edited by Condor on Wed Nov 02, 2005 12:04 am, edited 1 time in total.
Condor

Posts: 62
Joined: 19 June 2005

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
Lardarse

Posts: 106
Joined: 01 July 2005

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.

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.
Condor

Posts: 62
Joined: 19 June 2005

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 594173 268 945    652 419 873    489 375 621894 753 216    731 682 459    526 194 738357 826 491    816 794 325    294 513 867942 135 678    573 268 914    168 947 253681 479 532    429 351 786    735 682 149728 594 163    395 176 248    641 238 975416 382 759    287 945 631    953 761 482539 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         2313143652456246512313142.. ... ...    ... ... ..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. ... ...    ... ... ..6145354         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`
Condor

Posts: 62
Joined: 19 June 2005

Previous