让我们从游戏开始──点灯

　　一次上班无聊，把同事的手机拿来打游戏，发现有个叫“点灯”的小游戏，开始不太在意，玩了一会儿以后发现非常有趣，想想很久没有写过程序了，便决定用这个来练练手。
关于游戏
　　点灯游戏规则非常简单，简单到什么人都可以一学就会。但是简单的规则并不意味着游戏也简单，这恰恰就是我所喜欢的，在简单中充满变化。因为规则简单，我在这里就不多说了。
http://games.wuhan.cc/flash/flash/flash_swf/3015.swf
　　这个是网上找到的，所不同的就是他在开始的时候有些灯已经点亮了。让我们简化一下，4×4的正方形，一开始所有灯都是关闭状态，我们的目的就是把所有的灯都打开。等我们把这个简化的问题解决了，在来看看这个大的问题。

一些理论
　　这个游戏真是让人恼火啊，为了让程序能够解出答案，我们需要想想这个游戏到底是什么。
　　也许我们应该这样看这个游戏：这16个格子是16个开关，每个开关控制着灯泡的状态。如果一个开关的状态改变，那么其所在格子与相邻格子的灯泡状态反转。这样我们就可以初始化一个4×4,全部是0的数组，表示所有开关全部是关闭的，当某一格的开关打开，我们就把这格变成1。而且我们可以发现，某一格的开关状态变化偶数次，那么灯泡的状态和最初的状态是一样的（0->1->0）。那么我们用0和1来表示开关的状态是成立的。
　　好了，现在我们有个一个新的问题：如何从开关状态得到灯泡的状态？问题其实很简单，从上面我们知道，某一格的灯泡受到自己所在的格子与周围四格的影响（我们为了简单称这些格子叫“影响格”），由于一开始灯泡是关闭的，而且只有两种状态（灯亮，灯灭），所以我们可以知道：对于某一格的灯泡，如果影响格内有奇数个开关打开，这格灯泡就被点亮，反之关闭。
　　天，我的文笔实在太差，写这些理论真是很痛苦，也不知道有多少人能看懂。现在我们开始写程序吧。

第一天
　　对于这样的问题，我们最直接的想法就是穷举法：把所有的组合都试一次，有此来找到所有可能的解。
　　那么我们怎么的到这所有的组合呢？让我们来回想一下前面理论分析的内容。所有灯的状态都用0和1来表示，如果我们把这个4×4的二维数组组合成一个0、1序列，那么我们这个得到的0、1序列的是[0, 2^16)中所有的整数．我们用如下的语句得到这个整数序列：

[x for x in xrange(2**16)]#由于数量比较大，我们没有使用range。两者之间的额区别google一下就可以了。

　　现在我们把这些整数变成二进制！由于python里面没有直接的函数可以转换，所有我们要自己完成：

bstr = lambda n, l=16: n<0 and binarystr((2L<>1).lstrip('0')+str(n&1) or '0'

>>>bstr(5)
'101'

　　注意一下返回的是一个字符串（这个是肯定的，想想就知道了）。zfill可以补齐我们需要的位数。那么生成序列的语句就出来了：

[bstr(x).zfill(16) for x in xrange(2**16)]

　　现在我们把得到的序列变成数组。numarray是不错的选择。

>>> import numarray.strings as nastr
>>> a=nastr.array(’101010101′, itemsize=1)
>>> a
CharArray([’1′, ‘0′, ‘1′, ‘0′, ‘1′, ‘0′, ‘1′, ‘0′, ‘1′])
>>> numarray.reshape(a,3,3)
CharArray([[’1′, ‘0′, ‘1′],
[’0′, ‘1′, ‘0′],
[’1′, ‘0′, ‘1′]]))

　　还要把字符转换成数字，用eval就好了。
　　Hoho, 看来我们需要的东西基本已经齐全了，我们现在先把得到的东西都组合一下。得到下面的代码：

from numarray import * 
import numarray.strings as nastr 
PosSol=[reshape(nastr.array(bstr(x).zfill(16), itemsize=1),4,4).eval() for x in xrange(2**16)]#PosSol:Possible Solutions

