关于单箱推箱子的最大最优步数

发表于 2026-09-08 更新于 2026-09-20 分类于笔记

推箱子是一块风靡全球的益智游戏。单箱推箱子指地图上只有一个可推动不可拉动的箱子，和一个目标点的推箱子游戏，玩家将箱子推到目标点即通关。本文主要研究在固定大小的单箱推箱子地图上，最短解步数的最大值。此处人的每次移动计一步。

推箱子地图格式

推箱子关卡一般用 XSB 格式来保存和交流。

字符	含义
`@`	人 (man)
`+`	人在目标点 (man on goal)
`$`	箱子 (box)
`*`	箱子在目标点 (box on goal)
`#`	墙 (wall)
`.`	目标点 (goal)
`-` 或 `_`	地板

答案是 LURD 格式，小写字母是移动，大写字母是推动。

字符	含义
l 或 L	左
r 或 R	右
u 或 U	上
d 或 D	下

本文主要研究单箱推箱子，因此不涉及到箱子在目标点的 * 符号，否则如果箱子与目标点重合则不需要推动就可以完成关卡了。地板统一用 - 表示；允许人在目标点的情况。

设 $n$ 为地图尺寸。$n=1$ 时，没有合法地图。$n=2$ 时，每个格子都是角点，箱子没有任何合法推动，因而不存在有解且非 $0$ 步的关卡；$0$ 步关卡也没有研究的必要。因此，下文中所有 $n\ge 3$。

核心结论

下文中“最优步数/解”均指“最大步数/解”，“最长最优解步数”均指”最大最优解步数“。

设 $M(n)$ 为所有大小为 $n\times n$、恰有一个箱子和一个目标点的关卡中，最短解步数的最大值。则最短解步数的最大值随地图的边长而四次方增长：
$$M(n)=\Theta(n^4)$$

对于几个 $n$ 有可构造的下界：

$n$	$M(n)\ge$
$20$	$3582$
$40$	$25946$
$48$	$107593$

对于较小的 $n$ 有 $M(n)$ 的精确值：

$n$	$M(n)$
$3$	$10$
$4$	$25$
$5$	$41$
$6$	$78$

对 $n=7\sim 10$ 有启发式搜索得出的下界：

$n$	$M(n)\ge$
$7$	$119$
$8$	$159$
$9$	$231$
$10$	$311$

限定空格数的研究

设 $L_k(F)$ 表示最多 $k$ 个箱子，$F$ 个可通行格（包含人、$1$ 个箱子与对应目标点）的最大最短解长度。注意 $L_k(F)$ 中的 $F$ 为可通行格数，而本文所讨论的 $M(n)$ 中的 $n$ 为地图的边长尺寸，二者不相同。

对推箱子最短解步数的最大值问题的最早研究可以追溯到 2000 年。Erich Friedman, Problem of the Month, March 2000 给出了对于 $L_1(F)$ 的一些精确计算与估计。Sokoban Maximums 则给出了更加详细的研究，对 $k=1\dots8$ 箱子的情况给出了一些 $L_k(F)$ 的精确下界与对应构造。

对单一箱子，从 $F=3$ 开始的 $L_1(F)$ 序列 A195668 为
$$1,2,3,5,9,11,15,18,21,25,\dots$$
$L_1(F)$ 有渐进界：
$$\frac{3F^2}{49}\le L_1(F)\le F^2$$

对任意箱子数，从 $F=3$ 开始的 $L_{\infty}(F)$ 序列 A195667 为
$$1, 2, 3, 5, 9, 14, 17, 22, 27, 35,\dots$$

在较大地图上的尝试

$20\times20$

2024 年 1 月，WYXkk 在洛谷上举行了一场 Sokoban Golf 比赛，要求在 $20\times 20$ 的地图上构造一个最优解尽量长的单箱推箱子谜题。很显然，这场比赛成为了笔者写作本文的灵感来源。

笔者参与了这场比赛，使用 22.97h 构造了一个 $3185$ 步的解。比赛的第一名是 EDPZnCl，构造了一个 $3566$ 步的解。WYXkk 本人则构造了一个 $3516$ 步的解，位于第二名。

据该题目 U398206 Sokoban Golf 的描述，本题是 MIT Mystery Hunt 2024 的 Marathon Block Pushing Game 一题的第二部分，原题的要求是一个至少 1000 步的解。

构造方法大多来源于如下的结构（问号代表某段未知路径）:

  ?????
  P   ?
##*## ?
#....??
#...#
#####

玩家从上方把箱子推进来以后，不得不绕问号路径走一圈再继续前进。如果让问号路径足够长，那就能增加很多步数。于是最终步数的多少几乎就是比谁能塞下更多的该结构，当然单圈长度也对答案有一定影响。因此，这场比赛（也就是本文研究的题目）的大方向就几乎变成了增加子结构的数目。

比赛的赛后总结在这里：Sokoban Golf 赛后总结，包含了前十的解。因篇幅原因，本文仅摘录前三名（已做格式转换），绿色代表箱子的路径：

---####--#---##--#--
---------#-------#--
#-#####--##-###--#--
--#---#-###-###-##-#
------#-###--#-----#
--##-#-------#---#-#
####-#---##--#####-#
---#--########--##-#
------#--#--@#------
#-##--#------#--#---
#-#####--##$###-####
--#---##-##--##-##--
------#---##-#------
--##-##---#--#---#--
####--#-##--######-#
------#-#--#----.#-#
--##--#-#-##-##-##-#
--#####-#--#-#--##-#
---------#-#-#------
--####---#---#--#---
Title: 3566
Author: EDPZnCl

@-#-----------------
--$-###############-
--##---##--#---#--#-
---#-------#------#-
----#-###--##-##--#-
#-###--##-###--#-##-
-------#-------#-#--
---##--#---##--#-#-#
###--######--###-#--
--#-------#-------#-
--#--###--#--##---#-
--##-##--###-#####.-
#-----#-------#-----
#-#---#--##---#--#--
#-#############--###
#-#-----#-----#-----
#-#-----#-----#--#--
#-##-##-##-##-####--
-----#-----#--------
-----#-----#---###--
Title: 3516
Author: WYXkk

#------#----#---####
#$####--#-#-#-#-#---
#@##--#---#-#-#-----
------#####---#.##-#
---#--#---########--
####-##-------------
--##-###-###--####--
------##-#--##---###
--#---##-#-------###
#-######-#--###-####
#-##--#--##-##--#---
------#------#------
---#--#--#---#--##-#
####-#############--
--##-##---##--#-----
------#-------#--#--
--#---##-###--##-###
#-######--##-###--##
----------#-------##
---#####--#---##--##
Title: 3368
Author: GoldenFishX

笔者对前十的总步数、推动数、子结构数进行了整理分析，结果如下：

	总步数	推动数	子结构数	圈长
1	3566	110	27	128
2	3516	106	25	136
3	3368	98	26	126
4	3341	90	22	148
5	3314	99	23	140
6	3312	98	23	140
7	3291	83	22	146
8	3255	88	23	138
9	3185	97	22	140
10	3161	105	25	122

总步数与子结构数的比值近似于圈长。

平均下来，比赛前十中，每走 $34.2$ 步才能推动一次箱子，平均圈长为 $136.4$ 步，通过每个子结构需要 $4.1$ 次推动。标准的子结构需要 $4$ 次推动，多出来的 $0.1$ 往往在于空余的空间不够塞子结构了，因此只能利用剩余空间增加圈长。

第一名在 $20\times 20$ 的空间中塞下了 $27$ 个子结构，通过极高效地利用空间来有效提升了总步数。但同时，第二名和第三名的子结构数反转也说明了子结构数多不代表总步数多，同时也要优化圈长。

赛后总结的优化策略是，尽可能地塞下更多子结构；若子结构塞不进去再调整加长圈长。

时间来到了 2026 年 9 月，LLM 的飞速发展让人们瘫坐在椅子上，仿佛看到了原子弹爆炸。笔者又想起了这场比赛和推箱子，因此将上述材料作为参考，尝试使用 LLM 去继续优化，看能不能找出更优秀的解法。

GPT 6 Astra 的尝试过程见附录，最终基于第一名的 $3566$ 解法搜索出了 $3570$ 的一个解，提升了 $4$ 步，另外还对第二名的 $3516$ 解法搜索出了一个 $3522$ 的局部优化解。

---####--#---##--#--
---------#-------#--
#-#####--##-###--#--
--#---#-###-###-##-#
------#-###--#-----#
--##-#-------#---#-#
####-#---##--#####-#
---#--########--##-#
------#--#--@#------
#-##--#------#--#---
#-#####--##$###-####
--#---##-##--##-##--
------#---##-#------
--##-##---#--#---#--
####--#-###-#.####-#
------#-#---#----#-#
--##--#-#-##--#--#-#
--#####-#--#-#--##-#
---------#-#-#------
--####---#---#--#---
Title: 3570
Author: EDPZnCl + LLM

@-#-----------------
--$-###############-
--##---##--#---#--#-
---#-------#------#-
----#-###--##-##--#-
##-##--##-###--#-##-
-------#-------#-#--
---##--#---##--#-#-#
###--######--###-#--
--#-------#-------#-
--#--###--#--##---#-
--##-##--###-#####.-
#-----#-------#-----
#-#---#--##---#--#--
#-#############--###
#-#-----#-----#-----
#-#-----#-----#--#--
#-##-##-##-##-####--
-----#-----#--------
-----#-----#---###--
Title: 3522
Author: WYXkk + LLM

在一段时间的努力后，其又优化出了一个更优秀的摆放方式，实现了 $3582$ 步的一个解。

---####--#---#####--
---------#----------
#-#####--##-######--
--#---#-###-##--##-#
------#-###--#------
--##-#-------#--#---
####-#---##--##-####
---#--#########-##--
------#--#---#------
#-##--#------#---#--
#-#####--##-######-#
#-#--###-##-#---##-#
#-#-------#-#-#-----
#-#--##---#-#---#---
#-##-######-###-####
#-##-#---##--##-##--
#-##-#-------#------
--##-##-###--#---#--
------#-$--#######-#
--#---#-@#---------.
Title: 3582
Author: LLM

	总步数	推动数	子结构数	圈长	总步/推动	总步/子结构	推动/子结构
SOTA	3582	112	28	124	31.982	127.929	4
1优化	3570	112	27	128	31.875	132.222	4.148
1	3566	110	27	128	32.418	132.074	4.074
2优化	3522	108	25	136	32.611	140.88	4.32
2	3516	106	25	136	33.170	140.64	4.24

可以看到 $3570$ 的解是在 $3566$ 的右下角修改了箱子终点的部分路径，增加了 $2$ 步箱子的推动，但并没有影响圈长。

$3582$ 的解重新构造了空间使用方式，多塞下了一个子结构；即使圈长变小一点，但以极其巧妙的方式增加了一个子结构，又带来了 $12$ 步的提升。

解中使用了如下的另一种子结构 Structure 2：

Structure 1
  ?????
  @   ?
##$## ?
#----??
#---#
#####

Structure 2
  ?????
  ?   ?
##@## ?
#-$--??
#-#-#
#---#
#####

其可以使用 $3\times 3$ 的空间（子结构 1 是 $2\times 3$）对本圈增加 $2$ 步的圈长。

因此，对 $n=20$ 有
$$M(20)\ge3582$$

其他大小

cjcjc 在知乎上的文章一个永远没有人能搞定的推箱子关卡提到了 $50\times50$ 尺寸且只有一个箱子的推箱子关卡最优答案的步数的极限问题，这里也摘录 Zou Yongzhong(20603) 的《一箭十万步》如下。注意这里的 $50\times50$ 有外层的墙，因此对应着本文中的 $M(48)$。

一箭十万步.png

##################################################
#---#@----#---##--#---##--#---##--#---##--#---#--#
#-#-#-----#-------#-------#-------#-------#------#
#-#--#-##-##-###--##-###--##-###--##-###--##-##--#
#--#-#$#------##-###--##-###--##-###--##-###--#-##
##-#---#---#--#-------#-------#-------#-------#-##
#--#########--#---##--#---##--#---##--#---##--#-##
#-#--#---#--######--######--######--######--###-##
#-#------#--##---#--##---#--##---#--##---#-------#
#-#--##-##-------#-------#-------#-------#--##---#
#--#-#--###-###-###-###-###-###-###-###-###-######
##-#-#-------#-------#-------#-------#--###-##---#
##-#-#--##---#--##---#--##---#--##---#-----------#
#--#-###--####--######--######--######--##########
#-#-------#---##--#---##--#---##--#---##--#---#--#
#-#---##--#-------#-------#-------#-------#------#
#--#####-###-###--##-###--##-###--##-###--##-##--#
##----##-###--##-###--##-###--##-###--##-###--#-##
#####-#-------#-------#-------#-------#-------#-##
##----#---##--#---##--#---##--#---##--#---##--#-##
#--#######--######--######--######--######--###-##
#-#--#---#--##---#--##---#--##---#--##---#-------#
#-#------#-------#-------#-------#-------#--##---#
#-#--##-###-###-###-###-###-###-###-###-###-######
#--#-#-------#-------#-------#-------#--###-##---#
##-#-#--##---#--##---#--##---#--##---#-----------#
##-#-#--######--######--######--######--##########
#--#-###--#---##--#---##--#---##--#---##--#---#--#
#-#-------#-------#-------#-------#-------#------#
#-#---##--##-###--##-###--##-###--##-###--##-##--#
#--#####-###-###-###--##-###--##-###--##-###--#-##
##----##-###--#-------#-------#-------#-------#-##
#####-#-------#---##--#---##--#---##--#---##--#-##
##----#---##--####--######--######--######--###-##
#--#######--##---#--##---#--##---#--##---#-------#
#-#--#---#-------#-------#-------#-------#--##---#
#-#------#--###-###-###-###-###-###-###-###-######
#-#--##-###-##-------#-------#-------#-------#---#
#--#-#-------#--##---#--##---#--##---#--##---#-#-#
##-#-#--##---#--######--######--######--#####--#-#
##-#-#--########--#---##--#---##--#---##--#---#--#
#--#-###--#---##--#-------#-------#-------#-###-##
#-#-------#-------##-###--##-###--##-###--#---#--#
#-#---##--##-###-###--##-###--##-###--##-####-##-#
#--#####-###--#-------#-------#-------#-------#--#
##-###--------#---##--#---##--#---##--#---###.#-##
#--###---###--############################---##--#
#-#---###---##---#---#---#---#---#---#---#-#---#-#
#---#-----#----#---#---#---#---#---#---#---###---#
##################################################
Title: 一箭十万-107593步
Author: Zou Yongzhong(20603)

	总步数	推动数	子结构数	圈长	总步/推动	总步/子结构	推动/子结构
一箭十万步	107593	590	152	704	182.361	707.849	3.881

从图片中可以观察到很明显的周期性：有 $1339$ 个可通行格，每个周期内部由 $13$ 行高、$7$ 列宽的重复单元拼成。笔者尝试删去重复的一两部分再进行数据统计，得到数据如下（此处尺寸包含边界墙）：

尺寸	可通行格 $F$	最短步数	$\text{步数}\div F^2$	$\text{面积}^2\div\text{步数}$
50×50	1339	107593	0.060010	58.09
50×43	1152	71032	0.053524	65.08
37×50	980	57650	0.060027	59.37
37×43	844	37909	0.053218	66.77
50×36	954	45659	0.050168	70.96
50×29	760	25908	0.044855	81.15

这个 $50\times 50$ 地图中平铺了最优子结构，因此删去重复的一些部分后，留下的地图仍然平铺着同样的最优子结构。

观察到 $\text{面积}^2\div\text{步数}$ （对正方形地图即 $n^4\div\text{步数}$）可以衡量关卡的紧凑优秀程度（越低越好），且对较大的 $n$ 来说近似于一个常数。后文将会继续分析这一点，给出完整的 $M(n)=\Theta(n^4)$ 的证明，并通过一些不同尺寸的地图进行数值分析，来猜测这一常数的大小范围。

有读者可能会问了，你这个变化也太大了吧，最小的 $58$，最大的都 $81$ 了，怎么会是常数呢？笔者找补一句：虽然整体不是最优，但子结构的核心没有变，因此这里数值分析的结论不会变。

再欣赏一个 $42\times42$（除去最外围的墙是 $40\times 40$）的解：

----------------------####---#####-####---
----#####--########---#--#---#---###--#---
----#---####--#---#####--#---#--------#---
#####---------#----------########-##--#---
#---#####-----##-######-##--#---#--#-####-
#---------#####--#---#------#------#-#--#-
##-######-##--#------#---#--##-##--#-#--#-
-#-#---#------#--##-######-###--####-#--#-
##-----#---#--####--#---#-------#--#-#-##-
#--##-######-##--#------#---##--#------#--
#--#--#---#------#--##-##########--##--#--
#--#------#---#--#####-##----#--##-##--##-
####--##-######-##--##-#-----#------#---#-
---#####-##--#---------#--####--#---#---#-
---#---#--#--#---##--#-##-#--##-#########-
---#------#--#########--#-#------#---#--#-
#####-##--#-------------#-#--#---#------#-
#---#--#####--####--#--##-##-######-##--#-
#------#--#####--##-####--##--#---#--#-##-
###-#--#----------#--#----#---#------#-#--
--#-####--###-##--####-##-#--###-##--#-#--
--#-#--##-###--#-##-####--##-###--####-#--
--#-#------#---#----#--#----------#--#-###
-##-#--#---#--##--####-##--#####--#------#
-#--##-######-##-##--#--####--#####--#---#
-#------#---#--#-#-------------#--##-#####
-#--#---#------#-#--#########--#------#---
-#########-##--#-##-#--##---#--#--#---#---
-#---#---#--####--#---------#--##-#####---
-#---#------#-----#-##--##-######-##--####
-##--##-##--#----##-#####--#---#------#--#
--#--##--##########-##--#------#---#--#--#
--#------#--##---#------#--##-######-##--#
-##-#-#--#-------#---#--####--#---#-----##
-#--#-####--###-######-##--#------#---#-#-
-#--#-#--##-##--#---#------#--##-######-##
-#--#-#------#------#---#--#####$.@------#
-####-#--#---#--##-######-##-----#####---#
---#--##-########----------#---------#####
---#--------#---#--#####---#--####---#----
---#--###---#---#--#---########--#####----
---####-#####---####----------------------
Title: Microban_IV 101
Author: David W. Skinner

	总步数	推动数	子结构数	圈长	总步/推动	总步/子结构	推动/子结构	$\text{面积}^2\div\text{步数}$
