The New Sudoku Players' Forum

[sw478]

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.

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

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

[creint]

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.

[sw478]

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

[Mathimagics]

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

[sw478]

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.

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.

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]

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.

[sw478]

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.

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]

[creint]

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

[sw478]

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

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?

[creint]

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

[Mathimagics]

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

[sw478]

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

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.