### Developers Club geek daily blog

2 years, 8 months ago
For new year purchased to the nephew a puzzle of Galakub. A task to collect a cube of 4х4х4 in size from different parts. Total amount of parts, just, 4х4х4. Before to give it was necessary to collect a puzzle. The beautiful symmetric solution was found quickly enough. But there was interestingly only this solution or not. The intuition prompted that the only thing, but there was a wish to check.

I decided to notch quickly a script for search of all options. It was ideally necessary to be in time before the New Year's speech of Putin. The situation was aggravated with the fact that the code was written on Makbuk my parents. To put on it some libraries is a task more abruptly, than to write the program.

The code turned out surprisingly beautiful and clear. It is convenient to explain it. Perhaps, the text will be useful, for example, studying the Python.

All detalk were presented in the form of tensors 4х4х4.
``````def zero_vector():
return [0] * 4

def zero_matrix():
return [zero_vector() for _ in xrange(4)]

def zero_tensor():
return [zero_matrix() for _ in xrange(4)]
``````

The cube is coded by the letter "Q", a corner — the letter "J", a flourish — "Z".

``````def parse_tensor(data):
tensor = zero_tensor()
lines = data.splitlines()
for z in xrange(2):
for y in xrange(4):
line = lines[z * 5 + 1 + y]
for x in xrange(4):
if line[x] == '*':
tensor[z][y][x] = 1
return tensor

J = parse_tensor("""
***.
*...
....
....

***.
*...
....
....

""")

Q = parse_tensor("""
**..
**..
....
....

**..
**..
....
....

""")

Z = parse_tensor("""
*...
*...
....
....

*...
***.
.**.
....

""")

