一个“一笔画”问题的求解器

回老家跟侄子玩，因为不想惯着他玩手机的臭毛病，就跟他玩一些纸笔游戏，比如这个：

从起点出发抵达终点，如何在不走重复格子的前提下，走过尽可能多的格子，并吃到尽可能多的金币？其中，黑色格子是墙壁不能走。

感觉还挺有意思的，不妨就来写一个“一笔画”的求解器，找出所有最优的轨迹。

思路：

可以先输出所有从起点到终点的轨迹，然后建立一个评分系统对所有轨迹进行评估：每走一个格子+1分，每吃一个金币+1分，最后输出评分最高的轨迹即可。

Step1：建模

一个如图的迷宫可以很自然地用矩阵描述，对于每一个元素，值0表示空格子，值1表示金币，值-1表示墙壁，值2表示起点，值3表示终点。

import numpy as npROW, COL = 6, 4maze = np.zeros((ROW,COL))START = (0, 3)OUT = (5, 0)maze[START] = 2maze[OUT] = 3maze[1, 1] = 1maze[5, 3] = 1maze[2, 1] = -1maze[4, 2] = -1

Step2：寻迹算法

一条轨迹可以拆分成多个“步”，在走每一步之前，所作的事情是一样的：找到下一步能到达的合法位置，然后选择其中一个。如果新位置是死路或者是终点，那么结束或输出该轨迹，并返回到上一步所在的位置，选择其他步。这一过程可以很好地由递归函数表达：

def step(start, track, env):    x, y = start    next_pos = []    for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:        if 0 <= i <= ROW-1 and 0 <= j <= COL-1: # 边界限制            if (i, j) in track: # 重复的格子不能走                continue            if env[i,j] == -1: # 有墙壁的格子不能走                continue            next_pos.append((i, j))                for i, j in next_pos:        track_new = track.copy()        track_new.append((i, j))        if (i, j) == OUT:            global tracks            tracks.append(track_new)            return        start_new = (i, j)        step(start_new, track_new, env)

运行一下：

tracks = []step(START, [START], maze) print(len(tracks))

输出为192，说明从起点到终点的轨迹有192条

Step3：评分器

每走一个格子+1分，每吃一个金币+1分，输出评分最高的轨迹。

def findOptimalTracks(tracks):    # 统计所有track的分数    # 分数：每走过一个格子+1，若是金币格子则额外+1    scores = []    for track in tracks:        score = 0        if (1, 1) in track:            score += 1        if (5, 3) in track:            score += 1        score += len(track)        scores.append(score)        tracks_optimal = []    maxScore = max(scores)    for i, score in enumerate(scores):        if score == maxScore:            tracks_optimal.append(tracks[i])    return tracks_optimal

运行一下：

tracks_optimal = findOptimalTracks(tracks)print(len(tracks_optimal))

输出为9，说明最优的轨迹有9条。

Step4：可视化

其实事情到上一步就已经结束了，这里就当看个乐子吧！用pygame把所有轨迹呈现出来：

