python - Python 算法通过回溯解决三联谜题

Question

假设我有一个这样的板

. . x . . .
. . . . . .
. . 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 个方向）将 triomino 块安装到这个特定的单元格位置来制定解决方案。

如果这块合适，增加步长，从列表中删除占用的单元格并再次尝试求解，直到没有可用的单元格——这意味着整个板子都被覆盖了。

#!/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
$