The New Sudoku Players' Forum

[sw478]

Hi all,

I don't think I've been able to find sudokus of a higher dimension that aren't just 2D sudokus on the faces of a 3D surface, so I set out to write a program that can generate and solve sudokus that span multiple dimensions:

https://github.com/sw478/multidimensional-sudoku

It uses dancing links to solve, and a simple backtracking algorithm for generation. More details can be found in the readme.


It's based directly off of another sudoku program of mine:

https://github.com/sw478/sudoku

Both are still a work in progress so I'd like to know what you think of it!

Here's an album of all diagrams created so far:
https://imgur.com/a/qzXp2Ow

[creint]

Is it something like: http://www.realsudoku3d.com?
9*9*9 is 3d
If you have more dimensions, how much cells does do they have, where are the constraints?
If you cannot find them maybe it is because it's hard to visualize and hard to solve for a user.
My solver can already generate/solve/display those things.

[sw478]

If you have more dimensions, how much cells does do they have, where are the constraints?

The size/number of cells in each box (I call boxes containers), row, and column (I call rows and columns span) would be the product of all container dimensions, and the total number of cells in the sudoku is containerSize^n, where n is the number of dimensions. I define my sudokus by the container dimensions, so using a traditional "9x9" sudoku as an example, it would have dimensions of [3, 3].

So if you wanted to make a sudoku with dimensions [2, 3, 1], the containerSize would be 2*3*1 = 6 and the sudoku would look like a 6x6x6 cube with 6^3 number of cells. There would be (6^3)/6 containers and each container would look like a 2*3*1 rectangular prism. The numbers 1 through 6 would populate each container and each span. So there would be 1 type of constraint for the containers and n types of constraints for the spans.

Is it something like: http://www.realsudoku3d.com?

From what I'm able to see from that link, the sudoku in that game seems to be a version with dimensions [3, 3, 1], except with the added constraints that the 3x3x1 containers constrain the sudoku in all three orientations, so they have n constraints for the containers instead of just 1 in mine. I didn't implement that version of sudoku (containers that constrain the sudoku in all orientations possible) yet because the number of orientations is n!. I do see that as a possible path for my project, which is actually the reason for my last post.

If you cannot find them maybe it is because it's hard to visualize and hard to solve for a user.

I could imagine working on a user-friendly UI in the future for my project.

[creint]

Can you provide an example puzzle + solution? How does it look like, just a drawing could be helpful.

[sw478]

Here are some diagrams I made:

https://i.imgur.com/ZCenuaq.png

The figure in the top right would be a container, and as you can see, if you tile them together specifically, you get a tensor with equal length sides.

Here's a sample 3x2x1 puzzle with 21 clues:

https://i.imgur.com/ufpd4fa.png

I'm not completely sure how to use the feature for sharing puzzles, but I hope this works.

So for example, using the first diagram, you can see number at the cell:
span[0] = 5, span[1] = 1, span[2] = 0 would be 5.
span[0] = 4, span[1] = 3, span[2] = 2 would be 6.

Thanks for the feedback!

[creint]

I don't see how span[3] or higher would fit in here.
If you only support 3 dimensions then you could also write 5g1r2c6 : (span[0] = 5, span[1] = 1, span[2] = 0 would be 5.)
Do you have support for 5 instead of 6 grids in your 2x3 sample?

[sw478]

I don't see how span[3] or higher would fit in here.

If you have a [4, 3, 5, 2] sudoku, the containerSize would be 120 and sudokuSize would be 120^4 = 207,360,000. No one's ever going to make a sudoku that big but the concept still applies here. Along each of the 4 axes, the container would be tessellated. The side with the length 4 would be tessellated 3*5*2 times, the side with length 3 would be tessellated 4*5*2 times, and so on. You would end up with an equal length 4D tensor, length being 120.

You can see this in a 2x3 sudoku as well: the side with length 2 would be tessellated 3 times and the side with length 3 would be tessellated 2 times. You would end up with an equal length 2D tensor, length being 6.