Microban_IV 101	25946	499	84	302	51.996	308.881	5.940	98.666

这个解因为美观性牺牲了一些优化，但可以供读者一品子结构的魅力。

较小地图的精确解

搜索枚举得表格如下。代码见附录。

$n$	$M(n)$	最优地图数	本质不同地图数	墙布局数	本质不同墙布局数	最优地图的 $F$
3	10	8	1	4	1	8
4	25	16	2	16	2	13, 14
5	41	768	96	524	66	16, 17, 18, 19, 20
6	78	8	1	8	1	28

$n=3$，$M(3)=10$，此时只有 $1$ 种本质不同的地图，$F=8$：

1
2
3

#--
@$-
.--

$n=4$，$M(4)=25$，有 $2$ 种本质不同的地图，分别为 $F=13$ 与 $F=14$：

##-@
-$--
-#--
.---
Title: F=13

-#-@
-$--
-#--
.---
Title: F=14

$n=5$，$M(5)=41$，有 $96$ 种本质不同的地图，其中 $F$ 可以为 $16,17,18,19,20$，详细统计如下：

$F$	最优地图数	本质不同地图数	墙布局数	本质不同墙布局数
16	16	2	16	2
17	120	15	96	12
18	280	35	200	25
19	264	33	168	21
20	88	11	44	6

为每种 $F$ 取一个地图展示：

####.
-----
-#-#-
-#-$-
@--##
Title: F=16

####.
-----
-#-#-
-#-$-
@--#-
Title: F=17

###-.
-----
-#-#-
-#-$-
@--#-
Title: F=18

##--.
-----
-#-#-
-#-$-
@--#-
Title: F=19

-#--.
-----
-#-#-
-#-$-
@--#-
Title: F=20

$n=6$，$M(6)=78$，只有 $1$ 种本质不同的地图，其 $F=28$，解为 dllllddddrrrruullUdrrddllluluuurRurrdLLLrddrrddllluluuluurDDDuurrddrrddllllluR：

--#--@
------
--#$##
#-#---
--.##-
------

该关卡有 $24$ 条长度为 $78$ 的最短操作序列。

但地图的唯一性并不意味着走法唯一，对其中一条最短解，箱子推动方向为 URLLLDDDR，只推动 9 次，其余 69 步全部用于行走。

下一组推动	推动之前的行走步数	推动次数
U	17	1
R	14	1
LLL	4	3
DDD	18	3
R	16	1

总计 $(17+14+4+18+16)+9=78$，让人访问了全部 $28$ 个空地。

对唯一性的猜测，可能原因是 $6\times 6$ 的空间刚好容纳了一套很紧的换边与绕行结构，墙、回路、临时停车位和目标位置之间几乎没有调整余地。

由于 $n>6$ 时搜索空间很大，精确搜索不完，所以采用启发式搜索，只能给出可以构造的下界。同时地图种类有很多，笔者仅挑选几个（不一定）有代表性的地图。搜索代码见附录。

$n=7$，$M(7)\ge 119$，启发式搜索出 $F=36$ 与 $F=37$ 两类：

--##---
-------
--###-#
#-#-$--
----#--
-##-#--
----.#@
Title: F=36

--#----
-------
--###-#
#-#-$--
----#--
-##-#--
----.#@
Title: F=37

$n=8$，$M(8)\ge 159$，其中 $F$ 最小为 $44$，最大为 $48$：

##---#-@
---#-$--
-##.##--
-----#-#
#-#-----
--##-##-
------#-
--###---
Title: F=44

--#-----
------#-
--##-#--
#--#----
.-#--#-#
----##--
-###-$--
-----#-@
Title: F=48

$n=9$，$M(9)\ge 231$：

--#---#@-
------##-
--##-#---
--#------
--#--#$##
--#--#---
#-###.#--
-------#-
----#----

$n=10$，$M(10)\ge 311$：

--#---#---
--#-#-----
-------#-#
#-#-###---
--.##-@#-#
-##-$--#-#
-##-#--#--
-#--#-##--
-#-#------
---#---#--

$M(n)$ 的渐进界

对于有解地图 $B$，定义
$$\operatorname{OPT}(B)=\min{\text{解答的总移动步数}}$$
即 $\operatorname{OPT}(B)$ 为地图 $B$ 的最短解步数。

定义
$$M(n)=\max{\operatorname{OPT}(B):B\text{ 是合法且有解的 }n\times n\text{ 单箱地图}}$$
即 $M(n)$ 为所有大小为 $n\times n$、恰有一个箱子和一个目标点的关卡中，最短解步数的最大值。

先给出定理：

存在 $c,C>0$ 和 $n_0$，使得对所有 $n\ge n_0$，
$$cn^4\le M(n)\le Cn^4$$
即最短解步数的最大值随地图的边长而四次方增长
$$M(n)=\Theta(n^4)$$

常数 $c,C>0$ 可以取为
$$\frac{(n-23)^2(n-14)^2}{56}\le M(n)\le(n-2)(n-1)(n^2-1)<n^4\qquad(n\ge32)$$

且下界满足
$$M(n)\ge\frac{n^4}{56}-O(n^3)$$
特别地，$M(n)\ge n^4/896$ 对所有 $n\ge46$ 成立。

上界

设一张地图有 $F$ 个可通行格，包括人、箱子和目标所在格，则 $F\le n^2$。

墙的位置固定以后，后续合法操作只取决于人的位置 $p$ 和箱子的位置 $b$，因此完整状态可以写为 $s=(p,b)$，$p\ne b$。

设一条最短解依次经过 $s_0,s_1,\ldots,s_T$，其中 $T=\operatorname{OPT}(B)$，且第一次把箱子送到目标发生在 $s_T$。如果存在 $0\le i<j<T$，使得 $s_i=s_j$，那么可以删除从 $s_i$ 到 $s_j$ 的整段操作。由于两个状态中的人和箱子位置完全相同，原来从 $s_j$ 开始的操作在 $s_i$ 也合法。这样得到一个更短的解，与最短性矛盾。因此 $s_0,s_1,\ldots,s_{T-1}$ 是 $T$ 个互不相同的非终止状态。

尝试对非终止状态计数。设目标格为 $g$。通关之前，箱子不能位于 $g$，所以 $b$ 至多有 $F-1$ 种选择。给定 $b$ 后，人不能与箱子重叠，所以 $p$ 至多有 $F-1$ 种选择。故非终止状态数至多为 $(F-1)^2$ 个，则
$$\operatorname{OPT}(B)\le(F-1)^2\le(n^2-1)^2$$

对所有合法有解地图取最大值得到
$$M(n)\le(n^2-1)^2=O(n^4)$$

更紧的上界

尝试利用地图“边界”得到更紧的上界。以下设 $n\ge3$，把最外侧的行和列称为边界，剩下的 $(n-2)^2$ 个位置称为内部。

注意到，箱子一旦到达最上面一行，就不能再向下推回内部，因为这要求人站到地图外。其他三条边同理。因此，箱子到达一条边后，只能沿这条边移动。同时，箱子也不能通过角点转到另一条边，更进一步的，箱子到达角点后就完全不能移动。

由此得到两个限制：

若目标在内部，成功解中的箱子始终不能到达边界。
若目标在边界，成功解中的箱子首次到达边界后，只能沿同一条边活动，直到到达目标。若目标在角点，一条具体的成功路径也只能使用与目标相邻的两条边之一。

进行分类：

目标在内部：箱子只能出现在内部，并且通关前不能占据目标格。因此非终止箱子位置至多有 $(n-2)^2-1$ 个，得到 $\operatorname{OPT}(B)\le\left((n-2)^2-1\right)(n^2-1)$；
目标在边界非角点：子可以先在内部活动，随后只能沿目标所在的那条边移动。这条边有 $n-2$ 个非角点位置，排除目标后剩下 $n-3$ 个，得到 $\operatorname{OPT}(B)\le\left((n-2)^2+n-3\right)(n^2-1)$；
目标在角点：一条具体的成功路径可以先经过内部，再沿与目标相邻的某一条边到达目标。该边有 $n-2$ 个非角点位置，得到 $\operatorname{OPT}(B)\le\left((n-2)^2+n-2\right)(n^2-1)$。

第三种情况的上界最大，因此对 $n\ge 3$ 有
$$M(n)\le\left((n-2)^2+n-2\right)(n^2-1)=(n-2)(n-1)(n^2-1)=n^4-3n^3+n^2+3n-2$$

对于一张已知有 $F$ 个可通行格的地图，可以同时保留两种计数，容易得到
$$\operatorname{OPT}(B)\le\min{(F-1)^2,(n-2)(n-1)(F-1)}=O(n^4)$$

下界

省流

对于前文提到的子结构，可以按二维周期铺放，从而形成一个环形构造：

在 $n×n$ 中放入 $\Theta(n^2)$ 个固定大小的箱路转向结构，同时保留一条长度为 $\Theta(n^2)$ 的只能由人走的环形回路。箱子每通过一个结构，下一次推动前玩家必须换边，而唯一换边路线是走完该大回路，因而任何解至少进行 $\Theta(n^2)$ 次、每次 $\Theta(n^2)$ 步的绕行。

于是存在常数 $c>0$ 和无限多个 $n$，使 $M(n)\ge cn^4$。

证明与构造

为了证明 $M(n)=\Omega(n^4)$，必须构造一个地图族，并证明这个族中任何解都需要至少常数倍的 $n^4$ 步。下面给出构造满足

有 $\Theta(n^2)$ 个箱子必须经过的转弯；
每个转弯都强制人行走 $\Theta(n^2)$ 步；
箱子不能通过离开箱道来绕过这些转弯；
不同转弯强制产生的行走发生在互不重叠的时间段。

先构造一条由相邻空地组成的简单环 $\mathcal C$，满足除了环上相邻的格子，其他环上格子不在地图中直接相邻。只考虑这些环上格子的相邻关系时，得到的恰好是一个环图。

设环长为 $L$，即环图有 $L$ 个顶点和 $L$ 条边。取环上的一个直角转弯 $c$。箱子的指定前进方向在转弯前是单位向量 $a$，转弯后是垂直的单位向量 $b$，即 $a,b\in{(1,0),(-1,0),(0,1),(0,-1)}$ 且 $a\perp b$。箱子道路上的三个连续格子为 $c-a,c,c+b$。在环外增加下面四个空地格：$Q_c={c-b,\ c+a-b,\ c+a,\ c+a+b}$，附近其余格子保持为墙，并让不同转弯结构之间留出足够距离。

例如，取 $a=(1,0)$、$b=(0,1)$，以向右为横坐标正方向、向下为纵坐标正方向，子结构的局部图如下：

##sq#
--Cr#
##dt#
##-##

其中 C 表示转弯格 $c$，d 表示 $c+b$，s 表示下一次推动需要的站位 $c-b$；q,r,t 和 s 是新增的四个支撑格。

此结构满足下面的性质：

子结构不会把回路变短。 四个新增格组成一条路径：$c-b\longleftrightarrow c+a-b\longleftrightarrow c+a\longleftrightarrow c+a+b\longleftrightarrow c+b$。它与原环接触的顶点恰好是 $c$ 和 $c+b$，而这两个顶点本来就由环上的一条边连接。因此，任何从原环进入该结构、再回到原环的行走，都可以用原环上的零条或一条边替代，并且不会增加长度。换言之，这种局部结构不能缩短环上两个顶点之间的距离。

箱子进入支撑格以后不能回到原环。 箱子从 $Q_c$ 回到原环，只可能经过以下三条边：$c-b\to c,c+a\to c,c+a+b\to c+b$。但是，完成这三次推动所需的人的站位分别为 $c-2b,c+2a,c+2a+b$，这三个位置都是墙。所以，箱子一旦进入任何支撑格，就不可能再被推回原环。若目标设在原环上，这样的操作必然导致失败。即使箱子先在几个支撑格之间移动，最后要回到原环时也仍然必须经过上述三条边之一，因此结论不变。

箱子转弯时，人必须绕几乎一整圈。 假设箱子刚从 $c-a$ 被推到 $c$。这时人位于 $c-a$。要把箱子从 $c$ 沿 $b$ 方向推出去，人必须站到 $c-b$。箱子占据 $c$ 时，原环相当于删去了顶点 $c$。从 $c-a$ 到 $c+b$ 的另一侧环路长为 $L-2$。前面已经证明，其他转弯的子结构不能缩短这条路。当前转弯的子结构在 $c$ 被箱子占据后，只能从 $c+b$ 一侧进入。因此，人必须先沿另一侧原环走 $L-2$ 步，再沿当前支撑路径走 $4$ 步，所以最短换边距离恰好是 $L+2$。

具体构造：取整数 $m\ge2$ 和偶整数 $r\ge 2$，设置 $r$ 条横带，每条横带有 $m$ 个锯齿。令 $W=8m$，$y_j=8j$，$0\le j<r$。先设计一条从 $S=(0,0)$ 出发的简单箱道 $P$。所有坐标之间的连接都是水平或竖直线段，并把线段经过的全部整数格设为空地。

每一条横带中的锯齿。 在第 $j$ 条横带中，放置 $m$ 个锯齿。先看从左向右的版本。第 $i$ 个锯齿依次经过 $(8i,y_j),(8i+4,y_j),(8i+4,y_j+3),(8i+8,y_j+3),(8i+8,y_j)$，满足 $0\le i<m$。每个锯齿由两条长度为 $4$ 的横向线段和两条长度为 $3$ 的竖向线段组成，长度总共为 $14$，所以一条横带的箱道长度为 $14m$。

当 $j$ 为偶数时，直接采用上面的坐标，方向从左向右；当 $j$ 为奇数时，对全部横坐标作镜像 $x \mapsto W-x$ 使方向变为从右向左。每个锯齿的第二、第三、第四个列出的位置都是转弯，相邻锯齿的接点另有一个转弯。因此一条横带内部恰有 $3m+(m-1)=4m-1$ 个转弯；全部横带内部共 $r(4m-1)$ 个转弯。

横带之间的连接。 对于偶数 $j<r-1$，用下面的折线连接到下一条横带：$(W,y_j)\to(W+4,y_j)\to(W+4,y_{j+1})\to(W,y_{j+1})$；对于奇数 $j<r-1$，采用左侧连接：$(0,y_j)\to(-4,y_j)\to(-4,y_{j+1})\to(0,y_{j+1})$。每段连接的长度都是 $4+7+4=15$。

因为 $r$ 为偶数，所以最后一条横带在左端结束。把箱道继续向上延伸 $3$ 格，以
$G=(0,7(r-1)-3)=(0,7r-10)$ 作为目标，箱道 $P$ 到此结束。箱道总长度为
$$|P|=14mr+15(r-1)+3=14mr+15r-12$$

每个带间连接另有三个转弯：前一横带的末端、外侧竖段的上端和下端。下一横带的起始横段与连接共线，最后的向上延伸也与前一竖段共线。因此整个箱道的转弯数为
$$K=r(4m-1)+3(r-1)=4mr+2r-3$$

用不能运送箱子通过的折线闭合回路。 再加入一条从 $S$ 到 $G$ 的玩家道路 $R$：$S=(0,0)\to(-8,0)\to(-8,7r-10)\to G$，长度是
$$|R|=8+(7r-10)+8=7r+6$$

$P$ 和 $R$ 只在两个端点相交，它们的并集形成环 $\mathcal C$，环长为
$$L=|P|+|R|=14mr+22r-6$$

只在箱道 $P$ 的转弯处增加上文提到的子结构，在连接道 $R$ 的两个拐角处不增加支撑格。

初始时箱子位于 $S$，人位于 $(-1,0)$，目标位于 $G$，横向间距为 $4$，相邻横带基准行相隔 $7$，锯齿高度为 $3$，验证可知以上这些结构不会互相碰到；将未使用的格子全部填满墙即可。

空地的坐标范围为 $-8\le x\le8m+5$，$-1\le y\le7r-3$，因此空地外接矩形的宽、高分别为 $8m+14$ 和 $7r-1$，可装入边长 $N=\max{8m+14,\ 7r-1}=\Theta(m)$ 的正方形。选择 $r=\frac87m+O(1)$ 即可使长宽相等。

地图生成器见附录。使用生成器对一些 $m$ 生成地图，结果见表：

$m$	$r$	边长	环长 $L$	转弯数 $K$	最优步数
2	4	30	194	37	7412
4	6	46	462	105	49134
6	8	62	842	205	173800
7	10	70	1194	297	356330
14	18	126	3918	1041	4084506

取 $m=2$ 生成地图，得到 $30\times 30$ 的地图：

############--#---##--#---##--
-------@$-----#-------#-------
-###########--##-###--##-###--
-###########-###--##-###--##-#
-##########-------#-------##-#
-##########---##--#---##--##-#
-###########################-#
-##--##---#--##---#--#######-#
-##-------#-------#-----------
-##--###-##--###-##--######---
-###-##--###-##--###-#########
-###-##-------#-------########
-###-##--##---#--##---########
-###-#########################
-###-#######--#---##--#---##--
-##-----------#-------#-------
-##---######--##-###--##-###--
-###########-###--##-###--##-#
-##########-------#-------##-#
--------.##---##--#---##--##-#
########-###################-#
########-##--##---#--#######-#
########-##-------#-----------
########-##--###-##--######---
#######--###-##--###-#########
#######-------#-------########
#######--##---#--##---########
##############################
##############################
##############################

下面验证所有解都必须经过这些转弯。（直观上可以从上图中很方便的看出）

箱子不能通过步行连接道抄近路。 如果箱子从 $S$ 向左进入 $R$，它首先遇到的拐角是 $(-8,0)$。箱子到达该角后，要改为向下推动，人需要站在 $(-8,-1)$，但该格是墙。拐角左边也没有空地，箱子不能继续向左。由于这个拐角没有子结构，箱子不能通过它。在到达拐角之前，箱子可以折返，但这种折返只能把它送回 $S$，不能使它沿 $R$ 到达目标。同时箱子也不能通过进入某个子结构，再从其他地方返回原环。故任何成功解在到达 $G$ 前，都必须沿 $P$ 前进，允许中途后退，但不能绕过 $P$ 上的某个转弯。

后退不能消除换边的代价。 考虑 $P$ 上任意一个转弯 $c$，其前后格分别为 $c-a$ 和 $c+b$。在任意成功解中，选取箱子第一次从 $c$ 被推到 $c+b$ 的时刻，再向前回溯到此前最后一次箱子从 $c-a$ 被推到 $c$ 的时刻。在这两个时刻之间，箱子一直停在 $c$。否则，它要么进入支撑格并导致失败，要么退回前面的箱道，随后还必须重新从 $c-a$ 进入 $c$，与最后一次矛盾。

刚进入 $c$ 时，人位于 $c-a$；下一次向 $c+b$ 推动前，人必须到达 $c-b$，这段时间内至少发生 $L+2$ 步行走。沿 $P$ 的各个转弯第一次被成功通过的顺序，与它们在 $P$ 上的顺序相同。为不同转弯选出的上述行走时间段互不重叠，所以可以相加。

此外，箱子必须沿简单箱道从 $S$ 到 $G$，所以任何成功解至少有 $|P|$ 次推动。这些推动和上述行走不重叠。因此
$$\operatorname{OPT}(B)\ge |P|+K(L+2)$$

显然本构造有解：人从初始站位可以把箱子沿 $P$ 推到第一个转弯。每当箱子停在一个转弯 $c$，人沿原环的另一侧走到 $c+b$，再通过子结构到达 $c-b$，就能完成转向。直线部分继续推动即可。重复这一操作，最终可以把箱子送到目标点。初始站位已经在第一次推动所需的位置；整个解恰有 $|P|$ 次推动，且只在 $K$ 个转弯处各行走 $L+2$ 步。因此最优解恰好是
$$\operatorname{OPT}(B)=|P|+K(L+2)$$

先给出一个便于写出精确式子的地图边长系列，取整数 $t\ge 1$，令 $m=7t$，$r=8t+2$，此时地图的宽为 $8m+14=56t+14$，高为 $7r-1=56t+13$，只差 $1$ 格。有
$$N=56t+14$$
$$K=4 m r + 2 r - 3=224t^2+72t+1$$
$$L=14mr+22r-6=784t^2+372t+38$$
$$|P|=14mr+15r-12=784t^2+316t+18$$

因此该地图的最优步数为
$$\operatorname{OPT}(B)=|P|+K(L+2)=56^3 t^4+139776 t^3+37312 t^2+3568 t+58$$
有
$$\lim_{t\to\infty}\frac{\operatorname{OPT}(B)}{N^4}=\frac1{56}$$
分别对 $m,r$ 向下取整即可将构造推广到所有足够大的边长。

下面证明 $\Omega(n^4)$ 对所有足够大的 $n$ 成立。

若一个地图装得进 $n\times n$，则可以在外围填墙，把它嵌入更大的正方形。人的移动和箱子的推动关系完全不变，因此最优解长度也不变，$M(n)$ 单调不减。

对于任意 $n\ge30$，选择
$$m=\left\lfloor\frac{n-14}{8}\right\rfloor$$
$$r=2\left\lfloor\frac{n+1}{14}\right\rfloor$$
这时 $m\ge2$，$r\ge4$ 为偶数，$8m+14\le n$，$7r-1\le n$。

为标记方便，令构造的精确最优步数为
$$F(m,r):=\operatorname{OPT}(B_{m,r})=|P|+K(L+2)=56m^2r^2+116mr^2+44r^2-44mr-59r$$
保留取整参数可以直接得到精确下界
$$M(n)\ge F\left(\left\lfloor\frac{n-14}{8}\right\rfloor,2\left\lfloor\frac{n+1}{14}\right\rfloor\right)\qquad(n\ge30)$$

为了得到不含取整符号的多项式界，因为 $n$ 是整数，由 $\lfloor x\rfloor\ge x-1$ 得
$$m\ge m_0=\frac{n-21}{8}$$
$$r\ge r_0=\frac{n-12}{7}$$
当 $n\ge30$ 时，有 $m_0\ge9/8>1$、$r_0\ge18/7>2$。把 $F$ 看作实变量多项式，在 $m\ge1,r\ge2$ 上，$\frac{\partial F}{\partial m}=4r(28mr+29r-11)>0$，$\frac{\partial F}{\partial r}=(112m^2+232m+88)r-44m-59\ge224m^2+420m+117>0$，$F$ 对两个参数分别单调递增。

因此，将 $B$ 放入 $n\times n$ 后有
$$M(n)\ge\operatorname{OPT}(B)=F(m,r)\ge F(m_0,r_0)=\frac{7n^4-346n^3+5975n^2-42844n+106464}{392}$$

对 $n\ge30$ 有下界（$M(n)$ 为整数，右式可取整）
$$M(n)\ge\left\lceil\frac{n^4}{56}-\frac{173n^3}{196}+\frac{5975n^2}{392}-\frac{10711n}{98}+\frac{13308}{49}\right\rceil=\frac{n^4}{56}-O(n^3)$$

若看 $O(n^3)$ 项不美观，也可以给出一个不含 $O(n^3)$ 项的下界。有 $K\ge4mr$，$L+2=14mr+22r-8\ge 14mr$，因此
$$M(n)\ge\operatorname{OPT}(B)=|P|+K(L+2)\ge K(L+2)\ge56m^2r^2\ge\frac{(n-21)^2(n-12)^2}{56}$$

当 $n\ge42$ 时，$n-21\ge n/2$、$n-12\ge n/2$，所以
$$M(n)\ge\frac{n^4}{896}\qquad(n\ge42)$$
$$M(n)=\Omega(n^4)$$

结合上界，得
$$M(n)=\Theta(n^4)$$
$$\liminf_{n\to\infty}\frac{M(n)}{n^4}\ge\frac1{56}$$
$$\limsup_{n\to\infty}\frac{n^4}{M(n)}\le56$$

绘图

记
$$F(n):=F\left(\left\lfloor\frac{n-14}{8}\right\rfloor,2\left\lfloor\frac{n+1}{14}\right\rfloor\right)$$
为可构造的精确值，记
$$G(n):=\frac{7n^4-346n^3+5975n^2-42844n+106464}{392}$$
为放缩后的对所有 $n$ 均成立的下界，$G(n)$ 是 $F(n)$ 的一个下包络。

对满足 $n=56t+14$ 且 $t$ 为整数下的 $n$，记 $h(n):=56^3 t^4+139776 t^3+37312 t^2+3568 t+58$，代入得
$$h(n):=\frac{n^4}{56}-\frac{10 n^3}{49}-\frac{26 n^2}{49}+\frac{18 n}{7}\quad(n\equiv 14\pmod{56})$$
对 $h(n)$ 无条件化得到 $H(n)$：
$$H(n):=\frac{n^4}{56}-\frac{10 n^3}{49}-\frac{26 n^2}{49}+\frac{18 n}{7}$$
其满足 $H(n)$ 是 $F(n)$ 的一个上包络。

对 $n\ge 30$ 有 $G(n)\le F(n)\le H(n)$，且 $M(n)$ 一定满足 $M(n)\ge F(n)$，但不一定满足 $M(n)\ge H(n)$。

画出离散的 $F(n)$ 与连续的 $G(n),H(n)$：

F[m_, r_] := 56 m^2 r^2 + 116 m r^2 + 44 r^2 - 44 m r - 59 r;
F[n_] := F[Floor[(n - 14)/8], 2 Floor[(n + 1)/14]];
G[n_] := (7 n^4 - 346 n^3 + 5975 n^2 - 42844 n + 106464)/392;
H[n_] := (18 n)/7 - (26 n^2)/49 - (10 n^3)/49 + n^4/56;
Show[DiscretePlot[F[n], {n, 30, 60}, Filling -> None], 
 Plot[{Null, G[n], H[n]}, {n, 30, 60}, 
  PlotLegends -> {"F(n)", "G(n)", "H(n)"}]]

有
$$\lim_{n\to\infty}\frac{n^4}{F(n)}=\frac{n^4}{G(n)}=\frac{n^4}{H(n)}=56$$
画出 $\frac{n^4}{F(n)}$，$\frac{n^4}{G(n)}$，$\frac{n^4}{G(n)}$ 与本构造的极限 $56$：

Show[DiscretePlot[n^4/F[n], {n, 30, 100}, Filling -> None], 
 Plot[{Null, n^4/G[n], n^4/H[n], 56}, {n, 30, 100}, 
  PlotLegends -> {"\!\(\*FractionBox[SuperscriptBox[\(n\), \(4\)], \
\(F \((n)\)\)]\)", 
    "\!\(\*FractionBox[SuperscriptBox[\(n\), \(4\)], \(G \((n)\)\)]\)",
     "\!\(\*FractionBox[SuperscriptBox[\(n\), \(4\)], \(H \
\((n)\)\)]\)", "Construction bound limit 56"}], PlotRange -> All]

直观一些？

给出一个直观理解来说明为什么 $M(n)=\Theta(n^4)$：每个子结构的面积是固定的，因此直观上 $\text{子结构数}\sim\text{面积}\sim{n^2}$。

每个子结构的面积是固定的，因此最优解的间隙大小也是基本固定的。对于足够大的 $n$，圈长约等于总步数与子结构数的比值，玩家走圈的圈长为 $\sim n^2$。

总步数与子结构数的比值近似于圈长，因此 $\text{总步数}\sim\text{子结构数}\times\text{圈长}\sim n^4$。

回归分析

已经知道 $M(n)=\Theta(n^4)$，那么这个比例常数是多少呢？精确计算很难，可以直接对已知的几个解进行数值分析。

对已知的所有项进行四次拟合，绘制对数图：

1
2
3

data = {{3, 10}, {4, 25}, {5, 41}, {6, 78}, {7, 119}, {8, 159}, {9, 231}, {10, 311}, {20, 3582}, {48, 107593}};
line = Fit[data, {1, x, x^2, x^3, x^4}, x]
Show[ListLogPlot[data, PlotStyle -> Red], LogPlot[line, {x, 0, 50}]]

得到四次项系数为 $0.019$。可以看出对较大的 $n$ 有
$$M(x)\approx 0.02n^4$$
即
$$50M(x)\approx n^4$$

因此，称一个单箱推箱子地图 $B$ 的密度值 $\alpha$ 为
$$\alpha=\frac{\operatorname{OPT}(B)}{n^4}$$
密度倒数 $\beta=\frac{1}{\alpha}$ 为
$$\beta=\frac{n^4}{\operatorname{OPT}(B)}$$

对特定地图大小 $n$ 中所有合法的 $n\times n$ 单箱推箱子地图中最优解步数的最大值 $M(n)$ 定义关于 $n$ 的密度函数
$$\alpha(n)=\frac{M(n)}{n^4}$$
和密度倒数函数
$$\beta(n)=\frac{n^4}{M(n)}$$

设 $D(n)$ 是目前已知的地图的最优步数，则 $D(n)\le M(n)$，$\frac{D(n)}{n^4}\le\alpha(n)$，$\beta(n)\le\frac{n^4}{D(n)}$。

一个地图的密度 $\alpha$ 越大，密度倒数 $\beta$ 越小，代表了其空间利用效率越高。同时注意到 $M(n)=\Theta(n^4)$，因此如此定义的密度可以跨不同的地图大小进行地图效率的比较。笔者定义 $\beta$ 与 $\beta(n)$ 则是因为 $\alpha$ 通常小于 $1$，取倒数可以更明显。

对所有 $n$ 已知的最大 $\operatorname{OPT}(B)$ 进行统计，得到密度倒数函数 $\beta(n)$ 的上界（对 $n=3\sim 6$ 为精确值）：

1 2	Table[N[data[[i]][[1]]^4/data[[i]][[2]]], {i, Length[data]}] ListLinePlot[Table[{data[[i]][[1]], N[data[[i]][[1]]^4/data[[i]][[2]]]}, {i, Length[data]}]]

还记得可构造的精确值
$$F(n):=F\left(\left\lfloor\frac{n-14}{8}\right\rfloor,2\left\lfloor\frac{n+1}{14}\right\rfloor\right)$$

绘图

已经证明
$$\liminf_{n\to\infty}\frac{M(n)}{n^4}=\liminf_{n\to\infty}\alpha(n)\ge\frac1{56}$$
$$\limsup_{n\to\infty}\frac{n^4}{M(n)}=\limsup_{n\to\infty}\beta(n)\le56$$

根据目前观察到的结论，在 $n=3\sim 48$ 的已知最优解密度倒数在已知的数据上单调递增，笔者提出猜想：$\beta(n)$ 在足够大的 $n$ 上单调递增。

若该猜想成立，则根据单调有界定理，$\beta(n)$ 将会收敛到一个特定的值，该值的范围是
$$49.3379<\lim_{n\to\infty}\beta(n)\le56$$

结语

本文从单箱推箱子的问题出发，聚焦于单箱推箱子地图的最大最短步数问题，使用计算机搜索了较小地图的精确解与启发式下界，对中等规模的地图进行了构造尝试，对足够大的地图进行了渐进分析；证明了最大最短步数与地图的边长呈四次方量级增长；定义了地图的密度与密度倒数，猜测当地图足够大时，最优密度与密度倒数会收敛到一个特定的值。

附录

GPT 6 Astra 的局部优化尝试过程

先以资料中的 3566 图为起点做了以下精确或随机邻域检查：

固定墙图，穷举目标位置：原目标已最优；
固定墙图，反向 BFS 穷举所有人/箱/目标初始位置组合：原三者组合已全局最优；
穷举所有单格增删墙：无提升；
穷举所有两格同时翻转：无提升；
穷举墙图的 400 种环形平移/重新切边，并为每张图重新优化三枚标记：无提升；
随机采样 200 万张与冠军相差 3、4、5 或 6 个格子的墙图：无提升；
退火搜索 100 万次单格变异：无提升。

第二轮又完成了以下结构化搜索：

冠军图所有 3×3 窗口的全部 512 种重写，共 165888 个候选（包含人、箱、目标周围窗口）：无提升；
冠军图所有 4×4 窗口、与原窗口相差至多四格的 621699 个候选：无提升；
2×2 至 5×5 两个远距离区块互换，共 136859 个候选：无提升；
从其余九张榜单图移植 2×2 至 8×8 模块，共 103104 个候选：无提升；
随机移植 300000 个 4×4 至 10×10 模块：无提升；
保持墙数量不变的一开一关退火：冠军和改进后的第二名分支各 500000 次，无提升；
由榜单十种拓扑组成种群，运行 30 代、每代 1000 个后代，并对每代入围墙图重新全局优化标记：无提升。
两轮扩展多目标遗传搜索，各 50 代、每代 4500 个后代；同时保留总步数、长绕行次数、最大绕行长度、推动转向数等多个精英族：总步数无提升，但得到最大单段 153 步及多个新的可爬升骨架；
从 50×50 参考图裁取全部 961 个 20×20 连续窗口，并对每个墙图全局优化人、箱、目标位置：最高仅 176；
以 13 行、7 列周期为依据，随机压缩 50×50 模板 20000 次并全局优化三枚标记：最高 1062，说明简单抽样压缩不足以保留完整强制结构；
从 3394 新骨架出发，穷举远端目标和全部 3×3 改写，得到另一张 3522 图；再穷举其全部 4×4、汉明半径不超过 4 的 727413 张图：无提升；
从遗传搜索产生的 2938 骨架连续做 3×3 精确爬升，得到 2938 → 3224 → 3404，第三轮无提升。

搜索在原第二名拓扑上找到了一项可复现改进 3516 → 3522，其最短解包含 108 次推动和 25 次长绕行；大绕行平均约 136.5 步。它仍低于冠军，但证明搜索器确实能在已有比赛提交上找到严格增益，而不是只能复现输入。

随后，对每张变异墙图重新全局优化人、箱、目标三者的位置，并只接受不降分的单格变异；沿等分平台移动后找到 3566 → 3570。再逐格删除不影响分数的冗余地面，最终图只有 237 个可通行格，比原图多 2 个；关键长绕行仍为 27 次，主要增益来自箱路多出两次推动及相应短走路。随附 checker 与独立 BFS 均确认 3570。

围绕精简后的 3570 图又检查了：全部单格变异且每张图重新全局优化三枚标记（50 张等分邻居、无提升）；全部固定标记双格变异（868 张等分邻居、无提升）；两轮受空地数约束的等分平台漫步，合计检查 20000 个一步或两步变异；目标结构 3×7 窗口汉明半径 7 的 198440 个候选；起点与目标附近三个 5×5 窗口汉明半径 5、各 68406 个候选；全部 4×4 窗口汉明半径不超过 4 的 727413 个候选；均无提升。

又对前十名进行了批量优化，先导出前十地图的最优路线，分离箱道、拐角支撑格和步行连接道，再尝试以下结构变化：

整个矩形区域的平移、循环移位、镜像与旋转，配合起点和终点重新选择。
把箱道表示为正交折线，移动整段或成组的顶点，插入、删除折返段，并重新生成拐角的支撑空间。
用 Z3 同时安排拐角位置和步行连接道，尝试把一个拐角拆成三个阶梯拐角，以及以短换边结构的空间换取长绕行结构。
从结构变换产生的新分支继续进行完整 3×3 窗口重写，第三名、第八名各检查两轮，第十名检查三轮，共 1161216 个窗口候选。

