Multidimensional Sudokus

Programs which generate, solve, and analyze Sudoku puzzles

Re: Multidimensional Sudokus

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

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


The box constraint in the 3rd dimension you're talking about is the container. If it wasn't clear, the container is a 3D version of a traditional "9x9" box.

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


In the [2, 2, 2], you're trying to fit the numbers 1-8 in each container and each span[0] (row), span[1] (column), and span[2]. Not 1-4. The length of each span is 8 and the size of the containers is 8, which makes 8 the relevant number for a [2, 2, 2].

If you look at an 8x8x1 slice of the [2, 2, 2], that wouldn't ever be a sudoku. And you're not guaranteed to (most likely not unless designed) find any valid [2, 2] "4x4" sudokus in the [2, 2, 2].

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


In a [2, 2, 1], since the third dimension is 1, this is a special case where you can get split the [2, 2, 1] sudoku at the third dimension and get 4 valid [2, 2] sudokus. You can't meaningfully transform a [2, 2] to a [2, 2, 2], or split a [2, 2, 2] into [2, 2] sudokus to get extra puzzles.
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Tue Mar 16, 2021 10:29 pm

So going from [2,2] to [2,2,2] does not keep the original sudoku?
Can you give some sample constraints? Like r1234c1 for a 4x4, but then use x1y1z1 (=span 0,1,2) notation.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Tue Mar 16, 2021 11:14 pm

creint wrote:So going from [2,2] to [2,2,2] does not keep the original sudoku?
Can you give some sample constraints? Like r1234c1 for a 4x4, but then use x1y1z1 (=span 0,1,2) notation.


I'm not completely sure what you mean by "sample constraints", but if I understand you correctly, then for a [2, 2, 2] sudoku, the constraints on:
    x1y1z1 would be: x(1-8)y1z1 (span[0]), x1y(1-8)z1 (span[1]), x1y1z(1-8) (span[2])
    the container it's in would be: x1y1z1, x1y1z2, x1y2z1, x1y2z2, x2y1z1, x2y1z2, x2y2z1, x2y2z2
    x2y5z8 would be: x(1-8)y5z8 (span[0]), x2y(1-8)z8 (span[1]), x2y5z(1-8) (span[2])
    the container it's in would be: x1y5z7, x1y5z8, x1y6z7, x1y6z8, x2y5z7, x2y5z8, x2y6z7, x2y6z8
    x4y3z7 would be: x(1-8)y3z7 (span[0]), x4y(1-8)z7 (span[1]), x4y3z(1-8) (span[2])
    the container it's in would be: x3y3z7, x3y3z8, x3y4z7, x3y4z8, x4y3z7, x4y3z8, x4y4z7, x4y4z8
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby Mathimagics » Wed Mar 17, 2021 6:33 am

Some observations about the 3D case ...

We usually call a set of N cells that has values 1 to N a house. So 9x9 Suduku has 81 cells, and 27 houses (9 rows, 9 cols, 9 boxes). Every cell belongs to (is contained in) 3 houses (a row, a col, a box).

Moving to 3 dimensions (a 9x9x9 cube) is conceptually straight-forward. We can visualise slicing the cube in any of the 3 dimensions, with each slice resulting in a 2D Sudoku grid. There are 729 cells, 486 houses (81 x-rows, 81 y-rows, 81 z-rows, 81 xy-boxes, 81, xz-boxes, 81 yz-boxes), and every cell belongs to 6 houses.

Constructing a DLX solver is basically a matter of defining the houses correctly, in theory anyway.

It seems to me that this model works as well for non-square boxes, eg 3x2, and thus sw478 has introduced an unnecessary complication by restricting his 3x2 boxes ("containers") to a particular orientation. In other words his cake can only be sliced along one axis.

Wouldn't a 3-way slicing model be better, for both presentation (valid Sudoku 3x2 on all faces), and also for computation (more constraints for each cell)?

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1802
Joined: 27 May 2015
Location: Canberra

Re: Multidimensional Sudokus

Postby sw478 » Wed Mar 17, 2021 7:34 am

Mathimagics wrote:It seems to me that this model works as well for non-square boxes, eg 3x2, and thus sw478 has introduced an unnecessary complication by restricting his 3x2 boxes ("containers") to a particular orientation.


I don't think it would be fair to call restricting containers to a particular orientation an "unnecessary complication". When you're creating a [3, 3, 1] "9x9x9" there are actually 6 possible orientations for the containers, but only looks like 3 since half of them are isomorphic to each other. As I stated in my first reply to this post, there are (n!) orientations for containers. For example, in a [4, 3, 2, 1] sudoku, there would be 12 orientations for the containers. Isomorphisms would exist if a container dimension length equaled another, like in a [3, 3, 1].