If you only support 3 dimensions then you could also write 5g1r2c6 : (span[0] = 5, span[1] = 1, span[2] = 0 would be 5.)

I see, thanks. What does the 'g' stand for? Grid? Is there notation for span[3] at 4 dimensions? I want to say cube but 'c' is already taken haha.

Do you have support for 5 instead of 6 grids in your 2x3 sample?

I'm not completely sure what you mean. If you're talking about a 5x6x6 sudoku: If you remove one of the span[0] by span[1] grids from a 3x2x1 sudoku, you would technically still have 5 valid 2x3 sudoku grids but then the numbers along all the span[2] would be missing a number from the 1-6 range, so a 5x6x6 sudoku wouldn't be complete.

Also to note: you can only slice a portion of a higher dimensional sudoku and get valid lower dimensional sudokus only if the dimension you're slicing at is split into single units (length of the containers along that axis is 1). So it works with this 3x2x1 sudoku because you can get 6 valid 2x3 sudokus from slicing the cube along the span[2] axis, where the length of the container (dim[2]) is 1. Notice if you sliced the sudoku along span[0] or span[1], the resulting grids would still be latin squares, but the containers would be sliced apart, leaving no meaningful containers for the resulting grids. In the second diagram I made, I sliced the sudoku like that to show all the numbers, and I was only able to preserve the shape of the containers because of this fact.

[creint]

If you never use more than 3 dimensions then why does it support that?

4,4 with 2x2 boxes

1234
3412
2143
4321

With a new dimension 3 (g stands for grid), you always add size-1 new grids?
And then you only linked them on cell level g1234r1c1 and that for every cell.

If you add another dimension which 4 cells are then linked, and with which dimension..?
How much new grids does dimension 4 add?

Incomplete constraints like alldifferent on 5 cells with 6 candidates means that basic dlx does not work but you still can have a valid puzzle.

[mith]

8x8x8 with 2x2x2 boxes might be interesting

[1to9only]

I found these: 9*9*9 cube of 729 cells and 27 sudokus:
Tarek's Sudoku Cube puzzles (sudoku 3D sudoku3d)
Re-introducing The Sudoku Cube (3D sudoku, Sudoku3D, 9*9*9)

[sw478]

If you never use more than 3 dimensions then why does it support that?

I mean, nothing's stopping me from using sudokus with more dimensions?

With a new dimension 3 (g stands for grid), you always add size-1 new grids?
And then you only linked them on cell level g1234r1c1 and that for every cell.

If you add another dimension which 4 cells are then linked, and with which dimension..?
How much new grids does dimension 4 add?

A [2, 2] sudoku will have size (2*2)^2 = 16, 1 grid with dimensions of 4 rows 4 cols (4x4).
A [2, 2, 1] sudoku will have size (2*2*1)^3 = 64, 1 cube with dimensions (4x4x4), or 4 grids each with dimensions (4x4).
A [2, 2, 1, 1] sudoku will have size (2*2*1*1)^4 = 256, 1 hypercube with dimensions (4x4x4x4), or 4 cubes each with dimensions (4x4x4), or 16 grids each with dimensions (4x4).

When going from 3D to 4D, you're not just adding (containerSize - 1) extra grids for the new span[3], you're adding (containerSize - 1) number of cubes.

Incomplete constraints like alldifferent on 5 cells with 6 candidates means that basic dlx does not work but you still can have a valid puzzle.

There's never a case in multidimensional sudokus where you would have an incomplete constraint like that, it's always just x different numbers on x cells with x candidates for each span and box, where x is containerSize.

8x8x8 with 2x2x2 boxes might be interesting

Right now, [2, 2, 2] is actually too large for my program. [3, 2, 1] is the largest it can reliably generate. But solving? probably a better chance of doing so, but I'd have to generate one first.

I found these: 9*9*9 cube of 729 cells and 27 sudokus:

