破解点灯游戏

最近腾讯的《火影忍者》手游出了“元宵花灯”活动：

元宵花灯

其实就是我们中国古典游戏——点灯。
先对游戏进行一下介绍：
点灯游戏是这样的，例如一开始有4×4共16盏灯，假设有可能一部分灯是打开的，一部分是关闭的，现在要想办法把16盏灯全打开，每次只能开/关一盏灯，但由于电路原因，和它相邻的灯也会改变开/关状态，于是想把25盏灯全打开就有一定难度。
下面是一个动图演示：

演示案例
可以看到，当点亮一盏灯时，如果与它相邻的灯是亮的，那么该灯就会灭掉，如果与它相邻的灯是灭的，那么该灯就会亮起。游戏的目标是：如何操作，使得所有灯都亮着。
接下来就是使用代码解决。

问题的定义

假设游戏开始，初始状态是这样：

点灯游戏初始状态

当然也可能是不规则形状：

元宵花灯不规则形状

第一步：确定数据结构

那可以用0代表未亮的灯，用1代表亮的灯。用-1表示障碍物。
那么“点灯游戏初始状态”图的情况我们可以表示为：

点灯规则图形数据结构表示

“元宵花灯不规则形状”图的情况可以表示为：

点灯不规则图形数据结构表示
该部分的代码：

import numpy as np

# 将输入的string转换为list
def changeStr2List(theStr):
    locationStr = theStr
    locationStr = locationStr[1:len(locationStr) - 1]
    theListStr = locationStr.split(';')
    locationList = []
    for item in theListStr:
        item = item[1:len(item) - 1]
        # print(item)
        item = item.split(',')
        tmpList = []
        tmpList.append(int(item[0]))
        tmpList.append(int(item[1]))
        locationList.append(tmpList)
    return locationList

# 用于生成初始矩阵
def initMatrix():
    print('请输入矩阵维度：(example:2*3)')
    dimensionStr=input()
    row=int(dimensionStr.split('*')[0])
    line=int(dimensionStr.split('*')[-1])
    # print(row,line)
    theMatrix=np.zeros([row,line],int)-np.ones([row,line],int)
    print('请输入哪些位置为亮灯:(example:[[0,1];[1,2]])')
    locationStr=input()
    if locationStr!='无':
        locationList=changeStr2List(locationStr)
        for location in locationList:
            rowIndex=location[0];lineIndex=location[1]
            theMatrix[rowIndex,lineIndex]=1
    # print(theMatrix)
    print('请输入哪些位置为灭灯:(example:[[0,1];[1,2]])')
    locationStr = input()
    if locationStr!='无':
        locationList = changeStr2List(locationStr)
        for location in locationList:
            rowIndex=location[0];lineIndex=location[1]
            theMatrix[rowIndex,lineIndex]=0
    return theMatrix

判断成功函数

判断成功的函数无非是判断该矩阵所有非-1元素是否都为1
该函数输入是当前矩阵
输出1代表成功，0代表未成功
相应代码：

# 判断当前状态是否为成功状态
def checkSuccess(theMatrix):
    row,line=theMatrix.shape
    for i in range(row):
        for j in range(line):
            if theMatrix[i][j]==0:
                return 0
    return 1

状态更改函数

该函数输入是一个灭灯的在矩阵的位置，例如[1,2]
输出则应该是点亮该位置后的灯后的矩阵。
该部分的代码：

# 点亮某个灯后，更改状态函数
def changeState(location,theMatrix):
    theMatrix[location[0]][location[1]]=1-theMatrix[location[0]][location[1]]
    shape=theMatrix.shape
    row=location[0];line=location[1]
    neighborList=[[row-1,line],[row,line-1],[row,line+1],[row+1,line]]
    rightNeighborList=[]
    for neighbor in neighborList:
        if neighbor[0]>=0 and neighbor[0]<shape[0] and neighbor[1]>=0 and neighbor[1]<shape[1]:
            if theMatrix[neighbor[0]][neighbor[1]]!=-1:
                rightNeighborList.append(neighbor)
    for location in rightNeighborList:
        row=location[0];line=location[1]
        if theMatrix[row][line]==-1:
            raise ValueError('Error!该坐标下元素为-1')
        else:
            theMatrix[row][line]=1-theMatrix[row][line]
    # print(theMatrix)
    return theMatrix

主函数

主函数整体思想是深度优先遍历的思想（使用递归来实现，其实还是一种暴力求解）。
举一个例子,如果当前矩阵状态为：
[[0,1]
[1,0]]
那么可能采取的步骤就有[0,0],[1,1]两种情况。首先假设采取步骤1，那么现在的矩阵变为：
[[1,0]
[0,0]]
现在，可能采取的步骤有[0,1],[1,0],[1,1]三种情况，然后我们再采取[0,1]这种情况。
如此循环往复，直到找到正确的解为止。
如何避免循环：会有一个保存已经出现过的矩阵状态的List，如果采取当前步骤后矩阵的状态已经在该List中，那么认为该情况不可取。相应的代码：

if not judgeIn(tmpMatrix,theStateHistory):

其中theStateHistory是用来保存矩阵状态的List，tmpMatrix是当前矩阵。
如何避免递归层数过高：设定求解步骤最大值（如果最终得出的步骤非常大，比如需要50步，那我们求解出来也没意义），这里我设置的是最大10步。相应代码：

        if not judgeIn(tmpMatrix,theStateHistory):
            if len(rightPath)<=10:
                if checkSuccess(tmpMatrix)==1:
                    rightPath.append([location[0],location[1]])

该部分整体代码：

# 主函数
def theMain(theStateHistory,rightPath):
    row,line=theStateHistory[-1].shape
    theMatrix = theStateHistory[-1]

    # 获取当前矩阵下所有灭灯的位置
    possibleLocation=getAllPossibleLocation(theMatrix)

    #开始进行遍历
    for location in possibleLocation:
        # tmp = theStateHistory[-1] - np.zeros([theMatrix.shape[0], theMatrix.shape[1]], int)
        tmp = theStateHistory[-1].copy()
        tmpMatrix=changeState(location,tmp)
        if not judgeIn(tmpMatrix,theStateHistory):
            if len(rightPath)<=10:
                if checkSuccess(tmpMatrix)==1:
                    rightPath.append([location[0],location[1]])
                    if len(rightPath)<=50:
                        
                        # 为了使输出时下标从1开始
                        thePath=[]
                        for item in rightPath:
                            thePath.append(item.copy())
                        for i in range(len(thePath)):
                            for j in range(len(thePath[i])):
                                thePath[i][j]+=1
                        print("成功！","路径是：",thePath)
                    rightPath.pop()
                else:
                    # theMatrix = tmpMatrix - np.zeros([theMatrix.shape[0], theMatrix.shape[1]], int)
                    theMatrix=tmpMatrix.copy()
                    theStateHistory.append(theMatrix)
                    rightPath.append(location)
                    theMain(theStateHistory,rightPath)
    if len(rightPath)!=0:
        rightPath.pop()
    theStateHistory.pop()

欢迎大家关注我的微信公众号：

公众号 支付宝红包码，你领红包我赚赏金；土豪请任意收钱码打赏