>>> J
[[[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]
``````

More conveniently to look at tensors (and it will be necessary to look at them much and attentively), the show_tensor function the return was written to the parse_tensor function:
``````def show_tensor(tensor):
for y in xrange(4):
for z in xrange(4):
for x in xrange(4):
value = tensor[z][y][x]
print {
1: '*',
0: '.'
}[value],
print ' ',
print

def show_tensors(tensors):
for tensor in tensors:
show_tensor(tensor)
print

>>> show_tensors([J, Q, Z])
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * . .   * * . .   . . . .   . . . .
* * . .   * * . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* . . .   * . . .   . . . .   . . . .
* . . .   * * * .   . . . .   . . . .
. . . .   . * * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

Farther it was necessary to generate all possible provisions for each detalka. Rotation on an axis X and Y by 90 degrees is reduced to shift of axes.

``````def rotate_by_x(tensor):
rotated = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
rotated[z][y][x] = tensor[y][-z - 1][x]
return rotated

def rotate_by_y(tensor):
rotated = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
rotated[z][y][x] = tensor[x][y][-z - 1]
return rotated
``````

Not to duplicate cycles it is possible to start the transform_tensor function, it is useful still more than once:
``````def transform_tensor(tensor, function):
transformed = zero_tensor()
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
transformed[z][y][x] = function(tensor, x, y, z)
return transformed

def rotate_by_x(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[y][-z - 1][x])

def rotate_by_y(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[x][y][-z - 1])
``````

Let's look what turns out:
``````def apply_transformation(tensor, transformation, times=1):
for _ in xrange(times):
tensor = transformation(tensor)
return tensor

def show_transformation(tensor, transformation):
show_tensors([
tensor,
transformation(tensor),
apply_transformation(tensor, transformation, times=2),
apply_transformation(tensor, transformation, times=3),
apply_transformation(tensor, transformation, times=4),
])

>>> show_transformation(J, rotate_by_x)
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   * . . .   * * * .
. . . .   . . . .   * . . .   * * * .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   * . . .   * . . .
. . . .   . . . .   * * * .   * * * .

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
* * * .   * . . .   . . . .   . . . .
* * * .   * . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

>>> show_transformation(J, rotate_by_y)
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   * * . .   * * . .   * * . .
. . . .   . . . .   . . . .   * * . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   . * * *   . * * *
. . . .   . . . .   . . . *   . . . *
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . * *   . . * *   . . * *   . . . .
. . * *   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

Rotation on axis Z wonderfully can be received rotation on a x axis and Y. Only it is necessary to rotate in different directions therefore it is necessary to enter the direction into rotate_by_y:
``````def rotate_by_y(tensor, direction=1):
if direction == 1:
function = lambda _, x, y, z: _[x][y][-z - 1]
else:
function = lambda _, x, y, z: _[-x - 1][y][z]
return transform_tensor(tensor, function)

def rotate_by_z(tensor):
return rotate_by_y(rotate_by_x(rotate_by_y(tensor, direction=-1)))
``````

Let's look what turns out:

``````>>> show_transformation(J, rotate_by_z)
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . * *   . . * *   . . . .   . . . .
. . . *   . . . *   . . . .   . . . .
. . . *   . . . *   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . *   . . . *   . . . .   . . . .
. * * *   . * * *   . . . .   . . . .

. . . .   . . . .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
* * . .   * * . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

Well, except rotations there are still shifts. Having the transform_tensor function, it is very simple to make shift with transfer:
``````def shift_by_x(tensor):
return transform_tensor(tensor, lambda _, x, y, z: _[z][y][(x + 1) % 4])
``````

Problem only that there are nonexistent parts:
``````>>> show_transformation(J, shift_by_x)
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * . *   * * . *   . . . .   . . . .
. . . *   . . . *   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* . * *   * . * *   . . . .   . . . .
. . * .   . . * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. * * *   . * * *   . . . .   . . . .
. * . .   . * . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

Therefore the solution should be complicated. Let's do shift, only if there is a blank space under transfer. It is necessary to add a code for calculation of a projection of a tensor and check of a matrix on emptiness:
``````def project_tensor(tensor, function):
projection = zero_matrix()
for i in xrange(4):
for j in xrange(4):
projection[i][j] = function(tensor, i, j)
return projection

def project_by_x(tensor):
return project_tensor(tensor, lambda _, z, y: tensor[z][y][0])

def project_by_y(tensor):
return project_tensor(tensor, lambda _, z, x: tensor[z][0][x])

def project_by_z(tensor):
return project_tensor(tensor, lambda _, y, x: tensor[0][y][x])

def is_empty_matrix(matrix):
for i in xrange(4):
for j in xrange(4):
if matrix[i][j]:
return False
return True
``````

Now shift will look so:
``````def shift_by_x(tensor):
if is_empty_matrix(project_by_x(tensor)):
return transform_tensor(tensor, lambda _, x, y, z: _[z][y][(x + 1) % 4])
return tensor
``````

Now if the part rests against border, nothing occurs:
``````>>> show_transformation(J, shift_by_x)
* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * * .   * * * .   . . . .   . . . .
* . . .   * . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

The truth will not turn out to generate all possible parts. It is necessary to add still the direction and every time to do shifts in both parties. The final version is on Gitkhab.

It is good to receive all possible provisions for each part, it is necessary to touch all turning angles and all amount of shifts:
``````def generate_permutations(tensor):
for x_rotations in xrange(4):
for y_rotations in xrange(4):
for z_rotations in xrange(4):
for x_shifts in xrange(3):
for x_direction in (-1, 1):
for y_shifts in xrange(3):
for y_direction in (-1, 1):
for z_shifts in xrange(3):
for z_direction in (-1, 1):
permutation = apply_transformation(tensor, rotate_by_x, times=x_rotations)
permutation = apply_transformation(permutation, rotate_by_y, times=y_rotations)
permutation = apply_transformation(permutation, rotate_by_z, times=z_rotations)
permutation = apply_transformation(permutation, shift_by_x, direction=x_direction, times=x_shifts)
permutation = apply_transformation(permutation, shift_by_y, direction=y_direction, times=y_shifts)
permutation = apply_transformation(permutation, shift_by_z, direction=z_direction, times=z_shifts)
yield permutation
``````

Many combinations are duplicated. For example to rotate a cube it is useless, it does not add new combinations:
``````>>> Qs = list(generate_permutations(Q))
>>> show_tensors(sample(Qs, 10))
* * . .   * * . .   . . . .   . . . .
* * . .   * * . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

* * . .   * * . .   . . . .   . . . .
* * . .   * * . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. * * .   . * * .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. * * .   . * * .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. * * .   . * * .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

To leave only unique options, it is necessary to define function which puts number in compliance to a tensor. For this purpose it is possible to present a tensor 4х4х4 in the form of binary 64-bit number:
``````def hash_tensor(tensor):
hash = 0
index = 0
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
index += 1
hash += tensor[z][y][x] * 2 ** index
return hash
``````

Now unique combinations to leave simple:
``````def unique_tensors(tensors):
hashes = set()
for tensor in tensors:
hash = hash_tensor(tensor)
if hash not in hashes:
yield tensor

Zs = list(unique_tensors(generate_permutations(Z)))
Js = list(unique_tensors(generate_permutations(J)))
Qs = list(unique_tensors(generate_permutations(Q)))

>>> show_tensors(sample(Qs, 10))
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   * * . .   * * . .
. . . .   . . . .   * * . .   * * . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . * * .   . * * .
. . . .   . . . .   . * * .   . * * .

. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .

. . . .   . . . .   . * * .   . * * .
. . . .   . . . .   . * * .   . * * .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. . . .   . . . .   . . * *   . . * *
. . . .   . . . .   . . * *   . . * *
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .

. * * .   . * * .   . . . .   . . . .
. * * .   . * * .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
. . . .   . . . .   . . . .   . . . .
``````

Because the cube small, is not a lot of options:
``````>>> len(Zs), len(Js), len(Qs)
(288, 432, 27)
``````

The most primitive search of a solution could look so:
``````def solve(Zs, Js, Qs):
for Z1 in Zs:
for Z2 in Zs:
for Z3 in Zs:
for J1 in Js:
for J2 in Js:
for J3 in Js:
for Q1 in Qs:
for Q2 in Qs:
if not tensors_intersect(Z1, Z2, Z3, J1, J2, J3, Q1, Q2):
yield Z1, Z2, Z3, J1, J2, J3, Q1, Q2
``````

But it is too stupid, it will be necessary to touch 28834323272 options. The output is. After, for example, the first part is recorded, it is necessary to ignore all options in which the second part is crossed with the first. In a solution in a forehead it not so. Even if Z1 and Z2 are crossed, all other 6 subcycles will fulfill. The solution will be better to look so:
``````def solve_(path, done, hashes, todo):
for hash in hashes:
if not tensors_intersect(done, hash):
if todo:
for solution in solve_(path + [hash], union_hashes(done, hash), todo[0], todo[1:]):
yield solution
else:
yield path + [hash]

def solve(Zs, Js, Qs):
done = zero_tensor()
todo = [Z_hashes] * 3 + [J_hashes] * 3 + [Q_hashes] * 2
for solution in solve_([], done, todo[0], todo[1:]):
yield solution
``````

But there is one more nuance. The tensors_intersect function looks so:
``````def tensors_intersect(a, b):
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
if a[z][y][x] and b[z][y][x]:
return True
return False
``````

It works long. The output is again. Function which puts to a tensor in compliance number, is selected very successfully. If to operate with these numbers, but not tensors check on intersection will look so:
``````def tensor_hashes_intersect(a, b):
return a &b
``````

Search of solutions will a little change:
``````def union_tensor_hashes(a, b):
return a | b

def unhash_tensor(hash):
tensor = zero_tensor()
index = 0
for z in xrange(4):
for y in xrange(4):
for x in xrange(4):
index += 1
if hash &2 ** index:
tensor[z][y][x] = 1
return tensor

def solve_(path, done, hashes, todo):
for hash in hashes:
if not tensor_hashes_intersect(done, hash):
if todo:
for solution in solve_(path + [hash], union_tensor_hashes(done, hash), todo[0], todo[1:]):
yield solution
else:
yield path + [hash]

def solve(Zs, Js, Qs):
Z_hashes = [hash_tensor(_) for _ in Zs]
J_hashes = [hash_tensor(_) for _ in Js]
Q_hashes = [hash_tensor(_) for _ in Qs]
done = hash_tensor(zero_tensor())
todo = [Z_hashes] * 3 + [J_hashes] * 3 + [Q_hashes] * 2
for solution in solve_([], done, todo[0], todo[1:]):
yield [unhash_tensor(_) for _ in solution]
``````

We start:
``````solutions = list(solve(Zs, Js, Qs))
``````

We wait for six hours and we receive 576 solutions. Naturally there are a lot of duplicated. We leave only unique and we receive 8 options:
``````>>> show_tensors(unique_tensors(solution_tensor(_) for _ in solutions))
# # # *   # * * *   * * . .   * * . .
# # # *   # * * *   # * . .   # * . .
. . # #   . . * *   # * * *   # * * *
. . # #   . . # #   # # # #   # # * *

. . # #   . . # #   # # # *   # # # *
. . # #   . . * *   # * * *   # * * *
# # # #   # * * *   # * . .   * * . .
# # * *   # * * *   # * . .   * * . .

# # . .   # # . .   # # # #   * * # #
# # . .   * * . .   * * * #   * * * #
* # # #   * * * #   . . * #   . . * #
* # # #   * * * #   . . * *   . . * *

* * # #   * * * #   . . * #   . . * *
# # # #   * * * #   . . * #   . . * *
# # . .   * * . .   * * * #   * * * #
# # . .   # # . .   * # # #   * # # #

* * . .   # * . .   # * * *   # # * *
* * . .   # * . .   # * * *   # # # #
# * * *   # * * *   . . * *   . . # #
# # # *   # # # *   . . # #   . . # #

# # * *   # # # #   . . # #   . . # #
# * * *   # * * *   . . * *   . . # #
# * . .   # * . .   # * * *   # # # *
* * . .   * * . .   # * * *   # # # *

* # # #   * # # #   # # . .   # # . .
* * * #   * * * #   * * . .   # # . .
. . * *   . . * #   * * * #   # # # #
. . * *   . . * #   * * * #   * * # #

. . * *   . . * *   * * * #   * # # #
. . * #   . . * #   * * * #   * # # #
* * * #   * * * #   * * . .   # # . .
* * # #   # # # #   # # . .   # # . .
``````

Unfortunately all this possible rotations of that option which was found manually. That is Galakuba have only one solution.