04.01.2016 18:03
alexkuku 30 22000 Источник
На новый год купил племяннику головоломку Галакуб. Задача собрать из разных деталей куб размером 4х4х4. Суммарный объём деталей, как раз, 4х4х4. Прежде, чем дарить надо было собрать головоломку. Красивое симметричное решение нашлось достаточно быстро. Но стало интересно единственное это решение или нет. Интуиция подсказывала, что единственное, но хотелось проверить.


Я решил по-быстрому запилить скрипт для перебора всех вариантов. В идеале нужно было успеть до новогодней речи Путина. Ситуация усугублялась тем, что код писался на Макбуке моих родителей. Поставить на него какие-то библиотеки — это задача покруче, чем написать саму программу.

Код получился на удивление красивый и понятный. Его удобно объяснять. Может быть, текст будет полезен, например, изучающим Питон.

Все детальки представлялись в виде тензоров 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)]


Кубик кодируется буквой «Q», уголок — буквой «J», загогулина — «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]]]

Чтобы удобнее смотреть на тензоры (а смотреть на них нужно будет много и внимательно), была написана функция show_tensor обратная функции parse_tensor:
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])
* * * .   * * * .   . . . .   . . . .  
* . . .   * . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  

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

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

Дальше нужно было сгенерировать все возможные положения для каждой детальки. Вращение по оси Х и Y на 90 градусов сводятся к перестановке осей.

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

Чтобы не дублировать циклы можно завести функцию transform_tensor, она пригодится ещё не раз:
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])

Посмотрим что получается:
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)
* * * .   * * * .   . . . .   . . . .  
* . . .   * . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  

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

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

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

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

Вращение по оси Z удивительным образом можно получить вращением по оси X и Y. Только вращать надо в разные стороны, поэтому в 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)))

Посмотрим, что получается:

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

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

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

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

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

Хорошо, кроме вращений есть ещё сдвиги. Имея функцию transform_tensor, сделать сдвиг с переносом очень просто:
def shift_by_x(tensor):
    return transform_tensor(tensor, lambda _, x, y, z: _[z][y][(x + 1) % 4])

Проблема только в том, что возникают несуществующие детали:
>>> show_transformation(J, shift_by_x)
* * * .   * * * .   . . . .   . . . .  
* . . .   * . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  

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

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

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

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

Поэтому решение придётся усложнить. Будем делать сдвиг, только если есть пустое место под перенос. Нужно добавить код для вычисления проекции тензора и проверки матрицы на пустоту:
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

Теперь сдвиг будет выглядеть так:
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

Теперь если деталь упирается в границу, ничего не происходит:
>>> show_transformation(J, shift_by_x)
* * * .   * * * .   . . . .   . . . .  
* . . .   * . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  

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

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

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

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

Правда не получится сгенерировать все возможные детали. Нужно добавить ещё направление и каждый раз делать сдвиги в обе стороны. Финальная версия есть на Гитхабе.

Хорошо, чтобы получить все возможные положения для каждой детали, нужно перебрать все углы поворота и все размеры сдвигов:
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

Много комбинаций дублируется. Например, кубик вращать бесполезно, новых комбинаций это не добавляет:
>>> Qs = list(generate_permutations(Q))
>>> show_tensors(sample(Qs, 10))
* * . .   * * . .   . . . .   . . . .  
* * . .   * * . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   . . . .   . . . .  

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

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

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

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

Чтобы оставить только уникальные варианты, надо определить функцию, которая ставит в соответствие тензору число. Для этого можно представить тензор 4х4х4 в виде двоичного 64-битного числа:
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

Теперь оставить уникальные комбинации просто:
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))
. . . .   . . . .   . . . .   . . . .  
. . . .   . . . .   * * . .   * * . .  
. . . .   . . . .   * * . .   * * . .  
. . . .   . . . .   . . . .   . . . .  

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

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

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

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

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

За счёт того, что кубик небольшой, вариантов не так много:
>>> len(Zs), len(Js), len(Qs)
(288, 432, 27)

Самый примитивный поиск решения мог бы выглядеть так:
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

Но это слишком тупо, нужно будет перебрать 28834323272 вариантов. Выход есть. После того как, например, зафиксирована первая деталь, нужно игнорировать все варианты, в которых вторая деталь пересекается с первой. В решении в лоб это не так. Даже если Z1 и Z2 пересекаются, все остальные 6 подциклов отработают. Решение получше будет выглядеть так:
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