It looks like this also implements the same idea in http://www.realsudoku3d.com that creint mentioned earlier where it's a [3, 3, 1] with extra constraints due to the extra container orientations.

[creint]

Hidden Text: Show

Code: Select all

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
                                     
. . . .   . . . .   . . . .   . . . .
. . . .   . 1 . .   . . . .   . . . .
. . . .   1 . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
                                     
. . . .   . . . .   . . . .   . . 2 .
. . . .   . . . .   . . . .   . . . .
. 4 . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . 3 . .
                                     
. . . .   4 . . .   . . . 4   . . . .
. . . .   3 . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . 4 .

-> dimension 3
| dimension 4

Hidden Text: Show

Code: Select all

1 4 2 3   2 3 1 4   3 1 4 2   4 2 3 1
2 3 1 4   1 4 2 3   4 2 3 1   3 1 4 2
3 1 4 2   4 2 3 1   1 4 2 3   2 3 1 4
4 2 3 1   3 1 4 2   2 3 1 4   1 4 2 3
                                     
2 1 3 4   3 4 2 1   4 2 1 3   1 3 4 2
3 4 2 1   2 1 3 4   1 3 4 2   4 2 1 3
4 2 1 3   1 3 4 2   2 1 3 4   3 4 2 1
1 3 4 2   4 2 1 3   3 4 2 1   2 1 3 4
                                     
4 3 1 2   1 2 4 3   2 4 3 1   3 1 2 4
1 2 4 3   4 3 1 2   3 1 2 4   2 4 3 1
2 4 3 1   3 1 2 4   4 3 1 2   1 2 4 3
3 1 2 4   2 4 3 1   1 2 4 3   4 3 1 2
                                     
3 2 4 1   4 1 3 2   1 3 2 4   2 4 1 3
4 1 3 2   3 2 4 1   2 4 1 3   1 3 2 4
1 3 2 4   2 4 1 3   3 2 4 1   4 1 3 2
2 4 1 3   1 3 2 4   4 1 3 2   3 2 4 1

Here one generated with dlx (rated easy), can you confirm this is a 4d 4x4 sudoku?
So constraints are based on only cell level and for every dimension that is added all cells from previous dimension are used for constraints again.
Adding more dimensions will just copy it 3 times to the right or down.

What is difference between [2,2,2] and [2,2,1] and [2,2,2,2] and [2,2,2,1] and what does [2,2,>2]?

[sw478]

Here one generated with dlx (rated easy), can you confirm this is a 4d 4x4 sudoku?

I just checked it with my program, this is a valid [2, 2, 1, 1] sudoku.
A [2, 2, 2, 2] doesn't have side lengths = 4. It's not just 16 "4x4" ([2,2]) sudokus stacked together.

Calling it a 4d 4x4 sudoku isn't descriptive enough. I don't prefer calling the sudokus from those links "9x9x9" 3D sudokus. It doesn't adequately describe how the containers are laid out. A [4, 3, 2] sudoku would have the same sudokuSize (24^3) as a [8, 3, 1], [12, 2, 1], [6, 4, 1], or [24, 1, 1] sudoku, all of them would look like a 24x24x24 cube, but all of them would have distinct solution counts.

So constraints are based on only cell level and for every dimension that is added all cells from previous dimension are used for constraints again.
Adding more dimensions will just copy it 3 times to the right or down.

You could stack sudokus of a lower dimension together to create a higher dimensional sudoku, but the new dimension would always have to be 1.
You can't create a full [3, 3] traditional sudoku from gluing 8 extra [9] 1D sudokus onto 1 single [9] 1D sudoku without modifying the container dimensions.

You could start with a 1D sudoku of length 9, this would be a [9] sudoku. There would be one type of span, span[0], which is just the row with length 9. There are no columns or any other types of span. The only container is of size 9 and it takes the same shape as the row, 9x1. You could stack 8 more of these rows onto it, add constraints for the columns, and you would end up with a valid [9, 1] sudoku, a 9x9 latin square. The rows and columns have the same constraints as a [3, 3] sudoku, but the containers still have dimensions 9x1, not 3x3. You would have to change the constraints of a [9, 1] container to a [3, 3] container.