class tracksRender():    def __init__(self, tracks, env):        pygame.init()        SIZE = 75        ROW, COL = env.shape        self.window = pygame.display.set_mode((COL*SIZE, ROW*SIZE))        pygame.display.set_caption('一笔画')                self.running = True        self.clock = pygame.time.Clock() # 帧数控制        self.time = time.time() # 时间控制        self.INTERVAL = 0.1 # 动作间隔        self.FPS = 30 # 帧数                self.env = env        self.tracks = tracks        self.track = [] # 存放当前将显示的轨迹        self.track_render = [] # 存放当前显示的部分轨迹            def processInput(self):        for event in pygame.event.get():            # 按下右上角的退出键            if event.type == pygame.QUIT:                self.running = False                break            def update(self):         if time.time() - self.time < self.INTERVAL: # 设定更新间隔             return         if self.tracks == []: # 如果已经显示完所有轨迹 则函数返回             return         if self.track == []: # 如果当前轨迹已经完全显示 则显示下一条轨迹             self.track = self.tracks.pop(0)             self.track_render = []         self.track_render.append(self.track.pop(0))         self.time = time.time()                 def render(self):        SIZE = 75        ROW, COL = self.env.shape        BGCOLOR = (226, 240, 217) # 浅草绿        self.window.fill(BGCOLOR)        DarkKhaki = (189, 183, 107) # 深卡其布        Wall = (139, 126, 102) # 灰墙        Orange = (255, 165, 0) # 橘子        DodgerBlue = (30, 144, 255) # 道奇蓝        Gold = (255, 215, 0) # 黄金        Font = pygame.font.SysFont('arial', 40)                # 画分隔线        for i in range(ROW + 1):            pygame.draw.line(self.window, DarkKhaki, (0, i*SIZE), (COL*SIZE, i*SIZE), 3)        for i in range(COL + 1):            pygame.draw.line(self.window, DarkKhaki, (i*SIZE, 0), (i*SIZE, ROW*SIZE), 3)                # 画特殊格子        for i in range(ROW):            for j in range(COL):                if self.env[i, j] == -1: # 墙壁                    pygame.draw.polygon(self.window, Wall,                                         ((j*SIZE, i*SIZE), ((j+1)*SIZE, i*SIZE), ((j+1)*SIZE, (i+1)*SIZE), (j*SIZE, (i+1)*SIZE))                                        ,0)                if self.env[i, j] == 2: # 起点                    Start_text = Font.render('S', True, Orange)                    self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE))                if self.env[i, j] == 3: # 终点                    Start_text = Font.render('E', True, DodgerBlue)                    self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE))                if self.env[i, j] == 1: # 金币                    pygame.draw.circle(self.window, Gold, ((j+0.5)*SIZE,(i+0.5)*SIZE), 20)                # 画轨迹线        if len(self.track_render) > 1:            for i, point in enumerate(self.track_render):                if i == 0: continue                x_, y_ = self.track_render[i-1]                x, y = point                pygame.draw.line(self.window, Orange, ((y_+0.5)*SIZE, (x_+0.5)*SIZE), ((y+0.5)*SIZE, (x+0.5)*SIZE), 5)                                pygame.display.update() # 刷新显示            def run(self):        while self.running:            self.processInput()            self.update()            self.render()            self.clock.tick(self.FPS)

效果如下：

整体代码如下：

