之前在豆瓣的“东西”里面看到一块叫做《Logic Square》的IOS游戏，他们说很多人玩到入迷，所以我也就好奇下来玩一下，然后发现。。。。其实我以前玩过这一类的游戏。。大概界面就是这个样子，然后你就要往里面填写1或者0，也就是右下角的√和×；游戏的规则就是，你看，每一行每一列不是有一个以上的数字么？那个数字就表示那一行/列的√的数目的排列，比如一个5加一个3的话，说明这一行/列肯定是先有一个连着的5个√，至少空一格之后还有连着的3个√，然后这一行/列剩下的全部都是×了。

然后就是根据上面的数字把结果还原出来。。。

根据我的尿性，这么多关我肯定不会好好去玩，所以就直接写个像解数独一样的全解程序来解了这个游戏吧。。。

其实我是想对Python练一下手我会乱说？

代码很短：

# -*- coding: utf-8 -*-
#获取当前行/列的描述
def get_discripe(row):
    scan_list = [];
    counter = 0;
    for i in range(len(row)):
        if row[i] == 1:
            counter += 1
        elif counter != 0:
            scan_list.append(counter)
            counter = 0
    if counter:
        scan_list.append(counter)
    return scan_list

def check_row(row,dst):
    return get_discripe(row) == dst

#获取下一个位置的编号
def getxy(i,j,x_len):
    j += 1
    if j == x_len:
        j = 0
        i += 1
    return (i,j)

#检测行/列是否可能，不可能的话不会继续迭代
def normaltest_row(row,dst):
    if len(dst) < len(row):
        return False    
    for k in range(len(row)):
        if row[k] > dst[k]:
            return False
        if row[k] < dst[k] and k != len(row)-1:
            return False
    return True    

#检测行/列是否可能，不可能的话不会继续迭代  
def normal_test(state,x,y,i,j):
    if normaltest_row(get_discripe(state[i,:]),y[i]) == False:
        return False

    if normaltest_row(get_discripe(state[:,j]),x[j]) == False:
        return False
    return True

#迭代内部核心实现 
def foo(state,x,y,i,j):
    legal_flag = 1;
    if j == len(x)-1 and not check_row(state[i,:],y[i]):
        legal_flag = 0
    if i == len(y)-1 and not check_row(state[:,j],x[j]):
        legal_flag = 0
    if not normal_test(state,x,y,i,j):
        legal_flag = 0
    if legal_flag and (i == len(y)-1) and (j == len(x)-1):
        print state
    elif legal_flag:
        temp_ij = getxy(i,j,len(x))
        if temp_ij[0] != len(y):
            iteration(state,x,y,temp_ij[0],temp_ij[1])

#迭代计算            
def iteration(state,x,y,i,j):
    state[i,j] = 1
    foo(state,x,y,i,j)            
    state[i,j] = 0
    foo(state,x,y,i,j)    

#Main
x = [[6],[1,2],[5,3],[1],[6],[1],[6],[1],[5,3],[1,2]]
y = [[3,3,2],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,2,2],[1,1],[2,2],[1,1],[1,1]]

#x=[[4],[2,1],[1,1],[2,1],[1,4],[2,1],[1,1],[14],[1,1,2],[2,1,3],[1,4],[2,1],[1,1],[2,1],[4]]
#y=[[1],[9],[3,1,1,1,3],[2,1,1,1,2],[1,1,1,1,1],[15],[1,1,1,1,1],[1],[1],[1],[1],[1,1],[1,1],[3],[1]]

state = zeros((len(y),len(x)))
iteration(state,x,y,0,0)

如我在程序最后测试的两组数据里面所示，一组是10×10的，一组是15×15的，跑出来的结果分别是：

>>> runfile(r'C:Documents and SettingsAdministrator.spyder2
.temp.py', wdir=r'C:Documents and SettingsAdministrator.spyder2')
[[ 1.  1.  1.  0.  1.  1.  1.  0.  1.  1.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  1.  0.  1.  0.  1.  0.  1.  0.]
 [ 1.  0.  0.  1.  1.  0.  1.  1.  0.  0.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  1.]
 [ 0.  1.  1.  0.  0.  0.  0.  0.  1.  1.]
 [ 0.  0.  1.  0.  0.  0.  0.  0.  1.  0.]
 [ 0.  0.  1.  0.  0.  0.  0.  0.  1.  0.]]

15×15的：

>>> runfile(r'C:Documents and SettingsAdministrator.spyder2
.temp.py', wdir=r'C:Documents and SettingsAdministrator.spyder2')
[[ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  1.  1.  1.  1.  1.  1.  1.  1.  0.  0.  0.]
 [ 0.  1.  1.  1.  0.  1.  0.  1.  0.  1.  0.  1.  1.  1.  0.]
 [ 1.  1.  0.  0.  1.  0.  0.  1.  0.  0.  1.  0.  0.  1.  1.]
 [ 1.  0.  0.  0.  1.  0.  0.  1.  0.  0.  1.  0.  0.  0.  1.]
 [ 1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.]
 [ 1.  0.  0.  0.  1.  0.  0.  1.  0.  0.  1.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.  0.]]

思路其实就和填写数独一样，每个空分别填写所有的可能性的值，这里相当于1和0，然后递归迭代下去。。。

但是这个思路只能是最基本的思路，因为python本身速度就慢，而且这样会做了大量不可能的迭代到时时间上的浪费，这种思路基本上对5×5以下的可以在可以忍耐的时间内算出来，之外基本不行。。

所以就要加上很多提前判断的条件，用来提前进行——剪枝；

首先最基本的就是，每迭代完一行，或者一列，就来检查一下这一行是否合理，如果这一行本身就是错的，那么就放弃迭代，返回！

然后对于每一个，即便没有到达这一行/列的最尾部，我们也可以算出来一个描述目前这一行的那个序列，比如×√××√√…虽然这一行有10个空，我们现在才迭代到第六个，那么我们就可以算出这个序列目前的描述就是(1,2)，这个就是我刚刚所说的“描述”，然后我们可以用这个描述来和目标“描述”作对比，就可以提前判断出这个迭代是否应该进行下去：

比如这个描述的长度已经大于目标描述的长度了，那么显然不可能。

又或者这个描述中间某个位置的数字大于目标描述相应位置处的数字，显然还是不可能。

再或者，这个描述中间某个位置的数字小于目标描述相应位置的数，而且这个位置不是在我们这个临时描述的最尾部，那么也是不可能的。

经过上面各种剪枝，就可以瞬间算出10×10的来，但是15×15还是需要点时间。。。加上我的电脑确实也不是很好，。，。，

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com