跳转到内容

拼图/棋盘拼图/车马多项式

来自维基教科书,开放的书籍,开放的世界

该拼图最早由亨利·恩斯特·杜德尼 (Henry Ernest Dudeney) 在 1917 年的著作《数学中的消遣》(Amusements In Mathematics) 中提出,他的原话如下:

Every square is again either occupied or attacked, but in this case every rook is unguarded. Now, in how many different ways can you so place the eight rooks on the board that every square shall be occupied or attacked and no rook ever guarded by another? I do not wish to go into the question of reversals and reflections on this occasion, so that placing the rooks on the other diagonal will count as different, and similarly with other repetitions obtained by turning the board round.


前提类似于 拼图/棋盘拼图/八皇后问题,如何在 8x8 的棋盘上放置尽可能多的八个车,使得这些车不会互相攻击/保护。

车的合法移动是水平或垂直方向。

解决方案

[编辑 | 编辑源代码]

以下是车马多项式动画之一的动画。

根据上面的动画,您可以看到 X 代表车的攻击范围,随着每次车的位置变化,车在棋盘上的可放置位置越来越少。


由于车只能沿着直线移动:它必须在每一行和每一列上。

从顶行开始,很明显我们可以将第一个车放在八个不同方格中的任何一个上。

无论它放在哪里,我们都有七个方格可供选择作为第二行的第二个车。

然后我们有六个方格可以从第三行中选择,第四行有五个方格,依此类推。

因此,我们不同的方法的数量必须是 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320(即 8!/8 的阶乘),这是正确的答案。


参考书目

[编辑 | 编辑源代码]
华夏公益教科书