python小练习（097）：etch-a-scetch（一）

jerryxjr1220

python小练习马上要接近100期了，但是一直有一个python小练习的遗留问题没有解决，那就是在第0期中的etch-a-scetch的谜题始终没有解决，传送门

我准备在接下来的3期中，解决掉这个困扰我好久的难题，也给python小练习系列一个完美的收官。（或许以后就不会再更新了）

先来看一下，这个谜题的描述：

这个图片是热身题

可以看到图片中左边和上边的数字分别描述了对应横行和纵行的红色连续方块的数量。

例如第一行的2 1 2表示 第一横行2个红色方块相连，1个红色方块，2个红色方块相连。其余行和列类似。

那么假设现在知道了所有横行和纵行的数字描述，求这些数字描述所组成的图形。
热身题：

# Dimensions
9 9

# Horizontal
2 1 2
1 3 1
5

7
9
3

2 3 2
2 3 2
2 3 2

# Vertical
2 1 3
1 2 3
3

8
9
8

3
1 2 3
2 1 3

正式题：

# Dimensions
32 32

# Horizontal lines
3 2
8
10
3 1 1

5 2 1
5 2 1
4 1 1
15

19
6 14
6 1 12
6 1 10

7 2 1 8
6 1 1 2 1 1 1 1
5 1 4 1
5 4 1 4 1 1 1

5 1 1 8
5 2 1 8
6 1 2 1 3
6 3 2 1

6 1 5
1 6 3
2 7 2
3 3 10 4

9 12 1
22 1
21 4
1 17 1

2 8 5 1
2 2 4
5 2 1 1
5

# Vertical lines
5
5
5
3 1

3 1
5
5
6

5 6
9 5
11 5 1
13 6 1

14 6 1
7 12 1
6 1 11 1
3 1 1 1 9 1

3 4 10
8 1 1 2 8 1
10 1 1 1 7 1
10 4 1 1 7 1

3 2 5 2 1 2 6 2
3 2 4 2 1 1 4 1
2 6 3 1 1 1 1 1
12 3 1 2 1 1 1

3 2 7 3 1 2 1 2
2 6 3 1 1 1 1
12 3 1 5
6 3 1

6 4 1
5 4
4 1 1
5

jerryxjr1220

我们可以把这个问题的求解分成几步来操作，今天先分析第一步。
因为每一行的数字描述是由一个列表组成，但是反过来一个列表可以描述的数字组合有很多种，那么能否把所有的组合全部列出来呢？
比如，我们知道[2,1,2] 这个数字列表，同时我们知道这个行的长度是9
那么全排列所有的可能组合：（用1表示红色方块，0表示黑色方块）

['110101100', '110100110', '110100011', '110010110', '110010011', '110001011', '011010110', '011010011', '011001011', '001101011']

jerryxjr1220

分步程序，取得所有数字列表描述的可能排列：

def gen_candi(num,maxlen):   
    candi = []  
    for i in range(maxlen+2-sum(num)-len(num)):  
        head = '0'*i + '1'*num[0]  
        if len(num)==1:  
            tail = '0'*(maxlen-len(head))  
            candi.append(head+tail)  
        else:  
            tail = ['0'+j for j in gen_candi(num[1:], maxlen-len(head)-1)]  
            candi.extend([head + j for j in tail])  
    return candi