Creating a multidimension sudokus with more than one container orientation constraint is definitely doable, I just think that should just be considered a variant. For this variant, each cell would have n houses for each span and n! houses for each container orientation.

Mathimagics wrote:In other words his cake can only be sliced along one axis.


Again, you can't always slice a multidimensional sudoku to get a valid 2D sudoku from it.

sw478 wrote: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 » Wed Mar 17, 2021 6:56 pm

So [2,2,1] is an cube of 4x4 sudoku.
And [2,2,2] is an cube of 8x8 sudoku but this time it does not have box constraints but cube constraints.
Does it only have 2x8x(8row+8columns) and 4x4x4 cube constraints or am I still missing something?
This should not be that difficult to generate.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Wed Mar 17, 2021 9:42 pm

creint wrote:So [2,2,1] is an cube of 4x4 sudoku.
And [2,2,2] is an cube of 8x8 sudoku but this time it does not have box constraints but cube constraints.
Does it only have 2x8x(8row+8columns) and 4x4x4 cube constraints or am I still missing something?


The cube containers in a [2, 2, 2] have dimensions 2x2x2, not 4x4x4.
The [2, 2, 2] has 64 "2x2x2" cube constraints, 64 "8x1x1" span[0] constraints, 64 "1x8x1" span[1] constraints, and 64 "1x1x8" span[2] constraints.

creint wrote:This should not be that difficult to generate.


By all means, please do- my program is probably slower than most. The largest sudokus it can currently generate are solutions and puzzles of [3, 2, 1] and [2, 2, 1, 1, 1, 1], and it hasn't yet made solutions/puzzles for [4, 2, 1] or [2, 2, 2] yet.
Brief incomplete list of sudokus, sorted by estimated "hardness to generate", easiest first:
[2, 2]
[2, 2, 1]
[2, 2, 1, 1]
[2, 2, 1, 1, 1]
[3, 3]
[2, 2, 1, 1, 1, 1]
[6, 1, 1]
[4, 4]
[3, 2, 1]
[5, 5]
[4, 2, 1]
[2, 2, 2]
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Thu Mar 18, 2021 1:29 pm

Is this [2,2,2]?
Hidden Text: Show
Code: Select all
. . . . . 3 . .   . . . . . . . .   7 . . . . . . .   3 4 . 2 . . 5 .
. 5 . 7 . . 4 .   2 . . . . . 8 .   . . . 8 . . . .   . 2 . . . . . .
. . 5 . . . 1 .   3 . . . . . . .   . . . . . 3 . .   . . . . . 7 . .
. . . . . 2 . .   . . . . . . 7 .   . . . . . . 4 .   . . . 3 6 . . .
. . . . . . . 5   8 . 6 . . . . .   . . . 2 . . . .   . . . . . . . .
. . . . . . . 7   . . . . . . . .   . . . . 5 . 7 8   . . . . . . . .
. . . . . 8 5 .   7 . . 6 . . . .   4 . . . . . . 5   . . 6 . . 3 2 .
. . . 4 . . . .   . . . . 1 . . 4   . 1 . . . 5 . .   . 5 . 7 . . . .
                                                                     
. . . . . 1 . .   . . . . . . . .   5 . . . . . 3 .   . . . . . . . .
. . 6 . . . . .   . 3 . . . . . 5   . . . . . 4 . 2   . . . . . 8 . .
. . . . . . . .   . 2 . 4 . . . .   . . 8 . . . . .   2 . . . . 5 . 7
. . . 6 . . . .   . . . . 7 8 . .   . 7 6 . . . . .   . . . 1 . . . .
. . . . . . 8 .   . . . 7 2 . . 3   . . . 4 . . . .   . 6 . . . . . .
4 . . 1 . . . 5   . . . . . . . .   3 . . . 7 . . .   7 . . . . 4 1 2
1 . . . . . . .   . . . . . . 3 .   . . . . . 5 . 7   . . . . . . . .
. . . . . . . .   . . . 6 . . 1 .   . . . . 8 . . .   . . . . . . . .

Hidden Text: Show
Code: Select all
8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5   7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6
6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7   5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8
7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6   8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8   6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7
4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1   3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2
2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3   1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4
3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2   4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4   2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3
                                                                     
6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7   5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5   7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6
5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8   6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7
7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6   8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5
2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3   1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4
4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1   3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2
1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4   2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3
3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2   4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1


Dlx is not fast when you have many cells and only a few constraints.
SAT or other solvers can solve it very quickly
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby sw478 » Thu Mar 18, 2021 2:17 pm