　　当然，我们现在是限定一个4×4的情况，如果要解n×n，小小改动一下就可以了。如果你对上面的代码的结果有些怀疑，那试试2×2的情况，代码怎么修改相信你应该很清楚，看看结果吧。好了，让我们继续吧。
　　现在我们有了开关状态的所有组合，那么我们就要根据这些组合计算出灯泡状态。让我们想想灯泡状态的代码要怎么写。我们用x（表示列），y（表示行）表示给定的灯泡位置，我们根据开关状态计算它是否被点亮。相信很多人的第一想法就是按照给定的x，y得到x+1,x-1,y+1,y-1这些，还要自己判断是否在给定的元素处于数组的边界……天，我不要再想这种方法了。虽然很直接，但是一点都不好。让我们在脑子里面最后想想这种充满臭味的代码，你难道忍心你的代码是这样的吗？看来我们要用其他的方法来作，至少看上去要聪明一些的方法。
　　不如我们不考虑边界的问题，这样不就简单了。：）由于我们计算的是“1”的个数，所以我们把一个4×4的数组加一个由“0”组成的边框。这样就没有“出界”问题了。由于我们的数组是4×4,那么我们这么写：

tmpArray=zeros((6,6)) 
tmpArray[1:5,1:5]=PosSol.copy()

　　然后把我们需要的3×3的“抠出来”：

TxT=take(take(tmpArray, [x,x+1,x+2]),[y,y+1,y+2], axis=1)#TxT:Three X Three Square

　　好了，现在我们只要去掉四个角的数，然后求和判断是不是奇数就知道灯泡是不是点亮了：

putmask(TxT,[1,0,1,0,0,0,1,0,1],0) 
value=sum(sum(finalSquare),1)

　　现在我们全部汇总就得到了游戏的解法，顺便作些小的改动就得到了n×n的算法了：

#!/usr/bin/python 
# -*- coding: gb2312 -*- 
#Filename:first.py 
  
  
from numarray import * 
import numarray.strings as nastr 
from bin import bstr 
  
def light(n): 
   PosSol=[reshape(nastr.array(bstr(x).zfill(n*n), itemsize=1),n,n).eval() for x in xrange(2**(n*n))]#PosSol:Possible Solutions 
   tmpArray=zeros((n+2,n+2)) 
   for i in PosSol:  
      tmpArray[1:n+1,1:n+1]=i.copy() 
      Neg=False 
      for x in range(n): 
         if Neg: 
            break    
         for y in range(n): 
            if Neg: 
               break 
            TxT=take(take(tmpArray, [x,x+1,x+2]),[y,y+1,y+2], axis=1)#TxT:Three X Three Square 
        putmask(TxT, [1,0,1,0,0,0,1,0,1], [0]) 
        value=sum(sum(TxT)) 
        if not (value%2):#找到一个没有点亮就不用判断剩余的了 
               Neg=True 
      if not Neg: 
         print i 
         print "Total steps:%d" % sum(sum(i)) 
  
tests = [2, 3, 4] 
for xx in tests 
   print "solution for %d*%d" % (xx,xx) 
   light(xx)

太晚了，趁还没下班先把东西收拾了，下班回家睡觉。:-)

第二天
　　我们完成了一个求解的程序，但是我们还不能高兴，注意到first.py最后的注释没？因为运算量太大，连5×5都完成不了（或者很难完成），就别说更大的了。看来我们还要作一些大的改进才行。
　　让我们再琢磨琢磨我们的在理论分析中得到的一些信息。嗯~既然灯泡的状态之和“影响格”有关，那么是否意味着开关开启的顺序是无关的？看来我们有了一个突破口。一行一行的求解的可能性是有的，但是我们要怎么作呢？让我们先来分析一下。
　　我们从上往下考虑，如果先确定了第一行的开关状态，那么能影响这一行的就只有第二行;确定了第二行以后能影响它的就只有第三行……这样类推的话，我们只要穷举第一行可能的情况，然后从下面一行开始，保证上面一行的灯泡全亮。这样循环下去，到最后一行完成的时候如果就能确定这是否是一个解。看来我们从2**(n*n)已经化简到了2*n。好~好的很。
　　为了避免不停计算灯泡的状态，我们专门为灯泡状态添加一个表。有了昨天的基础，今天看来可以很快完成。：）
　　首先得到得到第一行的所有组合：

PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)]

　　嗯~让我们停下来一下。当我们得到了第一行的灯泡状态以后，我们就确定了第二行的开关状态。由于能影响第一行的只剩第二行的开关，那么我们其实只要把第一行的灯泡状态取反就得到了第二行的开关状态。对开关状态的判断也简单了，只需要对上两行的灯泡状态判断就可以了，真是比昨天的简单多了。

PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)] 
lightStats=zeros((n, n))#灯泡的状态 
solution=zeros((n, n))#解 
tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
for i in PosSol: 
　solution[0:1]=i.copy() 
　tmpArray[0, :]=0 
　tmpArray[1,1:-1]=i.copy() 
　for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
　　TxT = [take(tmpArray, [x, x+1, x+2], axis=1) for x in range(n)]  
　　[putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#我们要由上一行得到下一行的状态 
　　solution[line+1:line+2, :]=[(sum(sum(item))+1)%2 for item in TxT]

　　然后计算最后一行的灯泡状态得到是否是解：

def lightstats(switchstats, n): 
  TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]
  [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子
  return [(sum(sum(item)))%2 for item in TxT]

　　好了，配件齐全，开始组装：

#!/usr/bin/python 
# -*- coding: utf8 -*- 
#Filename:second2.py 
  
from numarray import * 
import numarray.strings as nastr 
from bin import bstr 
  
def lightstats(switchstats, n): 
   TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]  
   [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子 
   return [(sum(sum(item)))%2 for item in TxT] 
  
def light(n): 
   PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval() for x in xrange(2**n)] 
   solution=zeros((n, n))#解 
   tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
   for i in PosSol: 
      solution[0:1]=i.copy() 
      tmpArray[0, :]=0 
      tmpArray[1,1:-1]=i.copy() 
      for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
         solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n) 
         tmpArray[:,1:-1]=solution[line:line+2, :] 
      if sum(lightstats(tmpArray, n))==n: 
         print solution 
         print "Total steps:%d" % sum(sum(solution)) 
  
tests = [2,3,4,5,6] 
for xx in tests: 
   print "solution for %d*%d" % (xx,xx) 
   light(xx)

　　现在就算算10×10也不会很久啦，哈哈~~不过代码还有可以商量的地方，明天继续。

第三天
　　到目前为止，我们的进展都很顺利。不过我们的代码速度还不是很快，应该还有改进的余地。
　　昨天我们使用第一行生成了一个包含2^n个序列的list，我们认真看看，就会发现中间很多是对称的，比如n=3的时候100,001对称，110,011对称。按照我们的算法，这些对称的的序列最后得到的开关桩状态也是对称的，那么我们把每得到一个解，就可以把对称的第一行组合去掉。那么同理，如果第一行的某一个组合不是解，那么我们也可以把他去掉。这样不就减少了很多的循环次数啦。
　　首先判断list是否对称：

def symmetric(alist):#判断list是否对称 
  leng=len(alist) 
  le=alist[:(leng/2)] 
  ri=alist[-(leng/2):] 
  ri.reverse() 
  if le!=ri: 
    alist.reverse() 
    return alist 
  else: 
    return None

　　其他的都一样，我们在昨天的基础上修改一下就好了：

def light(n): 
  PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)] 
  solution=zeros((n, n))#解 
  tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
  try: 
    for i in range(len(PosSol)): 
      i=PosSol[i][:] 
      solution[0:1]=i 
      tmpArray[0, :]=0 
      tmpArray[1,1:-1]=i 
      for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
        solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n) 
        tmpArray[:,1:-1]=solution[line:line+2, :] 
      if sum(lightstats(tmpArray, n))==n: 
        steps=sum(sum(solution)) 
        print solution 
        print "Total steps:%d" % steps 
        rev=symmetric(i) 
        if rev!=None: 
          print solution[:,::-1] 
          print "Total steps:%d" % steps 
          PosSol.remove(rev) 
  except: 
    pass

　　注意for i in range(len(PosSol))这句，这个是很多初学python的人在循环上犯的错。但是我们这里这么作是有原因的。在如果直接写for i in PosSol，那么在循环体中间对PosSol的操作不会得到你想要的结果，所以我们这样避免了这样的问题。i=PosSol[i][:]是产生一个拷贝。免得对PosSol里面产生影响。
　　下面就是代码：

#!/usr/bin/python 
# -*- coding: utf8 -*- 
#Filename:third2.py 
  
from numarray import * 
import numarray.strings as nastr 
from bin import bstr 
  
def lightstats(switchstats, n): 
  TxT = [take(switchstats, [x, x+1, x+2], axis=1) for x in range(n)]  
  [putmask(item, [1,0,1,0,0,0], [0]) for item in TxT]#去掉不相关的格子 
  return [(sum(sum(item)))%2 for item in TxT] 
  
