前言

“伤脑筋十三块”，又被称为“八阵图”，这款玩具基于“伤脑筋十二块”的基础上，将其可玩性、多变性升华到了极致。
“伤脑筋十三块”既具备了一共有16146种平面装法（翻转、旋转均算一种），假若将十三块积木置于方盒之外，可以拼成汉字、动物、建筑物等等任何您所能想象到的物体，玩法更是不计其数，这就是“伤脑筋十三块”的微妙之处：玩物知志、寓教于乐！

一、解决思路

1.1. 解决思路

1. 遍历所有可能的排列
2. 对所有的组合进行验证，去除所有不能完美放入盒子的排列

1.2 存在问题

全部可能的排列一共13!（6227020800）种，每种排列又有2*4⁵*8⁵（67108864）种旋转、翻转状态，共计87756541318397952000（8.77×10¹⁹）各排列，根本无法在有限时间内全部验证可行性

1.3 解决方法

按遍历顺序，每块各种依次填入空格中，每增加一块积木，验证可行性，如果内部存在不可填充满的空隙、或者内部存在重叠区域，那么以前面几块积木开始的所有排列都是不可行，可以直接跳过，这样可以大大减小验证次数。

二、问题解决

1. 积木抽象

将所有积木简化成一个最小的二维矩阵，空的地方是0，实的地方置1，为简化计算，全部转化成numpy数组
文件名：config.py，代码如下：

import numpy as np

parts = [
        [[1, 1, 1, 1], 
        [1, 0, 0, 0]], 
        [[1, 1], 
        [1, 1], 
        [1, 0]], 
        [[1, 1, 1, 1], 
        [0, 1, 0, 0]], 
        [[1, 1, 1, 1, 1]], 
        [[1, 0, 0], 
        [1, 1, 0],
        [0, 1, 1]], 
        [[1, 0, 0], 
        [1, 1, 1], 
        [1, 0, 0]], 
        [[1, 1, 0], 
        [0, 1, 1],
        [0, 1, 0]], 
        [[1, 1], 
        [1, 1]],
        [[1, 1, 0], 
        [0, 1, 0], 
        [0, 1, 1]], 
        [[0, 1, 0], 
        [1, 1, 1], 
        [0, 1, 0]], 
        [[1, 1, 1], 
        [1, 0, 0], 
        [1, 0, 0]], 
        [[0, 1], 
        [1, 1], 
        [1, 0], 
        [1, 0]], 
        [[1, 1], 
        [1, 0], 
        [1, 1]], 
        ]
parts = [np.array(i, dtype=np.uint8) for i in parts]

2. 计算孔洞数量

每增加一块积木都计算一次孔洞个数，及每个孔洞内孔0的个数，如果所有孔洞内0的个数都能被5整除或被5除余4，那可能是可行解，否则一定是不可行解，返回False，提前结束后续遍历
文件名：findhole.py，代码如下：

import numpy as np

def findhole(arr):
    possible = {4,5,9,10,14,15,19,20,24,25,29,30,34,35,39,40,44,45,49,50,54,55,59,60,64}
    x, y = np.where(arr==0)
    #print(x)
    #print(y)
    rdt = {}
    cdt = {}
    for i, j in zip(x, y):
        rdt.setdefault(i, set())
        rdt[i].add(j)
        cdt.setdefault(j, set())
        cdt[j].add(i)
    #print('rdt:', rdt, sep='\n')
    #print('cdt:', cdt, sep='\n')
    res = set()
    for i, j in zip(x, y):
        if not j in rdt.get(i, {}):
            continue
        hole = {(i,j)}
        queue = {(i,j)}
        used = set()
        while queue:
            x0, y0 = queue.pop()
            rdt[x0].discard(y0)
            used.add((x0, y0))
            for dx, dy in zip([0,0,-1,1],[-1,1,0,0]):
                x, y = x0+dx, y0+dy
                if y in rdt.get(x, {}):
                    if (x,y) in used:
                        continue
                    queue.add((x, y))
                    hole.add((x, y))
        #res.add(hole)
        if not len(hole) in possible:
            return False, len(hole)
    return True, 0