What is difference between [2,2,2] and [2,2,1] and [2,2,2,2] and [2,2,2,1] and what does [2,2,>2]?

[2, 2, 2]:
n = 3
containerSize = 2*2*2 = 8
sudokuSize = 8^3 = 512
appearance: a 8x8x8 cube.
There would be (512/8 = 64) number of containers, span[0]s, span[1]s, and span[2]s.
container appearance: a 2x2x2 cube.

[2, 2, 1]:
n = 3
containerSize = 2*2*1 = 4
sudokuSize = 4^3 = 64
appearance: a 4x4x4 cube.
There would be (64/4 = 16) number of containers, span[0]s, span[1]s, and span[2]s.
container appearance: a 2x2x1 rectangular prism.

[2, 2, 2, 2]:
n = 4
containerSize = 2*2*2*2 = 16
sudokuSize = 16^4 = 65,536
appearance: a 16x16x16x16 hypercube.
There would be (65,536/16 = 4,096) number of containers, span[0]s, span[1]s, span[2]s, and span[3]s.
container appearance: a 2x2x2x2 hypercube.

[2, 2, 2, 1]:
n = 4
containerSize = 2*2*2*1 = 8
sudokuSize = 8^4 = 4096
appearance: a 8x8x8x8 hypercube.
There would be (4096/8 = 512) number of containers, span[0]s, span[1]s, span[2]s, and span[3]s.
container appearance: a 2x2x2x1 rectangular hypercube.

For something like [2, 2, >2]:
[2, 2, a]:
n = 3
containerSize = 2*2*a = 4a
sudokuSize = (4a)^3 = 64a^3
appearance: a (4a)x(4a)x(4a) cube.
There would be ((64a^3)/(4a) = (16a^2)) number of containers, span[0]s, span[1]s, span[2]s, and span[3]s.
container appearance: a 2x2xa rectangular prism.

This relates to why [2, 2, 1] is not the same as [2, 2].
If a = 0, the tensor doesn't exist in that dimension, so the sudoku would just be a [2, 2] sudoku, so [2, 2] is the same as [2, 2, 0], [2, 2, 0, 0], [2, 2, 0, ..., 0].

For the example you provided:

[2, 2, 1, 1]:
n = 4
containerSize = 2*2*1*1 = 4
sudokuSize = 4^4 = 256
appearance: a 4x4x4x4 hypercube.
There would be (256/4 = 64) number of containers, span[0]s, span[1]s, span[2]s, and span[3]s.
container appearance: a 2x2x1x1 rectangular hypercube.

Bonus:

[3, 3, 3]:
n = 3
containerSize = 3*3*3 = 27
sudokuSize = 27^3 = 19,683
appearance: a 27x27x27 cube.
There would be (19,683/27 = 729) number of containers, span[0]s, span[1]s, and span[2]s.
container appearance: a 3x3x3 cube.

[sw478]

Here are some more diagrams:

Layout for a [2, 2, 2] sudoku:
https://i.imgur.com/S1mBWH9.png

Layout for a [4, 3, 2, 1] sudoku:
https://i.imgur.com/BIFwpaO.png

[creint]

Yes that is an 8x8, but strangely I see box constraints in the 3rd dimension.
It is now unclear because you cannot fit 1-4 in a row 8 cells. Where are the constraints?
In your picture I see now box constraints in the 3rd dimension.
[2,2,] but somewhere it get transformed into a 4x4 puzzle. [3,3] = 9x9
[2,2,1] gives 3 extra puzzles = 1 cube, [2,2,2] gives 31 extra puzzles = 8 cubes, [2,2,3] gives 107 extra puzzles = 27 cubes. But I still don't see how they are linked.