This all started when I was looking for new kinds of puzzles for Mads Føk, the students magazine at Natural Sciences at Aarhus University. I was talking to some friends waiting for the revue, when we started talking about puzzles in higher dimensions. Eventually, we got to sudokus, and I thought that a 3-dimensional sudoku might be possible. So Magnus, Natascha, Viktor, and Jonas, if you read this: thank you very much for the inspiration.
Highlevel description
I’ll assume you know the rules of sudoku. For simplicity and computational tractability, we will restrict ourselves to 4x4, and eventually 4x4x4, sudokus. Suppose you have 4 sudokus, each 4x4. You can stack these on top of each other to create a 4x4x4 cube of numbers. If you take each horizontal slice out of this cube, it will be a valid 4x4 sudoku. However, there are more ways to take a 4x4 slice out of a 4x4x4 cube. You can take the front face of the cube or any of the layers behind it. In Julia, if we have a 4x4x4 array of numbers, the possible dimensions become clearer:
sudoku = reshape([
1, 2, 3, 4,
3, 4, 1, 2,
2, 1, 4, 3,
4, 3, 2, 1,
4, 3, 2, 1,
2, 1, 4, 3,
3, 4, 1, 2,
1, 2, 3, 4,
3, 1, 2, 4,
4, 2, 3, 1,
1, 3, 2, 4,
2, 4, 1, 3,
2, 4, 1, 3,
1, 3, 4, 2,
4, 2, 3, 1,
3, 1, 4, 2
], (4, 4, 4))
first_axis(i) = sudoku[:, :, i]
second_axis(i) = sudoku[:, i, :]
third_axis(i) = sudoku[i, :, :]
For example,
julia> third_axis(i)
4×4 Matrix{Int64}:
1 4 3 2
3 2 4 1
2 3 1 4
4 1 2 3
gives the slice whose columns are the first column of each layer above.
We define a 3-dimensional 4x4x4 sudoku to be a 4x4x4 array of numbers, such that first_axis(i), second_axis(i) and third_axis(i) are all valid 4x4 sudokus for all i in 1:4. The question is now, does 3-dimensional sudokus even exist?
Constructing 3-dimensional sudokus
The answer is yes, 3-dimensional sudokus do exist. You can see an example above. There has been some prior art in this area. Vegard Hanssen made some 3D sudokus of various sizes here. These have been turned into a game. However, I was unable to find any code he might have used to build them, so I got to write a script to generate them.
To do this, we can modify a sudoku solver to take the new constraints into account. I won’t bore you with the details, but the implementation is available here. It is based on the classic sudoku solver by Peter Norvig. The following piece of code finds all the cells that any given cell can see:
squares = reshape(1:4*4*4, 4, 4, 4)
rows = [squares[i, j, :] for i in 1:4 for j in 1:4]
cols = [squares[i, :, j] for i in 1:4 for j in 1:4]
fils = [squares[:, i, j] for i in 1:4 for j in 1:4]
subs = vcat([vec(squares[2*i-1:2*i, 2*j-1:2*j, k]) for i in 1:2 for j in 1:2 for k in 1:4] ,
[vec(squares[2*i-1:2*i, j, 2*k-1:2*k]) for i in 1:2 for j in 1:4 for k in 1:2] ,
[vec(squares[i, 2*j-1:2*j, 2*k-1:2*k]) for i in 1:4 for j in 1:2 for k in 1:2] )
unitlist = collect(chain(rows, cols, fils, subs))
units = [filter(u -> s in u, unitlist) for s in squares]
peers = [Set(vcat(map(collect, units[s])...)) for s in squares]
for (i, p) in enumerate(peers)
pop!(p, i)
end
and from there the logic of Norvig’s solver is unchanged.
Interesting discoveries
Spoiler alert: this section contains a discovery, that will make it almost trivial to solve 4x4x4 sudokus. I highly recommend that you have a go at solving a puzzle first. Otherwise, this fun intellectual challenge will forever be lost to you. You can find three puzzles in (this pdf)[https://www.madsfoek.dk/udgivelser/51-2.pdf] on page 27. I’ll wait right here until you get back.
I wanted to know what the minimum number of clues needed to make a 4x4x4 sudoku with a unique solution is. The puzzles made by Hanssen seemed to contain redundant clues. We can try to have the computer do this for us, by generating a random puzzle, and then removing clues until the solution is no longer unique. The search function from my code will find all valid solutions, so it can be used to check this. In this way, I found puzzles with 6 clues. However, if you try using the assign! function to manually create a puzzle, you will quickly make a fun discovery: on an empty board, setting a single cell will uniquely determine the value of another cell. It’s [spooky action at a distance)[https://en.wikipedia.org/wiki/Quantum_entanglement]!
To see this, let’s consider a 2x2x2 corner of the cube, and let’s place a 1 in one corner of the 2x2x2 cube. Now, three cells are touching the 1 along a face, so those cannot contain a 1 now. There are also three more cells, which are on the same plane as the 1 along different axes, so those cannot contain a 1 either. This means that out of the 8 cells in the cube, one of them contains a 1, and 6 of them cannot contain a 1. But each digit needs to appear two times in the 8 cells, so there is one cell remaining, which must also contain a 1.
With this observation, it was relatively simple to create a puzzle with only 4 given clues. I think this a neat example, where fuzzing the problem by trying random stuff didn’t work, and a bit of human insight solved the problem.
Generating 9x9x9 puzzles
After a while, you realize that 4x4x4 puzzles aren’t that interesting. They are a lot more interesting than 4x4 sudokus, but once you find the system, you’re done. The next logical step is 9x9x9 sudokus. Unfortunately, this gives us 729 cells, which is more than can fit on a printed page and is too big for my solver. I think a 9x9x9 sudoku would be quite a project to solve, perhaps to the point where you lose interest. I did find this StackExchange answer, which describes a more direct way to construct a 9x9x9 sudoku from a much simpler 3x3x3 sudoku. While it is very cool that such a construction exists, many possible puzzles cannot be generated in this way. Unfortunately, my solver is not nearly performant enough to explore this space. I tried coding up a solver in Z3, hoping that the magic of SAT solvers could save me, but it was also too slow.
Alright, that’s about it for this experiment. If you have any thoughts, feel free to shoot me a message on LinkedIn