java文字游戏求解算法

Question

该游戏由一个由3X3到7X7个字母组成的正方形棋盘组成。玩家必须在棋盘上找到最多10个给定单词（最难的情况）。字母必须相互接触（在周围的8个方格内）。当一个单词被发现时，它会被移除，重力会使上面的方块填满空隙（字母永远不会水平移动）。如果你熟悉手机游戏WordBrain，这个机制是相同的。不同之处在于，所有单词都是为您提供的，因此算法不需要字典来查找真正的单词。单词可以按任何顺序找到，当棋盘空了，游戏就结束了

示例（7X7，8个单词）：

起始状态：

C E F S C R E
R A U C G C E
T R N A R R C
E C A R C E E
A E E A E A H
R R C A M E L
I E R A R E R

Find: ARCHER CAMERA CARRIER CEREAL 
      CREATE FURNACE GREECE SCARE

现在，玩家决定删除单词CARRIER（粗体字母）：

由此产生的董事会状态：

      S C R E
    F C G C E
    U A R R C
C E N R C E E
R A A A E A H
T R E A M E L
E E C A R E R

Find: ARCHER CAMERA CEREAL 
      CREATE FURNACE GREECE SCARE

我保证起始状态是可解的。现在携带者被移除了，我不再有任何关于可解性的保证

游戏就是这样玩的。从算法的角度来看，解决这个问题的正确、最有效的方法是什么

编辑：应这个伟大的SO社区的要求，使问题更加简洁

Answer 1

我已经做了很多文字游戏，所以我会在这里评论一个整体的方法，我相信这是NP，所以只适用于小型电路板。由于问题更多的是寻找一个棋盘清理解决方案，而不是寻找可能的单词，因此我将不讨论如何解决给定长度n的所有可查找单词的问题，正如前面提到的，它可以通过使用前缀尝试来解决，并且在谷歌中非常适合搜索。此外，我假设列在一起移动，就像一列清除时的标准匹配3

几乎所有游戏求解者的算法设计都有相似的模式。对于match3游戏：

https://gamedev.stackexchange.com/questions/15063/ai-for-solving-a-match-3-game https://www.gamedev.net/forums/topic/575282-solving-bejeweled-type-game/

1. 制定可能的行动
2. 根据评估启发式对可能的动作进行排序
3. 每走一步，重新评估， 注意：移动意味着将节点添加到树中
4. 在树上潜水
5. 如果结果为启发式<；之前，爬树修剪
6. 拜访下一个兄弟姐妹

因此，关于你的规则的讨论就来了

1. 什么是好的成本函数

在这个游戏中，最佳目标是删除一个单词，使生成的网格尽可能保持正方形。这将最大限度地发挥每个字母的潜力。只有一个相邻字母的孤立字母大大减少了可能的单词列表。因此，一个好的成本可能是一块木板的“方正度”

1. 根据评估对可能的移动进行排序

   这里的起点可能只是长度搜索。试着先写出最长的单词

2. 早期测试的艺术

如果拼图是由相同长度的N个单词组成的，那么如果可能的单词列表不包含这样长度的单词，那么很容易提前完成。从最左边和最右边的边缘开始，如果其中一列有一个只有一个字母的字母，则可以几乎立即返回某些bigram

想想这个例子：

    B I
    A G 
Z X C T Y Y

这应该被认为是一个糟糕的电路板，因为没有单词以Z X开头或以XZ结尾