抖音热门游戏Fill one-line puzzle game解法的Python代码实现

版权声明：原创文章，转载请注明出处

导语

最近刷抖音的时候，发现经常有人提问一个游戏的解法，于是去下载了这款游戏，发现还挺好玩的。

这个游戏的玩法也很简单，就是一笔画成。比如像这样

我以为这个游戏很火，其实AppStore的下载量才寥寥几千。趁它还没有完全火起来，用Python写了一个小程序，可以列出这个游戏的解法。

思路

五个字，运用回溯法。
用两个List：
（1）List1是二维的，模拟整个表格，1代表起点，0代表原始的可以经过的点，-1代表原始的不能通过的点，比如本图

其List应该是这样的

如果移动到某一个点，则该点的值等于已经走过的步数，以记录移动路径。
（2）List2是三维的，用以记录每个点已经尝试了的路径，比如List2[1][1][2]=1，表示第一行第一列这个点已经尝试了向下（1代表上，2代表下，3代表左，4代表右），可避免重复。

从起点开始移动，按上下左右的方向去尝试，如果移动到某一个点，无法再移动了，就判断是否到达了终点，如果没有到达终点，则清空该点的记录信息（路径记录和已经尝试的路径记录），并往回退一步。循环该操作直到走到终点。

代码

import numpy as np
#初始化
Row=int(input('请输入行数：'))
Col=int(input('请输入列数：'))
list_path=np.zeros((Row,Col),dtype=int) #路径记录
list_pathrecord=np.zeros((Row,Col,4),dtype=int) #已尝试路径记录
cord=input("请输入起点坐标，以','隔开：")
list_path[int(cord[0])-1][int(cord[2])-1]=1
i_initial=int(cord[0])-1 #记录起点坐标
j_initial=int(cord[2])-1
i_tmp=int(cord[0])-1 #起点坐标
j_tmp=int(cord[2])-1
while 1:
    cord=input("请输入空白点坐标，以','隔开，如果已输入完毕请按回车：")
    if cord!='':
        list_path[int(cord[0])-1][int(cord[2])-1]=-1
    else:
        break
steps=np.sum(list_path==0)+1 #所需步数，加上起点
stepcount=1 #步数记录

def MoveTest(i,j,mType): #坐标和移动方式，判断是否可移动
    flag=False
    if mType==1: #向上
        if i!=0 and list_path[i-1][j]==0 and list_pathrecord[i][j][0]==0:
            flag=True
    elif mType==2: #向下
        if i!=Row-1 and list_path[i+1][j]==0 and list_pathrecord[i][j][1]==0:
            flag=True
    elif mType==3: #向左
        if j!=0 and list_path[i][j-1]==0 and list_pathrecord[i][j][2]==0:
            flag=True
    elif mType==4: #向右
        if j!=Col-1 and list_path[i][j+1]==0 and list_pathrecord[i][j][3]==0:
            flag=True
    return flag

def ReturnTest(i,j): #判断是否回头
    flag=True
    for s in range(1,5):
        if MoveTest(i,j,s):
            flag=False
            break
    return flag

def Move():
    global i_tmp
    global j_tmp
    global stepcount
    if ReturnTest(i_tmp,j_tmp) and stepcount!=steps: #需要回头并且未达到终点
        if i_tmp==i_initial and j_tmp==j_initial:  #判断是否无解
            print('无解！')
            stepcount=steps #跳出循环
        else:
            for s in range(4):
                list_pathrecord[i_tmp][j_tmp][s]=0 #清空该坐标已尝试路径记录
            list_path[i_tmp][j_tmp]=0 #清空该坐标路径记录
            for m in range(Row): #查找上一步坐标
                p=0 #跳出循环判断
                for n in range(Col):
                    if list_path[m][n]==stepcount-1:
                        i_tmp=m
                        j_tmp=n
                        p=1
                        break
                if p==1:
                    break
            stepcount-=1 #步数减1
    elif stepcount==steps: #达到终点
        pass
    else:
        for x in range(1,5):
            if MoveTest(i_tmp,j_tmp,x):
                list_pathrecord[i_tmp][j_tmp][x-1]=1 #记录已尝试路径
                if x==1: #移动一步
                    i_tmp-=1
                elif x==2:
                    i_tmp+=1
                elif x==3:
                    j_tmp-=1
                elif x==4:
                    j_tmp+=1
                stepcount+=1 #步数加1
                list_path[i_tmp][j_tmp]=stepcount #记录路径
                break
        
while stepcount!=steps:
    Move()

print(list_path)

验证

运行的结果如下

验证解法确实成功了

谢谢小李同学的提醒，加上了无解的判断，不然如果无解就进入死循环了！