舞蹈链和意大利炮的故事(Dancing Links)

部队缴获了一些意大利炮,团长高兴得不得了。
“手里的家伙好,咱腰杆子就硬”。
团长美滋滋的把这些炮都安置到自己阵地上,好形成交叉火力。
阵地是纵向的,每行的地块作用都不同。

1处即为意大利炮,0表示没有
指挥部那一列摆着三架意大利炮,真好玩。

旅长:恭喜你发财了啊!
团长:穷的都快要饭了。
旅长:你那些意大利炮,自己留七座防守,其余的送旅部来。
团长:你这抢劫啊,坚决不行。
旅长:那咱俩说道说道。

当然,团长还是没能说过旅长。
这下可气死团长。但为了保证火力精确覆盖和战略纵深,以及节省搬运炮的劳力,团长还得选择几个行的集合,使每列地块都包含一座意大利炮。
团长把政委叫来,政委拿来地图,开始研究起来。
政委意识到,得先确定每座炮上下左右都有什么炮。
于是团长又叫和尚给每列地块和每座炮都编上号。
虽然在缴获意大利炮之前给地块编过号,但这次还是得重新将每个地块的上下左右重新编。
不过编号的时候,和尚可是翘着二郎腿嗑瓜子的——他在“锻炼”新兵。
不论怎样说,号码是编好了。

于是就变成了下面阵地设施地图就变成了下面这个样子。
其中cx代表列数,数字代表编号。

团长:你小子可得确保7条路线每条都要有一座,否则敌人打进来可太容易了。
政委:我们先从左上角的地雷那儿开始。要是地雷右边没有cx标号的话,说明那列已经选好防守的意大利炮了。
团长:接着说。
政委:我们先从左翼西开始。左翼西,只有散兵坑和低洼地有炮。
假设我们选择散兵坑,那么低洼处也就不用摆放意大利炮了。
团长:对对,低洼处用来吃地瓜烧多好啊。
政委:我们选择了散兵坑,那么意味着中部中这条路线也没有也有了防守,那么编号为14的意大利炮就不需要了。也就是说指挥部那行的14 15 16号意大利炮都不需要了。
右翼东有了防守,也意味着编号13所在的后勤处的意大利炮也就不需要了。
团长:嗯。
政委:这样我们就不用再考虑左翼西,中部中和右翼东了。散兵坑,低洼处,后勤处,指挥部也就可以忽略了。然后我们的地图就变成了这样。

团长:后面一下空了许多。
政委:对,这样我们就能递归把复杂问题转换为简单问题了。
注意到,我们已经把c1,c4,c7的标号都撤去了。
但这样麻烦又来了,还有四路没选好由哪座意大利炮覆盖呢!
团长:前哨所和主堡垒不是还有嘛。
政委:你仔细看看,假如我们保留前哨所的炮的话,那么左翼东就没有防守,假如我们保留主堡垒的炮的话,中部东又变得岌岌可危。
团长:对,敌人很容易从那儿摸上来。去年敌人大扫荡,因为防守上的缺陷,丢了很多装备,
死了很多弟兄,穷得快只剩裤子了。
政委:对,我们那时队伍发展过快,好高骛远,吃了惨痛的教训。
团长:算你还有点头脑。
政委:那么这样说明我们第一步就选错了。不应该选散兵坑的炮,而应该试试选低洼处的的那一列。因为左翼西已经有炮了,那么散兵坑那列就不需要了。中部中已经有炮了,那么指挥部那列也不需要了。这样地图就变成了这样。

政委:继续从地雷选起,左翼东还没选好。同样是为了保证左翼东的安全,我们得从主堡垒和后勤处留下一列。同样,我们先选主堡垒的。为了防止一条路线上有多条的炮,前哨所和后勤处两列也不需要了。
团长:嗯。

政委:再找地雷的右边。麻烦了,中部东那路又成了敌人入侵的捷径。而我们已经没有多余的炮可以防守了。
团长:我就说嘛,后勤处不留武器的话,那里的人眼睛都得瞪得像个铃铛。上次有个做军鞋的娘们就从我这里坑走一把友军手枪。
政委:我看你怎么向友军交代。话说回来,既然保留后勤处那列的话,主堡垒那列就不需要了。
团长:不要也行,反正围墙厚着呢。
政委:前哨所那列炮也得留下来。这样七路我们就就都有意大利炮防守了。七路cx标号都撤掉,检查地雷右边已经没有标号了。最后地图就像这样子。框住的是保留的。

团长:你他娘真是个人才!

Leave a Reply