用传播分配算法解矩形数字谜题

矩形数字谜题

谜题如下图所示，每个数字N表示一个矩形区域R， R所包含的小方格数正好为N。要求计算出所有数字对应的矩形区域，使得它们之间不互相覆盖，并且正好包含所有的方块。

解决这种问题的最简单的办法就是回溯法，按照顺序把每个数字对应的矩形区域计算出来，如果当前计算出来的矩形区域和已经放置的矩形重叠的话，就尝试下一个候选矩形，直到全部区域被填满。题中一共有22个数字，每个数字对应的可能的矩形区域平均也有5、6种，这样一来，回溯法要花很长时间才能找到答案。

本文给出一种快速算法：传播与分配算法，关于此算法的基本知识，请参照文章：

解空间和初始状态

完整程序

首先我们需要得到所有的数字所对应的所有可能矩形，我们称之为解空间，通过传播与分配算法，逐渐缩小这个解空间的取值范围，直到找到最终解。

解空间我们用英文status来表示，下面的程序计算出问题的初始解空间。

blocks列表是一个3个元素的的元组，(横坐标、纵坐标、此坐标上的数字)。

WIDTH = 12
HEIGHT = 12
blocks = [
(0, 8, 10),(8, 4, 9),(7, 0, 8),(3, 1, 8),(5, 6, 8),
(7, 7, 8), (8, 9, 5),(11,9, 6),(4, 10,6),(3, 11,6),
(9, 11,4),(9,1, 6),(0, 3, 6),(6, 3, 6),(3, 4, 6),
(11,4, 6),(0, 6, 6),(10,6, 6),(2, 7, 6),(9, 8, 6),
(2, 9, 6),(6, 9, 6)
]

possible_block2()计算出所有包含坐标(x,y)，长宽为(w,h)的矩形区域。它返回的是4个元素的元组，其意义分别为（矩形区域的左上点横坐标， 矩形区域的左上点纵坐标， 矩形区域的宽， 矩形区域的高）。

def possible_block2(x, y, w, h):
    for i in xrange(-w+1, 1):
        for j in xrange(-h+1, 1):
            if (x + i >= 0 and
                y + j >= 0 and
                x + i + w <= WIDTH and
                y + j + h <= HEIGHT):
                yield (x + i, y + j, w, h)

possible_block()计算出坐标为(x,y)的数字c所对应的所有可能的矩形区域。例如：

>>> print list(possible_block(0, 8, 10))
[(0, 0, 1, 10), (0, 1, 1, 10), (0, 2, 1, 10), (0, 4, 2, 5),
(0, 5, 2, 5), (0, 6, 2, 5), (0, 7, 2, 5), (0, 7, 5, 2),
(0, 8, 5, 2), (0, 8, 10, 1)]