第十名分支的主要路径是 3161 → 3293 → 3296 → 3341。其最优解中的长行走段由 25 段增至 26 段，同时改变了回路的长度与末端结构，因此这一分支的提升不是只在起点附近增加几步。

优化结果如下：

第三名：3368 → 3380，增加 12 步。
第十名：3161 → 3341，增加 180 步。
第八名：3255 → 3304，增加 49 步。

#------##---#------.
#$####--#-#-#-#-###-
#-##--#---#-#-#-----
------#####---#--#-#
@--#--#---########--
####-##-------------
--##-###-####-####--
------##-#--##---###
--#---##-#-------###
#-######-#--###-#---
#-##--#--##-##--#-#-
------#------#------
---#--#--#---#--##-#
####-#############--
--##-##---##--#-----
------#-------#--#--
--#---##-###--##-###
#-######--##-###----
----------#------##-
---#####--#---##----
Title: 3380
Author: GoldenFishX + LLM

@-#----#---#---#.---
--$-##---#---#-#-##-
--##--####-###-#----
---#--#---#--#---#-#
------#------#####--
####-###-##---------
--##-#----###-####--
------#--#---#----##
--#---##-#-------##-
#-####---#-####-#---
#-##--#------#--#-#-
------#--#---#------
---#--###--###--##-#
####-#---##--#####--
--##-#-------#---#--
------#-###--#------
--#---#-##---##-##-#
#-#####--##-###--#--
---------#-------#--
----#-#--#---##--#--
Title: 3341
Author: Ew_Cors + LLM

.#---#--##---#--#---
-----#-------#------
-##-##--###-##--##-#
-#--###-##--###-##-#
-#-------#-------#-#
-#--##---#--##---#-#
--################-#
-----#---##--#---#--
#----#-------#------
--#####-###--##-##--
-#---##--##-###--###
-#-------#-------###
-##-###--#---##--###
-#--#############---
-#------------------
-#--##############-#
-###---#---#-----#-#
-###-#-#-#-#-###$#--
-###-#-#-#-#-#------
-----#---#---#@--#--
Title: 3304
Author: orz_z + LLM

代码

由 WYXkk 为 Sokoban Golf 比赛编写的 checker.cpp（依赖 testlib.h），采用 BFS 搜索算法：

#include "testlib.h"  
#include<queue>  
  
constexpr int W=22;  
char s[W][W];  
int dis[W][W][W][W];  
constexpr int infi=1e8;  
  
#define F(i,a,b) for(int i=(a);i<=(b);i++)  
#define mt std::make_tuple  
typedef std::tuple<int,int,int,int> pos;  
  
constexpr int dx[]={-1,1,0,0},dy[]={0,0,-1,1};  
  
constexpr int debug=0;  
  
int main(int argc, char* argv[])  
{  
    registerTestlibCmd(argc, argv);  
    constexpr int w=20;  
    F(i,1,w)  
    {  
        std::string _s=ouf.readLine();  
        if(_s.length()<w)  
        {  
            quitf(_wa,"Your puzzle is too short on line %d.",i);  
            return 0;  
        }  
        F(j,1,w) s[i][j]=_s[j-1];  
    }  
    int boxCnt=0,playerCnt=0,targetCnt=0;  
    int boxX=0,boxY=0;  
    int playerX=0,playerY=0;  
    int targetX=0,targetY=0;  
    F(i,1,w) F(j,1,w)  
    {  
        if(s[i][j]=='$') ++boxCnt,boxX=i,boxY=j;  
        if(s[i][j]=='@') ++playerCnt,playerX=i,playerY=j;  
        if(s[i][j]=='.') ++targetCnt,targetX=i,targetY=j;  
    }  
    if(boxCnt!=1) {quitf(_wa,"Your puzzle has %d instead of 1 box.",boxCnt);return 0;}  
    if(playerCnt!=1) {quitf(_wa,"Your puzzle has %d instead of 1 player.",playerCnt);return 0;}  
    if(targetCnt!=1) {quitf(_wa,"Your puzzle has %d instead of 1 target.",targetCnt);return 0;}  
        std::queue<pos> q;  
    q.push(mt(playerX,playerY,boxX,boxY));  
    F(i,1,w) F(j,1,w) F(p,1,w) F(q,1,w) dis[i][j][p][q]=infi;  
    dis[playerX][playerY][boxX][boxY]=0;  
    while(!q.empty())  
    {  
        pos u=q.front();q.pop();  
        int playerx=std::get<0>(u);  
        int playery=std::get<1>(u);  
        int boxx=std::get<2>(u);  
        int boxy=std::get<3>(u);  
        int d=dis[playerx][playery][boxx][boxy];  
        F(c,0,3)  
        {  
            int playerx2=playerx+dx[c],playery2=playery+dy[c];  
            if(playerx2>w||playerx2<1||playery2>w||playery2<1||s[playerx2][playery2]=='#') continue;  
            int boxx2=boxx,boxy2=boxy;  
            if(playerx2==boxx&&playery2==boxy)  
            {  
                boxx2+=dx[c];boxy2+=dy[c];  
                if(boxx2>w||boxx2<1||boxy2>w||boxy2<1||s[boxx2][boxy2]=='#') continue;  
            }  
            if(dis[playerx2][playery2][boxx2][boxy2]!=infi) continue;  
            dis[playerx2][playery2][boxx2][boxy2]=d+1;  
            q.push(mt(playerx2,playery2,boxx2,boxy2));  
        }  
    }  
    int minDis=infi;  
    F(i,1,w) F(j,1,w) minDis=std::min(minDis,dis[i][j][targetX][targetY]);  
    if(minDis==infi) quitf(_wa,"Your puzzle has no solution.");  
    else quitp(minDis,"Your puzzle can be solved in %d moves.",minDis);  
}

LLM 生成的推箱子分析与可视化绘图代码：

import argparse
import collections
import json
from pathlib import Path

SIZE = 20
DIRS = [(-1, 0, "u"), (1, 0, "d"), (0, -1, "l"), (0, 1, "r")]

def read_levels(path):
    levels = []
    rows = []
    for line in Path(path).read_text(encoding="utf-8-sig").splitlines() + [""]:
        if len(line) == SIZE and set(line) <= set("#$@.-_ "):
            rows.append(line.replace("_", "-").replace(" ", "-"))
        else:
            if len(rows) == SIZE:
                levels.append(rows)
            rows = []
    return levels