creint wrote:Is this [2,2,2]?
Hidden Text: Show
Code: Select all
. . . . . 3 . .   . . . . . . . .   7 . . . . . . .   3 4 . 2 . . 5 .
. 5 . 7 . . 4 .   2 . . . . . 8 .   . . . 8 . . . .   . 2 . . . . . .
. . 5 . . . 1 .   3 . . . . . . .   . . . . . 3 . .   . . . . . 7 . .
. . . . . 2 . .   . . . . . . 7 .   . . . . . . 4 .   . . . 3 6 . . .
. . . . . . . 5   8 . 6 . . . . .   . . . 2 . . . .   . . . . . . . .
. . . . . . . 7   . . . . . . . .   . . . . 5 . 7 8   . . . . . . . .
. . . . . 8 5 .   7 . . 6 . . . .   4 . . . . . . 5   . . 6 . . 3 2 .
. . . 4 . . . .   . . . . 1 . . 4   . 1 . . . 5 . .   . 5 . 7 . . . .
                                                                     
. . . . . 1 . .   . . . . . . . .   5 . . . . . 3 .   . . . . . . . .
. . 6 . . . . .   . 3 . . . . . 5   . . . . . 4 . 2   . . . . . 8 . .
. . . . . . . .   . 2 . 4 . . . .   . . 8 . . . . .   2 . . . . 5 . 7
. . . 6 . . . .   . . . . 7 8 . .   . 7 6 . . . . .   . . . 1 . . . .
. . . . . . 8 .   . . . 7 2 . . 3   . . . 4 . . . .   . 6 . . . . . .
4 . . 1 . . . 5   . . . . . . . .   3 . . . 7 . . .   7 . . . . 4 1 2
1 . . . . . . .   . . . . . . 3 .   . . . . . 5 . 7   . . . . . . . .
. . . . . . . .   . . . 6 . . 1 .   . . . . 8 . . .   . . . . . . . .

Hidden Text: Show
Code: Select all
8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5   7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6
6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7   5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8
7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6   8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8   6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7
4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1   3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2
2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3   1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4
3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2   4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4   2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3
                                                                     
6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7   5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5   7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6
5 6 7 8 1 2 3 4   1 2 3 4 5 6 7 8   6 5 8 7 2 1 4 3   2 1 4 3 6 5 8 7
7 8 5 6 3 4 1 2   3 4 1 2 7 8 5 6   8 7 6 5 4 3 2 1   4 3 2 1 8 7 6 5
2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3   1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4
4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1   3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2
1 2 3 4 5 6 7 8   5 6 7 8 1 2 3 4   2 1 4 3 6 5 8 7   6 5 8 7 2 1 4 3
3 4 1 2 7 8 5 6   7 8 5 6 3 4 1 2   4 3 2 1 8 7 6 5   8 7 6 5 4 3 2 1


Yes, so this would be a valid [2, 2, 2].

creint wrote:Dlx is not fast when you have many cells and only a few constraints.
SAT or other solvers can solve it very quickly


I was able to solve it in minimal time with 512 calls to DLX, to me, that's fast enough.
I haven't found a good way to generate these yet though. Can I ask what method you used for generation? What's SAT?
sw478
 
Posts: 14
Joined: 10 March 2021

Re: Multidimensional Sudokus

Postby creint » Thu Mar 18, 2021 3:57 pm

Minisat, Sat4J, Gurobi can generate a solution.
Solvers for boolean satisfiability problems.
creint
 
Posts: 322
Joined: 20 January 2018

Re: Multidimensional Sudokus

Postby Mathimagics » Thu Mar 18, 2021 4:53 pm

SAT (see the wiki page) can solve a wider class of problems than DLX, which solves only exact-cover problems. But since we are dealing here exclusively with exact-cover problems, that aspect is not particularly important.

You might want to look at the SAT alternative if and when you reach a stage where your DLX solver is showing signs of stress ... and you really want to solve harder and/or bigger puzzles ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1802
Joined: 27 May 2015
Location: Canberra

Re: Multidimensional Sudokus

Postby sw478 » Thu Mar 18, 2021 8:01 pm

creint wrote:Minisat, Sat4J, Gurobi can generate a solution.
Solvers for boolean satisfiability problems.


Mathimagics wrote:SAT (see the wiki page) can solve a wider class of problems than DLX, which solves only exact-cover problems. But since we are dealing here exclusively with exact-cover problems, that aspect is not particularly important.

You might want to look at the SAT alternative if and when you reach a stage where your DLX solver is showing signs of stress ... and you really want to solve harder and/or bigger puzzles ...


Thanks, I'll check these out.
sw478
 
Posts: 14
Joined: 10 March 2021

Previous

Return to Software