Алгоритм Python для решения головоломки triomines с возвратом

Question

Допустим, у меня есть такая доска

. . x . . .
. . . . . .
. . x . . x

х используется поле и '.' Бесплатно. Мне нужно положить триомины, чтобы заполнить всю область, чтобы не было свободных клеток. Триомины имеют L-образную форму, и я отмечаю одно и то же триомино с тем же номером.

Таким образом, решение может быть таким:

1 1 x 3 5 5
1 2 3 3 4 5
2 2 x 4 4 x

Каков возможный алгоритм обратного отслеживания Python?

Answer 1

Алгоритм довольно прост, сначала мы получаем список ячеек, доступных в этой конфигурации платы, в основном, перечисляем все возможные ячейки минус запрещенные.

затем мы делаем шаг решения, перебирая список доступных ячеек и пытаясь подогнать кусок триомино в эту конкретную позицию ячейки, используя 4 возможных ориентации (доступная ячейка - это угол, у нас 4 ориентации из-за поворота).

если фигура подходит, увеличьте шаг, удалите занятые ячейки из списка и попробуйте решить снова, пока ячейки не будут доступны - это означает, что вся доска покрыта.

#!/usr/bin/env python

solution = {}

orientations = [(1,1),(1,-1),(-1,1),(-1,-1)]    # 4 possible orientations

def solve( avl, step ) :
    if not len(avl) :
        print 'done!'
        return True

    for i,j in avl :
        for oi,oj in orientations :
            if (i+oi,j) in avl and (i,j+oj) in avl :
                occupied = [(i,j),(i+oi,j),(i,j+oj)]
                # remove occupied from available, increase step and keep solving
                if solve( [a for a in avl if a not in occupied], step + 1 ) :
                    for occ in occupied :
                        solution[occ] = step
                    return True

# initial conditions for this configuration
#
# . . x . . .
# . . . . . .
# . . x . . x

X_SIZE, Y_SIZE = 6, 3
forbidden_cells = [(0,2),(2,2),(2,5)]

if __name__ == '__main__' :
    available = []

    # fill the available cells list
    for i in range(Y_SIZE) :
        for j in range(X_SIZE) :
            if (i,j) not in forbidden_cells :
                available.append( (i,j) )

    # print the original problem
    for i in range(Y_SIZE) :
        for j in range(X_SIZE) :
            print '.' if (i,j) in available else 'x',
        print

    # solve away!
    if solve( available, 1 ) :
        for i in range(Y_SIZE) :
            for j in range(X_SIZE) :
                print solution[(i,j)] if (i,j) in available else 'x',
            print
    else :
        print 'sorry, no solution found'

Выход:

$ ./triomines.py 
. . x . . .
. . . . . .
. . x . . x
done!
1 1 x 3 2 2
1 4 3 3 5 2
4 4 x 5 5 x
$