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.
Solution of a puzzle of Galakub on the Python

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".
Solution of a puzzle of Galakub on the Python
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.
Solution of a puzzle of Galakub on the Python
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:
Solution of a puzzle of Galakub on the Python
>>> 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
        hashes.add(hash)


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.

This article is a translation of the original post at habrahabr.ru/post/274527/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus