Solving the 4D Sudoku cube
I have just come back from a short break in Alnmouth, and where we were staying had a “4D Sudoku” puzzle. The website for this puzzle is long gone, the Twitter account has not been updated since 2011, there does not appear to be any solution anywhere on the internet. I was on my own.
The rules were:
- Every face of the cube had to have the digits 1 to 9;
- Every row and column of the cube had to have the digits 1 to 9;
- Every number on a face had to be aligned the same way up (6 and 9 are interchangeable for this purpose);
- Every internal face of the cube had to have the digits 1 to 9; and
- One face was almost a magic square (rows and columns, but not diagonals, sum to 15).
I did not really understand the rows/columns constraint, until I realised that nine of the cubes had one blank face, which must all be one face of the cube, letting us have six rows and six columns coming off that blank face.
I also realised that every cube was of a similar format – four digits the same way up around, a number on top and a number on the bottom either the same way round as on top or upside-down, but never at right angles. This meant every cube had to be the same way up in the solution, and the same way round (barring if the top and/or bottom was a 6 or 9, in which case it could be either way round).
This was enough to solve the bottom square (with the blank face), but there was more than one matching solution. I was only here a few days, and I didn’t want to waste all my holiday time trying various combinations. So instead, I wasted my holiday time writing a program to solve it for me ;)
The program I wrote was a straightforward brute force approach, layer by layer. While better than a permutation of all 27 cubes (well, 14 orange/13 white), it would have been much quicker to write a recursive script that added one cube at a time, which is something I realised/ wrote after my brute force one had already found the answer. But that is the one I will give below, no-one wants to see my slow inefficent use of itertools :)
We start with a couple of dataclasses to store the cubes and a particular layout:
@dataclass
class Cube:
top: int
front: int
right: int
back: int
left: int
bottom: int
def __str__(self):
return f'[{self.top} {self.front}-{self.right}-{self.back}-{self.left} {self.bottom}]'
@dataclass
class Layout:
cubes: list # 3D array, [x][y][z] measured from the back top left, with x right, y down, z towards
def _row(self, row):
square = (self.cubes[x][y][row] for y in range(3) for x in range(3))
return ' '.join(map(lambda x: str(x), square))
# This is how I visualised it, squares from the front to back
def __str__(self):
return self._row(2) + ' | ' + self._row(1) + ' | ' + self._row(0)
Then the initial creation of the 27 cubes was:
orange_cubes = []
white_cubes = []
# Back row (having the blanks on the back)
orange_cubes.append( Cube(1, 9, 6, 0, 4, 5) )
orange_cubes.append( Cube(5, 4, 9, 0, 2, 1) )
orange_cubes.append( Cube(9, 8, 4, 0, 9, 3) )
orange_cubes.append( Cube(6, 1, 2, 0, 7, 6) )
orange_cubes.append( Cube(3, 7, 9, 0, 7, 8) )
white_cubes.append( Cube(4, 3, 3, 0, 8, 6) )
white_cubes.append( Cube(3, 2, 7, 0, 5, 8) )
white_cubes.append( Cube(6, 5, 5, 0, 2, 7) )
white_cubes.append( Cube(5, 6, 1, 0, 1, 4) )
# Other two rows
orange_cubes.append( Cube(2, 4, 7, 8, 6, 4) )
orange_cubes.append( Cube(5, 1, 8, 5, 6, 6) )
orange_cubes.append( Cube(1, 6, 6, 2, 6, 8) )
orange_cubes.append( Cube(1, 4, 8, 8, 2, 3) )
orange_cubes.append( Cube(8, 2, 3, 7, 8, 7) )
orange_cubes.append( Cube(4, 8, 6, 7, 5, 7) )
orange_cubes.append( Cube(4, 3, 7, 6, 8, 4) )
orange_cubes.append( Cube(7, 2, 3, 1, 5, 6) )
orange_cubes.append( Cube(6, 3, 1, 7, 5, 2) ) # 1
white_cubes.append( Cube(8, 5, 8, 2, 3, 5) )
white_cubes.append( Cube(7, 1, 9, 5, 9, 2) )
white_cubes.append( Cube(6, 3, 2, 1, 7, 9) ) # 2
white_cubes.append( Cube(8, 9, 1, 9, 3, 5) )
white_cubes.append( Cube(2, 8, 4, 4, 1, 6) )
white_cubes.append( Cube(9, 7, 4, 3, 4, 1) ) # 3
white_cubes.append( Cube(3, 5, 1, 6, 4, 2) )
white_cubes.append( Cube(2, 9, 2, 9, 3, 1) )
white_cubes.append( Cube(7, 6, 5, 4, 9, 3) )
# alternates for 6/9 top/bottom
orange_cubes.append( Cube(9, 7, 5, 3, 1, 2) ) # 1
white_cubes.append( Cube(9, 1, 7, 3, 2, 9) ) # 2
white_cubes.append( Cube(6, 3, 4, 7, 4, 1) # 3
Realising towards the end a way to handle the cubes that could be spun 180 was to include their alternatives was a good step.
The main code is a recursive function, that loops through each co-ordinate:
def recurse(orange_cubes, white_cubes, layout, x, y, z):
# White cubes are all an odd number of steps away from the origin
col = 'white' if (x+y+z) % 2 else 'orange'
cubes = white_cubes if col == 'white' else orange_cubes
for cube in cubes:
if try_cube(layout, cube, x, y, z):
# This cube didn't conflict with anything, store it
layout.cubes[x][y][z] = cube
if x+y+z == 6:
# Reached end of cube, final checks of rows/columns
if check_columns(layout):
print(layout)
else:
# Move on to next spot, remove cube we've just used
nx, ny, nz = next_coord(x, y, z)
if col == 'white':
white_cubes = [c for c in white_cubes if c != cube]
else:
orange_cubes = [c for c in orange_cubes if c != cube]
recurse(orange_cubes, white_cubes, layout, nx, ny, nz)
# Put back the cube we used into the pool
if col == 'white':
white_cubes.append(cube)
else:
orange_cubes.append(cube)
# Remove the cube after trying it
layout.cubes[x][y][z] = 0
def next_coord(x, y, z):
x += 1
if x == 3:
x = 0
y += 1
if y == 3:
x = 0
y = 0
z += 1
if z == 3:
return -1, -1, -1
return x, y, z
We can kick the whole thing off with:
layout = Layout(cubes=[
[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ], # Left, empty
[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ], # Middle, empty
[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ], # Right, empty
])
recurse(orange_cubes, white_cubes, layout, 0, 0, 0)
Lastly, then, the actual checks themselves. We loop through the whole cube, and if we are in the same row/column/slice as the new cube, check the relevant faces of it to make sure they are different:
def try_cube(layout, cube, x, y, z):
# Back is blank
if z == 0:
if cube.back != 0: return False
for xx in range(3):
for yy in range(3):
for zz in range(3):
cc = layout.cubes[xx][yy][zz]
if not cc: continue
if xx == x:
if cc.left == cube.left: return False
if cc.right == cube.right: return False
if yy == y:
if cc.top == cube.top: return False
# Extra check here due to possible spun cubes
if cc.bottom == cube.bottom and \
not (cc.bottom in (6,9) and cube.bottom in (6,9)): return False
if zz == z:
if cc.front == cube.front: return False
if z > 0 and cc.back == cube.back: return False
return True
def check_columns(layout):
for i in range(3):
col = (*(layout.cubes[i][0][j].top for j in range(3)),
*(layout.cubes[i][j][2].front for j in range(3)),
*(layout.cubes[i][2][j].bottom for j in range(3)))
# Again, extra check here due to possible 6/9 confusion
if len(set(col)) < 8:
return False
if len(set(col)) == 8 and col.count(9) <= 1 and col.count(6) <= 1:
return False
row = (*(layout.cubes[0][i][j].left for j in range(3)),
*(layout.cubes[j][i][2].front for j in range(3)),
*(layout.cubes[2][i][j].right for j in range(3)))
if len(set(row)) != 9:
return False
return True
And here is the one solution (the almost magic square is in the fourth picture on the left):