3. 主程序

采用递归法遍历所有可行解，当递归深度达到13时，刚好将所有积木填入盒中，如果能够同时满足孔洞个数是0，并且没有重叠时，说明该排列符合要求，输出结果，为便于分辨积木，将不同形状积木编号，每块积木对应位置输出积木号码

文件名：main.py，代码如下：

import numpy as np
import time
from config import parts
from findhole import findhole

def getPos(arr, flip=1):
    lt = []
    for i in range(4):
        lt.append(np.rot90(arr, i))
        if not flip:
            continue
        lt.append(np.rot90(arr.T, i))
    dt = {}
    for i in lt:
        dt[str(i.tolist())] = i
    lt = list(dt.values())
    return lt

def showall(parts):
    arr = np.zeros([8,8], dtype=np.uint8)
    #arr[:2, :2] = 13
    #arr[0, 2:7] = 12
    for i, part in enumerate(parts):
        val = mapping.get(str(part), 111)*16
        ret = check(arr, part, val)
    return True, arr//16

def check(arr, part, out=0):
    #print(arr)
    #print(part)
    m, n = part.shape
    x0, y0 = np.where(part==1)
    x, y = np.where(arr==0)
    x, y = x[0], y[0]-y0[0]
    ##print('part:\n', part)
    if y<0:
        #print('out of arr left')
        return False, arr
    if y+n>8:
        #print('out of arr right')
        return False, arr
    if x+m>8:
        #print('out of arr bottom')
        return False, arr
    tmp = arr[x:x+m, y:y+n]
    ##print('tmp:\n', tmp)
    if out:
        #print('temp:', tmp, sep='\n')
        #print('part:', part, sep='\n')
        tmp += part*out
    else:
        tmp += part
        if tmp.max()>1:
            #print('coincide')
            return False, arr
    ##print(m, n, x, y, x0[0], y0[0])
    return True, arr

def merge(used, length, lt, arr, deep=0):
    ret, num = findhole(arr)
    if not ret:
        return
    if deep>12:
        print(f'deep: {deep}')
        print(showall(result[:deep+1])[1])
        #print(arr)
        return
    for i8 in range(length):
        if i8 in used:
            continue
        used.add(i8)
        for j, p8 in enumerate(lt[i8]):
            result[deep] = p8
            #print(arr)
            arr2 = arr.copy()
            ret, arr3 = check(arr2, result[deep])
            if not ret:
                continue
            if deep<4:
                print(time.strftime('%H:%M:%S'), f"deep:{deep} i:{i8} j:{j}", *used)
            merge(used, length, lt, arr2, deep+1)
        used.remove(i8)
if __name__=='__main__':
    length = 13
    np.random.shuffle(parts)
    lt = [getPos(i) for i in parts]
    #lt.sort(key=lambda i: len(i))
    #print(*[j for i in lt for j in i], sep='\n\n')
    flag = True
    print(*[len(i) for i in lt])
    for i, items in enumerate(lt):
        if flag and len(items)==8:
            lt[i] = items[:1]
            flag = False
            print('only')
        print(*lt[i], sep='\n', end='\n\n')
    print(*[len(i) for i in lt])
    mapping = {str(k):(i+1) for i, j in enumerate(lt) for k in j}
    used = set()
    arr = np.zeros([8,8], dtype=np.uint8)
    ret, arr = check(arr.copy(), parts[0])
    result = list(range(length))
    #exit(0)
    arr = np.zeros([8,8], dtype=np.uint8)
    merge(used, length, lt, arr)

4. 部分结果展示

总结

以上是遍历法解决伤脑筋十三块的全部，有什么问题欢迎提出改进意见，可以直接留言或发邮件，邮箱：zhyh55@163.com
如果有什么难题，好玩的、需要用程序解决的也可以分享，一起解决