def symmetric(alist):#判断list是否对称 
  leng=len(alist) 
  le=alist[:(leng/2)] 
  ri=alist[-(leng/2):] 
  ri.reverse() 
  if le!=ri: 
    alist.reverse() 
    return alist 
  else: 
    return None 
  
def light(n): 
  PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)] 
  solution=zeros((n, n))#解 
  tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
  try: 
    for i in range(len(PosSol)): 
      i=PosSol[i][:] 
      solution[0:1]=i 
      tmpArray[0, :]=0 
      tmpArray[1,1:-1]=i 
      for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
        solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n) 
        tmpArray[:,1:-1]=solution[line:line+2, :] 
      if sum(lightstats(tmpArray, n))==n: 
        steps=sum(sum(solution)) 
        print solution 
        print "Total steps:%d" % steps 
        rev=symmetric(i) 
        if rev!=None: 
          print solution[:,::-1] 
          print "Total steps:%d" % steps 
          PosSol.remove(rev) 
  except: 
    pass 
  
if __name__ == "__main__": 
  tests = [2,3,4,5,6,7,8,9,10] 
  for xx in tests: 
    print "solution for %d*%d" % (xx,xx) 
    light(xx)

　　既然可以用对称得到解，那么也可以用对称排除不是解的组合：

def light(n): 
  PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)] 
  solution=zeros((n, n))#解 
  tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
  try: 
    for i in range(len(PosSol)): 
      i=PosSol[i][:] 
      solution[0:1]=i 
      tmpArray[0, :]=0 
      tmpArray[1,1:-1]=i 
      for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
        solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n) 
        tmpArray[:,1:-1]=solution[line:line+2, :] 
      rev=symmetric(i) 
      if sum(lightstats(tmpArray, n))==n: 
        steps=sum(sum(solution)) 
        print solution 
        print "Total steps:%d" % steps        
        if rev!=None: 
          print solution[:,::-1] 
          print "Total steps:%d" % steps 
          PosSol.remove(rev) 
      else: 
        if rev!=None: 
          PosSol.remove(rev)        
  except: 
    pass

　　这是新的light函数。不过我们想想，我们可以把解进行旋转，得到的就是其他的解，但是不是解的组合不能旋转排除哦，原因嘛，想想就明白了。我们写一个旋转的函数：

def rotatearray(array): 
  o=zeros(shape(transpose(a))) 
  for i in range(len(a)): 
    b[:,i]=a[i,::-1] 
  return o

　　那么就是修改以后的light函数：

def light(n): 
  allSolutions=[] 
  PosSol = [nastr.array(bstr(x).zfill(n), itemsize=1).eval().tolist() for x in xrange(2**n)] 
  solution=zeros((n, n))#解 
  tmpArray=zeros((2, n+2))#用来存放每一行的开关状态 
  try: 
    for i in range(len(PosSol)): 
      i=PosSol[i][:] 
      solution[0:1]=i 
      tmpArray[0, :]=0 
      tmpArray[1,1:-1]=i 
      for line in range(n-1):#取n-1是因为第一行是生成的，不需要计算      
        solution[line+1:line+2, :]=ones((1, n))-lightstats(tmpArray, n) 
        tmpArray[:,1:-1]=solution[line:line+2, :] 
      if sum(lightstats(tmpArray, n))==n: 
        steps=sum(sum(solution)) 
        temp=solution 
        for j in range(2): 
          for k in range(4): 
            temp=rotateArray(temp) 
            if temp.tolist() not in allSolutions: 
              allSolutions.append(temp.tolist()) 
              print temp 
              print "Total steps:%d" % steps 
            try: 
              PosSol.remove(temp[0, :].tolist()) 
            except: 
              pass 
          temp=transpose(temp) 
      else: 
        try: 
          PosSol.remove(rev) 
        except: 
          pass 
  except: 
    pass

我们去掉了判断对称的函数，直接使用remove，跳过错误信息。定义了allSolutions来避免重复。
现在来总测试一下我们的成果吧：

程序         　  n         时间
first.py      2~4     real 3m16.271s
second.py    2~10   real 2m32.655s
second2.py  2~10   real 2m38.275s
third.py      2~10   real 2m28.386s
third2.py　2~10   real 1m32.934s
third3.py    2~10   real 1m17.786s