Python的算法來解決triomines帶回溯

Question

困擾比方說，我有這樣的

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

X一板用於箱子和「」免費。我需要把triomines填滿整個區域，所以不會有空閒的單元格。 Triomines是L形的，我用相同的數字標記相同的triomino。

因此，解決辦法可能是這樣的：

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

什麼可以回溯蟒蛇算法可能是什麼？

Answer 1

算法非常簡單，首先我們得到這個電路板配置中可用的單元列表，基本上列出所有可能的單元減去禁止的單元。

然後我們通過遍歷可用單元列表並嘗試將一個triomino塊放到這個特定的單元位置，使用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 
$