Multidimensional Sudokus

Programs which generate, solve, and analyze Sudoku puzzles

Multidimensional Sudokus

Postby sw478 » Fri Mar 12, 2021 5:58 pm

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
Last edited by sw478 on Tue Mar 16, 2021 7:25 pm, edited 1 time in total.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Sat Mar 13, 2021 8:57 am

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.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Sat Mar 13, 2021 11:53 am

creint wrote: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.

creint wrote: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.

creint wrote: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.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Sat Mar 13, 2021 8:48 pm

Can you provide an example puzzle + solution? How does it look like, just a drawing could be helpful.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Sun Mar 14, 2021 3:22 pm

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!
Last edited by sw478 on Tue Mar 16, 2021 7:24 pm, edited 2 times in total.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Sun Mar 14, 2021 10:33 pm

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?
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Mon Mar 15, 2021 8:04 am

creint wrote: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.

creint wrote: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.

creint wrote: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.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Mon Mar 15, 2021 6:06 pm

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.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby mith » Mon Mar 15, 2021 6:58 pm

8x8x8 with 2x2x2 boxes might be interesting
mith
 
Posts: 577
Joined: 14 July 2020

Re: Multidimensional Sudokus

Postby 1to9only » Mon Mar 15, 2021 9:01 pm

1to9only
 
Posts: 3244
Joined: 04 April 2018

Re: Multidimensional Sudokus

Postby sw478 » Tue Mar 16, 2021 6:23 am

creint wrote: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?

creint wrote: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.

creint wrote: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.

mith wrote: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.

1to9only wrote: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.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Tue Mar 16, 2021 9:35 am

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]?
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Tue Mar 16, 2021 12:38 pm

creint wrote: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
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby sw478 » Tue Mar 16, 2021 3:18 pm

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
Last edited by sw478 on Tue Mar 16, 2021 7:25 pm, edited 2 times in total.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Tue Mar 16, 2021 6:04 pm

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.
creint
 
Posts: 322
Joined: 20 January 2018

Next

Return to Software