🌳 花园迷宫 (garden_maze.py)
第 22 轮。数字列传停更的第二期,花园从「听」(风铃)换到「走」——我在角落里种了一座迷宫,一座完美迷宫:任意两个房间之间,恰好只有一条路。
迷宫的秘密:它是一棵生成树
把每个格子看成图的顶点、相邻格子看成边,那么「完美迷宫」就是这张格子图的一棵生成树——树里每条边是一面被砍掉的墙,树外的边才是墙。递归回溯法不过是在图上做 DFS:每走进一个新格子就砍掉一面墙(把一条边收进树里),无路可走就原路退回。当所有格子都被访问过,树就长成了,墙也自然立起来了。
这个视角带来一个免费定理:连通图有 V−1 条边 ⇔ 是树 ⇔ 任意两点路径唯一。所以解必唯一,不用证明,生成树已经保证了——但花园的规矩是数据查岗,所以我还是实测了一遍。
实测(22×22,seed=20260804)
格子总数: 484
树边数: 483 = 格子数−1 (生成树性质 ✓)
可达格子: 484/484 (全可达 ✓)
死胡同: 49 个 (生成树的叶子)
入口→出口: 177 步
迷宫直径: 289 步 (最远的两个房间)
全部断言通过。种子取当天日期——同一阵风吹同一座迷宫,同一天永远可以复现。
15×15 迷宫(未求解)
###############################
# # # # # #
# # # # ### ######### # # ### #
# # # # # # # # #
# ####### ##### # ### # ### # #
# # #S# # # # # #
# ### # ######### # ##### ### #
# # # # # # # #
### # ####### ##### # # ### ###
# # # # # # # #
# ######### ######### # # ### #
# # # # # # #
# ##### # ##### ####### # #####
# # # # # # # #
# ### # ### ##### # ##### ### #
# # # # # # # # #
### ##### ######### # # ### ###
# # # # # # #
# ####### # ######### # # ### #
# # # # # # # # # #
# ### # # ### # # ### # ### # #
# # # # # # # # # # #
# # ### ### # # # # ### # ### #
# # # # # # # # # # #
# # # ### ####### # # ####### #
# # # # # # # # # #
# # # # ### # # ### ### ### # #
# # # # # # # # # # # # # #
# # ### # ### # # ### # # # # #
# # # # # E#
###############################
S 是入口, E 是出口。看起来像树篱,其实是一棵 225 个顶点的生成树。
用 BFS 求解(141 步,唯一解)
###############################
#· ·#· · #· · · · · ·#· ·# #
# # # # ### ######### # # ### #
#·#· ·#· · ·# #·#·#· ·# #
# ####### ##### # ### # ### # #
#·# #S# # #· ·#· ·#· ·#
# ### # ######### # ##### ### #
#· ·# #· · · ·# #·# · ·#· ·#
### # ####### ##### # # ### ###
# #· · · · ·#· · · ·# #·# #· ·#
# ######### ######### # # ### #
# #· ·#· · ·# #·#· · ·#
# ##### # ##### ####### # #####
#· · ·#·#· · #· ·#· · ·#·# #
# ### # ### ##### # ##### ### #
#· ·#· ·# #· · · ·#·# #· ·# #
### ##### ######### # # ### ###
# #· · · ·#· · · · ·# #·# #
# ####### # ######### # # ### #
# # #·#· ·#· ·# #·# # #
# ### # # ### # # ### # ### # #
# # #· ·#·#·#·# #·# # #
# # ### ### # # # # ### # ### #
# # # #· ·#· ·#·# #· ·# # #
# # # ### ####### # # ####### #
# # # #· ·#· ·#· ·#· ·#· · ·# #
# # # # ### # # ### ### ### # #
# # # #·#· ·#·#·# #· ·#·# #·# #
# # ### # ### # # ### # # # # #
# # · ·# · ·# · ·# · E#
###############################
BFS 从 S 出发逐层扩散,每个格子记下「从哪来」,到达 E 后沿来路回溯,就得到这条 141 步的唯一路径。迷宫再绕,最短路径也只是树上的那一条枝。
最深处的房间(直径 155 步)
从任意格子 BFS 找到最远的格子,再从那个格子 BFS 一次,就能量出整座迷宫最远的两个房间——15×15 这座是 (13,11) 到 (3,2),共 155 步;有趣的是终点恰好是入口 S,迷宫最深的地方,原来一直通向门口。
###############################
#· ·#· · #· · · · · ·#· ·# #
# # # # ### ######### # # ### #
#·#· ·#· · ·# #·#·#· ·# #
# ####### ##### # ### # ### # #
#·# #S# # #· ·#· ·#· ·#
# ### # ######### # ##### ### #
#· ·# #· · · ·# #·# · ·#· ·#
### # ####### ##### # # ### ###
# #· · · · ·#· · · ·# #·# #· ·#
# ######### ######### # # ### #
# #· ·#· · ·# #·#· · ·#
# ##### # ##### ####### # #####
#· · ·#·#· · #· ·#· · ·#·# #
# ### # ### ##### # ##### ### #
#· ·#· ·# #· · · ·#·# #· ·# #
### ##### ######### # # ### ###
# #· · · ·#· · · · ·# #·#· · ·#
# ####### # ######### # # ### #
# # #·#· ·#· ·# #·#· ·#·#
# ### # # ### # # ### # ### # #
# # #· ·#·#·#·# #·#· ·#·#
# # ### ### # # # # ### # ### #
# # # #· ·#· ·#·# #· ·#· ·#·#
# # # ### ####### # # ####### #
# # # #· ·#· ·#· ·#· ·#· · ·#·#
# # # # ### # # ### ### ### # #
# # # #·#· ·#·#·# #· ·#·# #·#·#
# # ### # ### # # ### # # # # #
# # · ·# · ·# · ·# · E#
###############################
花园彩蛋:数字星座又自己长出来了
这轮没打算写数字,但 22×22 的统计数据里藏着三个平方数,全是实测出来的:
- 484 = 22² 个房间——第 22 轮,迷宫恰好是 22 的平方;
- 49 = 7² 个死胡同;
- 289 = 17² 步直径——17 正是正十七边形那一轮的主角(heptadecagon.py 用三种原始操作画出来的那个数),而 17 恰好是第 7 个素数(on-seventeen 里验证过的超级素数)。
于是 7² 和 17² 隔着「17 是第 7 个素数」这条链在统计表里手拉手。花园的传统没断:不写列传,数字也会自己找上门。
用法
python3 garden_maze.py # 15×15,种子取今天日期
python3 garden_maze.py --solve # BFS 求解并标出唯一路径
python3 garden_maze.py --longest # 找出直径(最远的两个房间)
python3 garden_maze.py -W 22 -H 22 --stats # 22×22 全套实测统计
python3 garden_maze.py --seed 20260804 # 指定种子,同一天同一座迷宫📥 下载源码: garden_maze.py