Но есть ещё один нюанс. Функция tensors_intersect выглядит так:
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

Она работает долго. Выход опять есть. Функция, которая ставит тензору в соответствие число, выбрана очень удачно. Если оперировать этими числами, а не тензорами проверка на пересечение будет выглядеть так:
def tensor_hashes_intersect(a, b):
    return a & b

Поиск решений немного изменится:
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]

Запускаем:
solutions = list(solve(Zs, Js, Qs))

Ждём шесть часов и получаем 576 решений. Естественно много дублирующихся. Оставляем только уникальные и получаем 8 вариантов:
>>> show_tensors(unique_tensors(solution_tensor(_) for _ in solutions))
# # # *   # * * *   * * . .   * * . .  
# # # *   # * * *   # * . .   # * . .  
. . # #   . . * *   # * * *   # * * *  
. . # #   . . # #   # # # #   # # * *  

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

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

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

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

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

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

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

К сожалению это все возможные вращения того самого варианта, которое было найдено вручную. То есть у Галакуба есть только одно решение.

Комментарии (30)


  1. Daniyar94
    04.01.2016 21:20
    #8725649
    +2

    Похоже на проблему типа Dynamic Programming


    1. A1ien
      05.01.2016 00:04
      #8725779

      Интуитивно — похоже, но вот как выделить функцию задачи которую уже можно было бы решать методом динамического прогаммированния — мне пока не очевидно.


      1. r4nd0m
        05.01.2016 18:55
        #8726349

        Если вы про целевую функцию, то можно взять незаполненный объём и минимизировать его до нуля. Или заполненный объём в пределах кубика, и максимизировать его до объёма кубика. Или минимизировать количество оставшихся фигур до нуля при условии невыхода за границу кубика.


  1. andy_p
    04.01.2016 23:17
    #8725751
    +2

    Преобразуем в задачу SAT и не надо ждать 6 часов.


    1. semenyakinVS
      04.01.2016 23:58
      #8725777
      +1

      Интересно. Это вот это имеется в виду? Можете чуть детальнее рассказать как можно было решить задачу вашим методом?


      1. andy_p
        05.01.2016 01:30
        #8725817
        +3

        Очень просто. Каждое возможное положение каждой фигуры обозначаете одной булевской переменной. Затем записываете уравнения конфликтов между пересекающимися фигурами. Потом, поскольку каждая фигура встречается один раз — конфликты между вариантами фигур одного типа и, наконец, по одному уравнению для каждой фигуры, которое говорит, что должен присутствовать хотя-бы один вариант. Сохраняете это в файл cnf, скачиваете какой-нибудь SAT солвер и получаете решение. Затем добавляете уравнение, исключающее данное решение, запускаете SAT солвер еще раз и получаете другое решение. И так до тех пор, пока решения существуют.


        1. semenyakinVS
          05.01.2016 01:43
          #8725829

          А не выйдет то же решение, что и у автора статьи, просто выполненное SAT-солвером?.. Вообще, если честно, пока с трудом пониманию о чём речь. Если будет время — напишите пример как могут выглядеть эти уравнения.


          1. andy_p
            05.01.2016 23:02
            #8726517

            Ну, например, уравнение (которое на самом деле называется клозом), того, что вариант 1 для одной фигуры не может быть одновременно с вариантом 2 для другой фигуры (то есть они пересекаются):

            (not x1) or (not x2) = 1


        1. guyfawkes
          05.01.2016 17:20
          #8726237

          А что вы подразумеваете под «конфликтами»?


          1. andy_p
            05.01.2016 22:57
            #8726513

            Когда две фигуры пересекаются.


  1. Ambassadorik
    04.01.2016 23:33
    #8725763
    +1

    Пост заставил меня задуматься, что решение такой «простенькой» задачки, заняло бы у меня несколько месяцев :(


    1. KvanTTT
      05.01.2016 01:35
      #8725821

      На Питоне?


  1. Wesha
    05.01.2016 00:50
    #8725799

    К сожалению это все возможные вращения того самого варианта, которое было найдено вручную. То есть у Галакуба есть только одно решение.
    Так человек в очередной раз качеством вычислений задавил компьютерное количество.


    1. semenyakinVS
      05.01.2016 01:09
      #8725807

      Но теперь есть метод, которым можно решить любую подобную задачу… Кстати, любопытно — можно играть на скорость с компьютером в сборку подобных головоломок.


    1. Ghool
      07.01.2016 01:50
      #8727969
      +1

      так задачи были разные.
      У человека изначально стояла одна задача — найти решение.

      А у компьютера (если быть точным, у программиста) стояла другая задача — узнать, возможны ли другие решения.
      При чём это не «найти ещё одно решение» — ведь человек может бесконечно думать и не находить другого решения, но это не будет значить, что его нет.


  1. KvanTTT
    05.01.2016 01:56
    #8725833
    -5

    Почему-то мне кажется, что задача решает за секунды, видимо не все у вас оптимизировано. Хотя может это такой Питон.


  1. vovkasolovev
    05.01.2016 06:02
    #8725889

    Можете, пожалуйста, проверить существование решения в аналогичной головоломке?
    Мне когда-то подарили заранее разобранную головоломку, идейно она проще: в куб 5?5?5 надо вставить 25 одинаковых фигур. Каждая фигура состоит из 5 кубиков вот такой конфигурации:

    ##
 ###

    Самостоятельно не смог найти решения пока ни разу. Проверкой на чётность вроде должна иметь решение.
    К сожалению я никогда не имел дела с питоном, а в коде в некоторых местах захардкожено что куб 4?4?4, не смог догадаться где всё заменить.

    Код моей беспомощной попытки переделать repl.it/Bbfo/0


    1. CnapoB
      05.01.2016 09:56
      #8725931

      У самого такая есть, вот описание решения на JavaScript: JSFiddle, GitHub.


      1. vovkasolovev
        05.01.2016 09:58
        #8725933

        О, она решается! Отлично, спасибо!


    1. p53
      06.01.2016 00:13
      #8726571

      Не сочтите за рекламу, но вот пост, а вот само решение.


      1. andy_p
        06.01.2016 03:24
        #8726747

        Подозреваю, что SAT solver справится быстрее.


        1. p53
          06.01.2016 03:38
          #8726757

          Было бы интересно понять, за счёт чего.


          1. andy_p
            06.01.2016 12:11
            #8727019

            В рассмотренном выше методе используется одна эвристика — начинать перебор со столбцов с минимальным количеством вариантов, а SAT solver использует значительно большее количество эвристик.


            1. p53
              06.01.2016 13:07
              #8727059

              Если бы у вас получилось прогнать эту задачу на SAT солвере и показать прирост скорости, было бы здорово.


  1. IDMan
    05.01.2016 16:51
    #8726217

    Годно!


  1. igrishaev
    05.01.2016 18:09
    #8726289

    > Поставить на него какие-то библиотеки — это задача покруче, чем написать саму программу.
    В чем трудности? brew, pip и вперед


  1. Zagrebelion
    06.01.2016 01:04
    #8726621

    .


  1. doozza
    11.01.2016 13:48
    #8733453

    Любопытная задача.

    Ваш вариант головоломки содержит только одну «загогулину». Интернет показывает наличие других вариантов, если я правильно понял, этой же задачи: https://i.ytimg.com/vi/QP4sMtPQj_Y/maxresdefault.jpg — здесь видно две загогулины. Даже если это не так, на мгновение представим, что у нас есть две или более загогулины.

    Так вот. Эти загогулины не являются выпуклыми, так что хоть под неё и есть место, она может не вставиться из-за блокирующих элементов вокруг. Иначе говоря, важен порядок вставки элементов. Очевидно, что модель, реализующая сборку в таких условиях не должна ограничиваться перестановкой элементов, но и реализуемостью их вставки (то есть учитывать порядок вставки).

    И теперь, собственно, главный вопрос к людям опытным в этой области: может ли оказаться решение допустимое теоретически, но неосуществимое физически из-за невыпуклости элементов?


  1. rodem
    12.01.2016 13:40
    #8735183

    С таким подходом однозначно надо попробовать Eternity II


  1. andy_p
    12.01.2016 13:48
    #8735207

    Кстати, возможное количество положений загогулины 576 а не 288.