Nonogram也是一种类似于数独的数字游戏，但是似乎要简单一些，只要有足够的耐心，任何玩家都可以成功完成，而且在游戏过程中会逐渐熟练。
在应用商店中也可以找到，而且评分高达4.9。
游戏界面如下，感兴趣的话可以自行查找游戏规则，app中也有新手指引。很容易上手。
求解思路：
这个游戏比数独简单的一点是，它不需要反复试探，也就是不需要回撤，只需要依次扫描，先从能够确定的位置出发，逐步填充即可。
（1）找到可能的开头组合。
比如对上面的第6列，只有一个数字8，其可能的开头为1~10共10种，但是如果从4及以后开头，则会超出格子，故只能有3种情况
①从1开头，第6列为1111111100
②从2开头，第6列为0111111110
③从3开头，第6列为0011111111
（2）取交集部分，完成部分填充。
可以看到，不论怎样取，第3~8位都是1，所以就可以将其标记为1。
（3）不断重复上述过程，直到完成所有填充。
另：当已有部分方格被填充时，还应保证新的填充不与其发生冲突。
上面只是举了个简单的例子，实际程序中，可以对每行每列反复扫描。
代码实现：
import numpy as np from itertools import combinations class nonogram: def __init__(self,rows,cols): if len(rows) != len(cols): raise Exception(‘The number of rows and columns varies‘) self.rank = len(rows) self.rows = rows self.cols = cols # 初始化结果矩阵为-1，用1表示填充，用0表示× self.result = np.zeros(shape=(self.rank, self.rank))-1 def cal_coms(self,nums): """ 由某行或某列的数字列表计算可能的开头组合 nums可表示rows或cols中的一个元素 """ l = len(nums) # 可能的开头组合 coms_p = list(combinations(range(0,self.rank), l)) # 可行的开头组合 coms_v = [] # 对所有可能的组合逐一筛选 for com in coms_p: flag = 0 # 保证两两间隔 for i in range(1,l): if com[i]-com[i-1]<nums[i-1]+1: flag = 1 break # 保证不超过范围 if self.rank-com[-1]<nums[-1]: flag = 1 if flag == 0: coms_v.append(com) return coms_v def cal_res(self,nums,result_l): ‘‘‘ 检查是否一定是1或者一定是0 返回1、0或-1（不确定） ‘‘‘ coms_v = self.cal_coms(nums) lines = [] # 对每种可能组合，列出在该组合下的数字nums记入line for com in coms_v: line = np.zeros(self.rank) for i in range(0,len(com)): for j in range(com[i],com[i]+nums[i]): line[j]=1 # 如果没有与已知情况发生冲突，则加入lines if 1 not in line+result_l: lines.append(line) if len(lines) == 0: return lines = np.mat(lines) for n in range(0,self.rank): # 如果在各种组合下都是1，记为1 if lines[:,n].all(): result_l[n] = 1 # 如果在各种组合下都是0（没有1），记为0 if not lines[:,n].any(): result_l[n] = 0 return result_l def cal_nono(self): ‘‘‘ 完成nonogram的计算 ‘‘‘ while -1 in self.result: # 当有未标记的位置时，对每行每列反复扫描 for i in range(0,self.rank): self.result[i,:] = self.cal_res(rows[i],self.result[i,:]) for i in range(0,self.rank): self.result[:,i] = self.cal_res(cols[i],self.result[:,i])
测试一下：
# 测试用例 rows = [ [5], [4], [6], [7], [1,5], [5], [1,5,2], [6,2], [1,2], [1,2]] cols = [ [1], [1], [5,4], [4,2], [4,2], [8], [1,6], [4], [7], [6]] N = nonogram(rows,cols) N.cal_nono() print(N.result)
计算得到的结果为：
完成一局游戏后就会获得一张色块拼图，我目前积攒的部分拼图如下。（前面的都是手动推理的，后面几个是用上面的程序计算的，程序虽然快很多，但手动才有趣味嘛。）