chessboard.js - 如何找到最小的移动次数？

Question

注意：-我已经通过回溯方法解决了上述问题，通过尝试所有不同的方式，我正在寻找一种非常有效的方式/模式。

我们得到一个大小为 'N' X 'N' 的棋盘。但它可以包含任意数量的 white-squares 和 black-squares ，也可以是 any-order 。

假设有白色的“a”正方形和黑色的“b”正方形，那么，

[ a+b=n*n ]

我们必须继续在棋盘上用黑色方块移动，直到没有移动为止。

这就是移动中发生的事情：-

1）我们在坐标：-(row,column) 处选择一个黑色方块并将其移动到 (row-1,column+1) ，前提是坐标 (row-1,column+1) 也包含一个黑色方块。移动到新位置后，旧位置，即 [row,column] 变为空，即颜色变为白色。

或者

2）我们在坐标：-(row,column) 处选择一个黑色方块并将其移动到 (row-1,column-1) ，前提是坐标 (row-1,column-1) 也包含一个黑色方块。移动到新位置后，旧位置，即[行，列]变为空，即它的颜色变为白色。

我们必须以最少的步数结束这场比赛，问题是找出这些步的顺序。

让我们用'1'表示黑色方块，用'0'表示白色方块......

例子：-

3X3 棋盘：-

0 1 0

1 0 1

0 0 0

以最少步数结束游戏的步数：-

1）将[1,0]处的黑色方块移动到[0,1]......现在棋盘看起来像这样： -

0 1 0

0 0 1

0 0 0

2）我们将[1,2]处的黑色方块移动到[0,1]，棋盘看起来像这样：-

0 1 0

0 0 0

0 0 0

现在，没有有效的移动，游戏结束:-)

给定一个大小为“N”x“N”的棋盘和任何黑白格子的配置，如何找到以最少步数结束游戏的步数？

标签： chessboard.js

Answer 1

您可以查看此问题的一种方法是将其视为图形遍历。由于我们正在寻找最短的移动，我们可以利用我们对图遍历算法的知识并考虑使用广度优先遍历。

我们将需要能够做几件事来实现这一目标：

• 给定一个具有某种配置的棋盘，计算所有可以采取的合法棋步。
• 给定一个具有某种配置的棋盘和一个合法的移动，计算应用该移动后棋盘的配置。
• 给定一个棋盘的某种配置，检查这个配置是否是终端的（这样就不能从这个位置进行其他移动，游戏就结束了）。

现在我们有了这个，让我们看看如何将这个问题映射到图遍历问题。

• 让初始配置成为图的根节点。
• 引出根节点的边是我们可以从这个位置进行的合法移动。
• 这些边指向的子节点是将边标签上的移动应用于父节点的配置。

然后寻找到终端位置的最短路径的过程将如下所示（从根节点开始）：

• 通过在给定此配置的情况下生成所有合法移动来扩展根节点的子节点。
• 检查每个孩子以查看是否已达到终端配置。
• 如果没有，请以呼吸优先的方式扩展子项（BU 的此链接包含有关此类遍历的实现细节的更多详细信息）

呼吸优先遍历的魔力在这里发挥作用。从这里我们重复这个扩展节点的过程，检查终端配置，如果我们没有找到这样的配置，则在图表中下降一个级别。

一旦我们找到了终端配置，我们就知道从根节点（初始配置）到终端节点（游戏结束位置）的路径（代表移动的边）是最短的。我们现在所做的就是计算返回根节点的边数，并且我们知道最小移动次数是多少。