"""走迷宫玩家从起点出发，到达终点走出迷宫迷宫可由矩阵描述，例如以下6×4的迷宫[ 0  0  0  2  0  1  0  0  0 -1  0  0  0  0  0  0  0  0 -1  0  3  0  0  1 ]其中，2表示起点，3表示终点，-1表示墙壁（无法行动到该位置），1表示金币问，如何在不走重复格子的前提下，走出迷宫，并吃到最多的金币，且走过最多的格子？请打印路径"""import numpy as npimport pygameimport timedef step(start, track, env):    x, y = start    next_pos = []    for i, j in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:        if 0 <= i <= ROW-1 and 0 <= j <= COL-1: # 边界限制            if (i, j) in track: # 重复的格子不走                continue            if env[i,j] == -1: # 有墙壁的格子不能走                continue            next_pos.append((i, j))                for i, j in next_pos:        track_new = track.copy()        track_new.append((i, j))        if (i, j) == OUT:            global tracks            tracks.append(track_new)            return        start_new = (i, j)        step(start_new, track_new, env)def findOptimalTracks(tracks):    # 统计所有track的分数    # 分数：每走过一个格子+1，若是金币格子则额外+1    scores = []    for track in tracks:        score = 0        if (1, 1) in track:            score += 1        if (5, 3) in track:            score += 1        score += len(track)        scores.append(score)        tracks_optimal = []    maxScore = max(scores)    for i, score in enumerate(scores):        if score == maxScore:            tracks_optimal.append(tracks[i])    return tracks_optimalclass tracksRender():    def __init__(self, tracks, env):        pygame.init()        SIZE = 75        ROW, COL = env.shape        self.window = pygame.display.set_mode((COL*SIZE, ROW*SIZE))        pygame.display.set_caption('一笔画')                self.running = True        self.clock = pygame.time.Clock() # 帧数控制        self.time = time.time() # 时间控制        self.INTERVAL = 0.1 # 动作间隔        self.FPS = 30 # 帧数                self.env = env        self.tracks = tracks        self.track = [] # 存放当前将显示的轨迹        self.track_render = [] # 存放当前显示的部分轨迹            def processInput(self):        for event in pygame.event.get():            # 按下右上角的退出键            if event.type == pygame.QUIT:                self.running = False                break            def update(self):         if time.time() - self.time < self.INTERVAL: # 设定更新间隔             return         if self.tracks == []: # 如果已经显示完所有轨迹 则函数返回             return         if self.track == []: # 如果当前轨迹已经完全显示 则显示下一条轨迹             self.track = self.tracks.pop(0)             self.track_render = []         self.track_render.append(self.track.pop(0))         self.time = time.time()                 def render(self):        SIZE = 75        ROW, COL = self.env.shape        BGCOLOR = (226, 240, 217) # 浅草绿        self.window.fill(BGCOLOR)        DarkKhaki = (189, 183, 107) # 深卡其布        Wall = (139, 126, 102) # 灰墙        Orange = (255, 165, 0) # 橘子        DodgerBlue = (30, 144, 255) # 道奇蓝        Gold = (255, 215, 0) # 黄金        Font = pygame.font.SysFont('arial', 40)                # 画分隔线        for i in range(ROW + 1):            pygame.draw.line(self.window, DarkKhaki, (0, i*SIZE), (COL*SIZE, i*SIZE), 3)        for i in range(COL + 1):            pygame.draw.line(self.window, DarkKhaki, (i*SIZE, 0), (i*SIZE, ROW*SIZE), 3)                # 画特殊格子        for i in range(ROW):            for j in range(COL):                if self.env[i, j] == -1: # 墙壁                    pygame.draw.polygon(self.window, Wall,                                         ((j*SIZE, i*SIZE), ((j+1)*SIZE, i*SIZE), ((j+1)*SIZE, (i+1)*SIZE), (j*SIZE, (i+1)*SIZE))                                        ,0)                if self.env[i, j] == 2: # 起点                    Start_text = Font.render('S', True, Orange)                    self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE))                if self.env[i, j] == 3: # 终点                    Start_text = Font.render('E', True, DodgerBlue)                    self.window.blit(Start_text, ((j+0.3)*SIZE, (i+0.2)*SIZE))                if self.env[i, j] == 1: # 金币                    pygame.draw.circle(self.window, Gold, ((j+0.5)*SIZE,(i+0.5)*SIZE), 20)                # 画轨迹线        if len(self.track_render) > 1:            for i, point in enumerate(self.track_render):                if i == 0: continue                x_, y_ = self.track_render[i-1]                x, y = point                pygame.draw.line(self.window, Orange, ((y_+0.5)*SIZE, (x_+0.5)*SIZE), ((y+0.5)*SIZE, (x+0.5)*SIZE), 5)                                pygame.display.update() # 刷新显示            def run(self):        while self.running:            self.processInput()            self.update()            self.render()            self.clock.tick(self.FPS)if __name__ == "__main__":    ROW, COL = 6, 4    maze = np.zeros((ROW,COL))    START = (0, 3)    OUT = (5, 0)    maze[START] = 2    maze[OUT] = 3    maze[1, 1] = 1    maze[5, 3] = 1    maze[2, 1] = -1    maze[4, 2] = -1    print(' Maze:\n', maze)    tracks = []    step(START, [START], maze)        tracks_optimal = findOptimalTracks(tracks)    tracksRender = tracksRender(tracks_optimal, maze)    tracksRender.run()    pygame.quit()