def solve(rows):
    grid = "".join(rows)
    n = len(grid)
    player, box, goal = (grid.index(ch) for ch in "@$.")
    neighbors = [[] for _ in grid]
    for p, ch in enumerate(grid):
        if ch == "#":
            continue
        y, x = divmod(p, SIZE)
        for dy, dx, move in DIRS:
            yy, xx = y + dy, x + dx
            if 0 <= yy < SIZE and 0 <= xx < SIZE:
                q = yy * SIZE + xx
                if grid[q] != "#":
                    neighbors[p].append((q, move))
    start = box * n + player
    parent = [-1] * (n * n)
    moves = [""] * (n * n)
    parent[start] = start
    queue = collections.deque([start])
    end = None
    while queue:
        state = queue.popleft()
        b, p = divmod(state, n)
        if b == goal:
            end = state
            break
        for pp, move in neighbors[p]:
            bb = b
            if pp == b:
                bb = b + b - p
                if not any(q == bb for q, _ in neighbors[b]):
                    continue
                move = move.upper()
            next_state = bb * n + pp
            if parent[next_state] < 0:
                parent[next_state] = state
                moves[next_state] = move
                queue.append(next_state)
    if end is None:
        return {"moves": -1}
    solution = []
    while end != start:
        solution.append(moves[end])
        end = parent[end]
    solution = "".join(reversed(solution))
    p, b = player, box
    box_visits = collections.Counter([b])
    player_visits = collections.Counter([p])
    pushes = []
    walk = 0
    delta = {move: dy * SIZE + dx for dy, dx, move in DIRS}
    for step, move in enumerate(solution, 1):
        p += delta[move.lower()]
        player_visits[p] += 1
        if move.isupper():
            bb = b + delta[move.lower()]
            pushes.append(
                {
                    "step": step,
                    "from": [b // SIZE + 1, b % SIZE + 1],
                    "to": [bb // SIZE + 1, bb % SIZE + 1],
                    "direction": move,
                    "walk_before": walk,
                }
            )
            b = bb
            box_visits[b] += 1
            walk = 0
        else:
            walk += 1
    return {
        "moves": len(solution),
        "pushes": len(pushes),
        "floor": n - grid.count("#"),
        "long_walks": sum(v["walk_before"] >= SIZE for v in pushes),
        "solution": solution,
        "push_trace": pushes,
        "box_visits": dict(box_visits),
        "player_visits": dict(player_visits),
    }

def draw(rows, result, output):
    from PIL import Image, ImageDraw, ImageFont

    cell = 36
    im = Image.new("RGB", (SIZE * cell + 60, SIZE * cell + 100), "white")
    d = ImageDraw.Draw(im)
    font = ImageFont.truetype("C:/Windows/Fonts/consola.ttf", 15)
    gates = {
        tuple(p["from"]): p["walk_before"]
        for p in result["push_trace"]
        if p["walk_before"] >= SIZE
    }
    for y, row in enumerate(rows):
        d.text((3, 34 + y * cell), str(y + 1), fill="black", font=font)
        for x, ch in enumerate(row):
            pos = y * SIZE + x
            color = "#343738" if ch == "#" else "#ffffff"
            if pos in result["box_visits"]:
                color = "#a3d9c3"
            if (y + 1, x + 1) in gates:
                color = "#efb664"
            rect = (
                35 + x * cell,
                30 + y * cell,
                35 + (x + 1) * cell,
                30 + (y + 1) * cell,
            )
            d.rectangle(rect, fill=color, outline="#c4c9c7")
            label = ch if ch in "@$." else str(gates.get((y + 1, x + 1), ""))
            d.text((rect[0] + 4, rect[1] + 8), label, fill="black", font=font)
    for x in range(SIZE):
        d.text((39 + x * cell, 8), str(x + 1), fill="black", font=font)
    d.text(
        (35, 765),
        f"{result['moves']} moves / {result['pushes']} pushes / {result['long_walks']} long walks",
        fill="black",
        font=font,
    )
    im.save(output)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("file")
    parser.add_argument("--out", default="analysis")
    args = parser.parse_args()
    out = Path(args.out)
    out.mkdir(exist_ok=True)
    for i, rows in enumerate(read_levels(args.file)):
        result = solve(rows)
        stem = Path(args.file).stem + (
            f"_{i + 1}" if len(read_levels(args.file)) > 1 else ""
        )
        (out / f"{stem}.json").write_text(
            json.dumps(result, indent=2), encoding="ascii"
        )
        (out / f"{stem}.xsb").write_text("\n".join(rows) + "\n", encoding="ascii")
        if result["moves"] >= 0:
            (out / f"{stem}.txt").write_text(
                result["solution"] + "\n", encoding="ascii"
            )
            draw(rows, result, out / f"{stem}.png")
        print(
            stem,
            {
                k: v
                for k, v in result.items()
                if k not in ("solution", "push_trace", "box_visits", "player_visits")
            },
        )

对小地图进行精确搜索与启发式搜索的代码见代码包 search_source.zip。

LLM 生成的下界证明中的地图生成器。接受一个参数 $m$（每条横带的锯齿数，整数且不小于 $2$），向标准输出打印一张 XSB 地图，如取 $m=2$ 有 python lower_bound_construction.py 2。默认取 $r=2\lfloor(8m+15)/14\rfloor$，即宽度 $8m+14$ 内可容纳的最大偶数横带数。输入 $m=7t$ 时取 $r=8t+2$。

import argparse

SHIFTS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def add(p, q):
    return p[0] + q[0], p[1] + q[1]

def expand(vertices):
    result = [vertices[0]]
    for a, b in zip(vertices, vertices[1:]):
        dx, dy = b[0] - a[0], b[1] - a[1]
        assert bool(dx) != bool(dy)
        d = ((dx > 0) - (dx < 0), (dy > 0) - (dy < 0))
        while a != b:
            a = add(a, d)
            result.append(a)
    return result

def construct(m, bands=None):
    if not isinstance(m, int) or isinstance(m, bool) or m < 2:
        raise ValueError("m must be an integer at least 2")
    if bands is None:
        bands = 2 * ((8 * m + 15) // 14)
    if not isinstance(bands, int) or isinstance(bands, bool) or bands < 2 or bands % 2:
        raise ValueError("bands must be an even integer at least 2")
    step, vertical, gap = 4, 3, 7
    w = 2 * step * m
    vertices = [(0, 0)]
    for j in range(bands):
        y = gap * j
        mirror = (lambda x: x) if j % 2 == 0 else (lambda x: w - x)
        for i in range(m):
            vertices.extend(
                (mirror(x), yy)
                for x, yy in (
                    (2 * step * i + step, y),
                    (2 * step * i + step, y + vertical),
                    (2 * step * i + 2 * step, y + vertical),
                    (2 * step * i + 2 * step, y),
                )
            )
        if j < bands - 1:
            edge, outside = (w, w + step) if j % 2 == 0 else (0, -step)
            vertices.extend(((outside, y), (outside, y + gap), (edge, y + gap)))
    goal = (0, gap * (bands - 1) - vertical)
    vertices.append(goal)
    path = expand(vertices)
    closure = expand([path[0], (-2 * step, 0), (-2 * step, goal[1]), goal])
    cycle = path + list(reversed(closure))[1:-1]
    core = set(cycle)
    expected_length = 14 * m * bands + 22 * bands - 6
    expected_pushes = 14 * m * bands + 15 * bands - 12
    assert len(path) - 1 == expected_pushes
    assert len(core) == len(cycle) == expected_length
    assert all(sum(add(p, d) in core for d in SHIFTS) == 2 for p in core)
    floor = set(core)
    gates = []
    for previous, c, following in zip(path, path[1:], path[2:]):
        a = (c[0] - previous[0], c[1] - previous[1])
        b = (following[0] - c[0], following[1] - c[1])
        if a == b:
            continue
        pocket = {
            add(c, (-b[0], -b[1])),
            add(c, a),
            add(c, add(a, b)),
            add(c, (a[0] - b[0], a[1] - b[1])),
        }
        assert len(pocket) == 4 and not pocket & floor
        floor.update(pocket)
        gates.append((c, following, pocket))
    assert len(gates) == 4 * bands * m + 2 * bands - 3
    for c, following, pocket in gates:
        contacts = {
            add(p, d)
            for p in pocket
            for d in SHIFTS
            if add(p, d) in floor and add(p, d) not in pocket
        }
        assert contacts == {c, following}
        # A box in a pocket has no legal push back onto the core cycle.
        for b in pocket:
            for d in SHIFTS:
                destination = add(b, d)
                support = add(b, (-d[0], -d[1]))
                assert destination not in core or support not in floor
    assert (-2 * step, -1) not in floor and (-2 * step - 1, 0) not in floor
    start, player = (0, 0), (-1, 0)
    xmin, ymin = min(x for x, y in floor), min(y for x, y in floor)
    xmax, ymax = max(x for x, y in floor), max(y for x, y in floor)
    width, height = xmax - xmin + 1, ymax - ymin + 1
    assert width == 8 * m + 14
    assert height == 7 * bands - 1
    n = max(width, height)
    shift = (-xmin, -ymin)
    marked = {start: "$", player: "@", goal: "."}
    rows = [["#"] * n for _ in range(n)]
    for p in floor:
        x, y = add(p, shift)
        assert 0 <= x < n and 0 <= y < n
        rows[y][x] = marked.get(p, "-")
    return ["".join(row) for row in rows]

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("m", type=int, help="Number of teeth per band, at least 2")
    args = parser.parse_args()
    if args.m < 2:
        parser.error("m must be at least 2")
    print("\n".join(construct(args.m)))

绘图程序：

from pathlib import Path
import matplotlib.pyplot as plt
import numpy as np
if __name__ == "__main__":
    data = np.array(
        [
            (3, 10),
            (4, 25),
            (5, 41),
            (6, 78),
            (7, 119),
            (8, 159),
            (9, 231),
            (10, 311),
            (20, 3582),
            (48, 107593),
        ],
        dtype=float,
    )
    n, moves = data.T
    fig, ax = plt.subplots(figsize=(7, 4.6), layout="constrained")
    ax.plot(
        n, n**4 / moves, ".", color="#b53c38", label="Record upper bound on beta(n)"
    )
    ax.scatter(
        n[:4],
        n[:4] ** 4 / moves[:4],
        facecolors="white",
        edgecolors="#b53c38",
        zorder=4,
        label="Exact beta(n), n=3..6",
    )
    sides = np.arange(30, 500)
    m = ((sides - 14) // 8).astype(float)
    r = (2 * ((sides + 1) // 14)).astype(float)
    values = (14 * m * r + 15 * r - 12) + (4 * m * r + 2 * r - 3) * (
        14 * m * r + 22 * r - 4
    )
    ax.plot(
        sides,
        sides.astype(float) ** 4 / values,
        ".",
        markersize=2,
        color="#256d85",
        label="Construction bound: n^4 / F(n), integer n >= 30",
    )
    ax.axhline(56, linestyle="--", color="#555555", label="Construction bound limit 56")
    ax.set(
        xscale="log",
        xlabel="Board side n",
        ylabel="Reciprocal density: n^4 / moves",
        title="Bounds",
    )
    ax.legend(fontsize=8)
    ax.grid(alpha=0.2)
    output = Path(__file__).with_suffix(".png")
    fig.savefig(output, dpi=170)
    plt.close(fig)
    print(output.resolve())

一些无关紧要的事情

通过分析，笔者还注意到 Sokoban Golf 比赛的第五名（$3314$）和第六名（$3312$）间的结构非常相似。箱子路径几乎完全一致，仅在一些墙的位置上有所变化。这里放出二者的对比图以供读者参考。