def possible_block(x, y, c):
    for i in xrange(1, c+1):
        if c%i == 0:
            for p in possible_block2(x, y, i, c//i):
                yield p

make_init_status()通过收集所有的数字对应的所有可能的矩形区域，返回本问题的初始解空间status。status[i]为blocks[i]对应的所有可能的解。

def make_init_status(blocks):
    status = []
    for x, y, b in blocks:
        status.append( list(possible_block(x,y,b)) )
    return status

传播算法

传播和分配的基本思想是通过传播操作，尽量缩小解空间的取值范围，在无法缩小的情况下，进行解空间的分配操作，也就是把解空间分解成两个子空间，然后分别对其进行传播和分配操作，直到找到解为止。

我们先来看看传播操作。对于本问题，传播操作就是剔除掉所有相互重叠的矩形。具体地说，就是当某个矩形R与某个数字N对应的所有的矩形都重叠的时候，从解空间中删除矩形R，下文称这种矩形为无效矩形。下面是这部分代码的说明。

rectangle_overlap()判断矩形rect1和矩形rect2是否有重叠部分，有则返回True，无则返回False。

def rectangle_overlap(rect1, rect2):
    x1, y1, w1, h1 = rect1
    x2, y2, w2, h2 = rect2
    if y1 + h1 - 1 < y2: return False
    if y1 > y2 + h2 - 1: return False
    if x1 + w1 - 1 < x2: return False
    if x1 > x2 + w2 - 1: return False
    return True

rectangle_overlap_all()判断矩形rect和矩形列表rectlist中的所有矩形是否都重叠，都重叠时返回True。

def rectangle_overlap_all(rect, rectlist):
    for rect1 in rectlist:
        if not rectangle_overlap(rect, rect1):
            return False
    return True

remove_overlap_rectangles()从矩形列表rectlist1中删除掉与矩形列表rectlist2中所有矩形重叠的矩形，如果删除了某个矩形的话，返回True，否则返回False。

def remove_overlap_rectangles(rectlist1, rectlist2):
    flag = False
    for i, x in enumerate(rectlist1):
        if rectangle_overlap_all(x, rectlist2):
            rectlist1[i] = 0
            flag = True
    while 0 in rectlist1:
        rectlist1.remove(0)
    return flag

del_impossible_choice()完成对解空间status的传播操作，从解空间status中删除掉所有无效矩形，直到找不到更多的无效矩形。tocheck是一个待检查的集合，它的元素为一个2元元组(x, y)，表示要删除status[x]中所有与status[y]重叠的矩形。当remove_overlap_rectangles()返回Ture时，表示status[x]发生了变化，因此需要重新检查(i, x)，i为除了x之外的所有下标。当tocheck为空时，则表示无法继续进行传播操作了。此时的解空间的大小将明显的减少。例如本问题的初始解空间中共有个345矩形元素，经过一次传播操作之后剩下156个矩形元素。

def del_impossible_choice(status):
    tocheck = set()
    for i in range(len(status)):
        for j in range(len(status)):
            if i!=j: tocheck.add((i,j))

    while len(tocheck) > 0:
        x, y = tocheck.pop()
        r = remove_overlap_rectangles(status[x], status[y])
        if r:
            for i in range(len(status)):
                if i!=x:
                    tocheck.add((i,x))

分配算法

当传播操作无法继续时，进行分配操作，通过分配算法将当前的解空间分解为两个子解空间，然后再递归执行传播分配操作。下面是这部分程序的解释。

divide_status()对解空间status进行分配，得到两个子解空间status1和status2。分配的算法有很多种，这里采用的具体算法如下：

• 当某个数所对应的矩形列表长度为1时表示这个数所对应的矩形已经有解。
• 当长度大于1时表示还多个候选解，找到候选解最少的下标index，然后把这组候选解[x0, x1, x2，...，xn]分为两部分：[x0], [x1, x2, ... , xn]。

程序中的status1和status2是分解后的子解空间，显然status1和status2的集合就是status。

def divide_status(status):
    m = 100
    index = -1
    for i, x in enumerate(status):
        if len(x) > 1 and m > len(x):
            m = len(x)
            index = i

    status1 = deepcopy(status)
    status2 = deepcopy(status)
    status1[index] = [status[index][0]]
    status2[index] = status[index][1:]
    return status1, status2

is_solved_status()判断status是否是最终解。当解空间status中所有的候选矩形数都为1时，则找到了最终解。

def is_solved_status(status):
    for x in status:
        if len(x)!= 1:
            return False
    return True

is_impossible_status()判断status是否是无解解空间。 当解空间status中某组候选矩形数为0时，表示此空间无解。

def is_impossible_status(status):
    for x in status:
        if len(x) == 0:
            return True
    return False

solve_puzzle()递归调用自己来实现传播分配操作，直到找到解。

def solve_puzzle(status):
    del_impossible_choice(status) #分配操作，尽可能地缩小解空间
    if is_solved_status(status): #判断解空间是否为最终解
        print_solve_status(status)
        return
    if is_impossible_status(status): #判断解空间是否无解
        return
    #对解空间status进行分配操作，得到子解空间status1和status2
    status1, status2 = divide_status(status)
    solve_puzzle(status1) #递归调用solvePuzzle搜索解空间status1中的解
    solve_puzzle(status2) #递归调用solvePuzzle搜索解空间status2中的解

运行结果

最后我们来运行一下程序：

>>> status = make_init_status(blocks)
>>> solve_puzzle(status)
[[(0, 7, 2, 5)], [(8, 2, 3, 3)], [(0, 0, 8, 1)], [(2, 1, 4, 2)],
[(5, 3, 1, 8)], [(6, 4, 2, 4)], [(8, 7, 1, 5)], [(11, 6, 1, 6)],
[(4, 5, 1, 6)], [(2, 11, 6, 1)], [(9, 10, 2, 2)], [(8, 0, 3, 2)],
[(0, 1, 2, 3)], [(6, 1, 2, 3)], [(2, 3, 3, 2)], [(11, 0, 1, 6)],
[(0, 4, 2, 3)], [(8, 5, 3, 2)], [(2, 5, 2, 3)], [(9, 7, 2,3)],
[(2, 8, 2, 3)], [(6, 8, 2, 3)]]

print_solve_status()将解打印成易读的形式：

def print_solve_status(status):
    chars = "abcdefghijklmnopqrstuvwxyz"
    board = []
    for i in range(HEIGHT):
        board.append([" "]*WIDTH)
    for cnt, rect in enumerate(status):
        x, y, w, h = rect[0]
        for i in range(x, x+w):
            for j in range(y, y+h):
                board[j][i] = chars[cnt]
    for line in board:
        print "".join(line)

最终的输出结果为：

cccccccclllp
mmddddnnlllp
mmddddnnbbbp
mmoooennbbbp
qqoooeffbbbp
qqssieffrrrp
qqssieffrrrh
aassieffgtth
aauuievvgtth
aauuievvgtth
aauuievvgkkh
aajjjjjjgkkh

在我的电脑上整个计算过程不过2，3秒。我用回溯法解了一下这个题，睡了一觉才等到答案，所以不知道到底花了多长时间。:-)