查找可以生成所提供的Connect-4板状态的任何顺序的动作

Question

给出矩阵A（6x7）中的有效Connect-4板状态，其中

A[i][j] = '0',  if empty,
A[i][j] = 'r',  if filled with red stone,
A[i][j] = 'y',  if filled with yellow stone.

我正在尝试一种算法，该算法可以返回可以生成给定板状态的任何有效移动顺序。

可以假设红色总是开始游戏。

示例：

A = [0 0 0 0 0 0 0
     0 0 0 0 0 0 0
     0 0 0 y 0 0 0
     0 0 0 r 0 0 0
     0 0 0 y 0 0 0
     0 0 r r 0 0 0]

Valid sequence of moves:- 44443 

44443表示->第一位玩家进入第4列然后第二名玩家进入第4列，...（以列号为1索引）

我的方法：--）首先通过非空位置数量的奇偶性找出最后一块石头的颜色。将该颜色设为last_coloured。-）然后从板上取出一块最上面的颜色last_coloured的石头，递归地继续前进，如果找不到任何一块颜色last_coloured的石头，则回溯。

尽管这种方法可以用不到16 ^ 21的步长来解决7 * 6的电路板。（编辑：感谢@Prune纠正了这个上限）

问题1）上述方法的步骤数是否有更好的界限？问题2）有更好的方法吗？

Answer 1

认为这不是Connect-4，而是同一板上的单人纸牌游戏。您的目标是清除所有结石。您有清除石头的规则；现在，如果您具有评估任意板位置的良好功能，它将改善搜索树。

由于您交替进行颜色去除，所以您有

• 规则：任何清除都必须至少使另一种颜色的石头裸露
• 启发式：在红色和黄色宝石之间保持平衡
• 启发式：如果一列仅包含一种颜色的宝石，那么从该列中除去宝石是最后的选择。

这也将导致评估功能中的第二个术语：如果您的石材供应不平衡，请确定您需要奖励挖掘以获得稀有颜色的一列。

对于这么小的一块棋盘，我猜想一个相对简单的启发式方法将为任何实际游戏位置提供有效的解决方案，而不会发生回溯：两位玩家的合理策略将促进易于导航的宝石混合。

足够让您动起来吗？