如何有效地为 8 球比赛打台球？

注意！这个答案是在轮换要求之前写的。请自行谨慎行事:)

这是我对这个问题的初步看法。

首先要做的是计算外部的奇偶校验 - 如果它适合“角落中的条纹”，则为 +1，如果它适合“角落中的固体”，则为 +0，如果是 8 球。这给了我们一个从 +12 到 -12 的范围，我们的目标是更接近的极端值。（如果为 +0，则选择 +12 或随机）

例如，这是 +1 +1 +1 -1 -1 +1 -1 -1 +1 +0 -1，因此它是拐角处的 -1 倾斜实体：

x o x x o
 x o x o
  8 x o
   o x
    o

接下来要做的是将 8 球移动到中心。如果你可以用它进行两次相邻交换，将两个球移动到位，而不是一个相邻的交换，只将一个球移动到位（或者如果它在角落里，则进行一个不相邻的交换），那就这样做。

x o x x o
 x 8 x o
  o x o
   o x
    o

在我们移动 8 个球后，共享一个球的两个相邻交换的所有组合都可以由非相邻交换产生相同的结果，因此我们必须同时考虑更少的复杂性。

按此优先级对所有剩余移动进行排序：

-外侧两个相邻球之间的交换是“价值 4”（如果这是我们的最后一个球，则为 2）

-两个相邻球之间的交换，一个在外面，“价值 2”（如果这是我们的最后一个，则为 1）

-外侧两个球之间的交换是“价值 2”

-两个球之间的交换，一个在外面，是“价值 1”

并从上到下执行它们。

因此，我们将 o 移到顶部，左边 （4），将 o 移到 （2） 中右边，将 o 移到 （2） 中左下角，然后将 x 顶部与中间 （2） 的 o 交换。我们最终在2-2-1系列赛中进行了五次交换，所以三次移动。

o x o x o
 x 8 x x
  o o o
   x x
    o

（值得注意的是，如果我们瞄准角落的条纹，这个问题也会很快得到解决。

x x o o x
 o 8 o x
  o x o
   x o
    x

我认为要求 4 圈是不可能的，但我还没有向自己证明这一点。

另一个工作的例子：

它的奇偶校验为 +1，因此我们的目标是角落中的条纹：

8 o o o x
 o o o x
  o x x
   x x
    x

将 8 球与中心 X 交换 (1-)

x o o o x
 o o o x
  o 8 x
   x x
    x

交换两个相邻的外侧，4分 (1-1)

x o o o x
 o o o x
  x 8 x
   o x
    x

将相邻边交换为中心，2 点 (1-2-)

x o o o x
 o o x o
  x 8 x
   o x
    x

边到边交换，2 点 (1-2-1-)

x o x o x
 o o x o
  x 8 x
   o o
    x

3步。

编辑：这对于开篇文章中的示例非常有效，分两步解决：

它的奇偶校验为 +1，因此我们的目标是角落中的条纹：

x x o o x
 o o x o
  o o 8
   x x
    x

将 8 与边缘的 x 交换，然后用 o 在中心交换（求解两条边缘） (2-)

x x o o x
 o o x o
  o 8 x
   x o
    x

交换左上角和左下角的相邻 O 和 X（求解四条边） (2-2-)

x o x o x
 o o x o
  x 8 x
   o o
    x

2步。

你有 2 个八球，作弊者。

在给定的示例中，解决方案需要 2 个动作：

2-5， 3-8，
3-4， 11-12

最好通过为动态规划 （DP） 配置问题来找到最佳解决方案。由于问题是多阶段的，具有固定成本且没有不确定性，因此将存在一个以最佳方式解决问题的 DP 矩阵。

要创建矩阵：请注意，考虑到对称性，8 球可以位于 9 个位置之一。固体可以以大约 （14 选择 7）/2=1716 的不同方式排列。这意味着机架配置的总数约为 1716 * 9 = 15,444。因此，您有 15,444 种不同的可能状态。计算从这些状态中的任何一种状态到任何其他状态的成本。这导致基质具有 15,444 * 15,444 个细胞，或大约十亿个细胞的四分之一。识别所有最终状态单元。为了求解矩阵，您需要从起始状态向前搜索，直到达到结束状态（或直到您达到的总成本大于当前最小成本）。通过这样做，您将可以证明地找到了所有成本最低的路径。

请注意，上述解决方案有些幼稚，可以通过各种方式进行优化以产生更小的矩阵。例如，您可以使用旋转对称性来减少单元数，并将成本 1（用于旋转机架）添加到正确的路径上，但将 8 球置于低中心位置之一除外。

Pseudocode:

Create DP Matrix:

(1) determine number of possible arrangements, A, of balls
(2) for each arrangement, make a list of possible unique moves  
---- the possible moves are:  
------- rotating right  
------- rotating left  
------- exchanging any pair of balls  
------- exchanging any two pairs of adjacent balls  
(3) for each move in A store a pointer to the resulting arrangement  
(4) for each arrangment make an attribute indicating whether it is an end state  

Solve Problem  
(5) goto arrangement for starting position S  
(6) set best-cost-so-far (BCSF) variable to infinity
(6) breadth search from S, accumulating current cost CC as +1 for each transition
(7) if you reach an end state CC < BCSF, then set BCSF = CC and make solution list contain only the current path
(8) if you reach an end state CC = BCSF, then add path to solution list
(9) if CC > BCSF abandon branch and try next branch

The result will be a list of all possible solutions and the minimum cost BCSF.

这是一个具有挑战性、令人深感沮丧和有趣的问题。我的猜想是，以下是一个最佳解决方案：

• 根据 Patashu 的奇偶校验方法选择条纹或实体是否位于拐角处
• 无轮换
• 每次计时，都要做出得分最高的一步，除非 +3 的动作可以将 8 球放在中间
• 在平局的情况下，选择无关紧要吗？编辑：请参阅底部的注释。关系是困难的。

（我根据正确位置的球数的净差异来对动作进行评分。

以下是两个机架示例：

    x            8
   x x          o o
  o o x        o o x
 o o x x      o x x x
8 o o o x    o x x o x

如果我们从左到右对位置 1 到 15 进行编号，然后从上到下，第一个机架 求解为 （2-4/3-5）（5-11）（10-13），第二个机架求解为 （4-8/11-12）（5-10）（1-5）。

我最近一次的证明尝试中，只有 11 个不同的机架在对称性上失败了一部分（上面显示的两个是失败的变体）。以下是我在尝试中发现的两个引理，希望它们能帮助其他人进行证明。

引理 1：不需要轮换

请注意，如果我们需要在解决方案中的某个点进行轮换，则何时进行轮换并不重要（轮换不会更改任何可用的交换）。此外，我们最多只需要旋转一圈，因为顺时针旋转 2 次 = 逆时针旋转 1 次，反之亦然。

因此，如果需要，让我们选择在最后一步进行轮换。此时，由于外部的旋转对称性，外部必须是正确的。因此，8 球将位于三个中心球之一中。如果它在正确的位置，我们不需要轮换。否则，我们可以使用它，但请注意，交换也会完成机架。因此，在最佳解决方案中没有必要。

引理 2：贪婪是最佳的，如果它在 3 步内解决机架

让策略成为贪婪的解决方案，让策略成为任何试图更快的非贪婪解决方案。 必须至少做出一个不贪婪的举动。这必然不能是最后一步。因此，如果用 n 个回合来完成一个机架，则必须在第 n-2 回合或更早的时候进行非贪婪移动。这意味着，如果在 2 圈或更短的时间内解决机架问题，则它是最佳的。ABBABA

---

编辑：好吧，我刚刚在编程测试中运行了我的算法，发现它甚至不一致。事实上，这种联系似乎很难打破。请考虑以下机架：

    x
   o o
  x o x
 x 8 o x
x o o x o

我的算法将执行以下移动序列之一：（5-8/13-14）（7-8/10-15）、（5-8/10-15）（7-8/13-14）、（5-8/14-15）（10-13）（7-8）、（5-8/14-15）（7-8）（10-13）、（5-8/9-10）（14-15）（7-13）、（5-8/9-10）（7-13）（14-15）、（5-8/9-10）（13-14）（7-15）或（5-8/9-10）（7-15）（13-14）。前两个在最优的 2 个时间度量中求解它，但其他的在 3 个时间度量中求解它。问题是 （14-15） 和 （9-10） 开关在第二回合破坏了可能的 +4 移动。对此算法的修改可能需要提前查看，然后很快就会变得复杂。我开始认为没有“简单”的解决方案，@JeffreySax的解决方案是要走的路。另请注意，此机架也击败了贪婪的解决方案。贪婪的解决方案可以做 （13-14/10-15）（5-8）（7-8） 或 （13-14/10-15）（7-8）（5-8）。

Salut，首先我必须说这是一个非常有趣和有趣的问题，也是我在架子时没有想到的事情，尽管在总共 15 个球时，一些额外的动作并不重要。

从货架描述和图像中，我们得到以下规则：

1. 角总是相同的类型
2. 每边的中间始终与角的类型相同
3. 每组接触角的 2 个球始终是相同的类型（与角的类型相反）
4. 内三角形总是有 8 球、条纹和实心（8 球在顶部）
5. 在两侧，彼此靠近的球将始终交替出现

正如 中@DPenner所述，轮换不是必需的，因为它们可以被交换所取代，前提是成本相同。如果您是 Rubick 的粉丝并选择使用它们，您只需要一个。Lemma 1

少于 4 次交换无法解决！（ 总是 )

您的示例图像最好证明这一点，无论您以哪种方式计算，您都需要将 6 个色球从它们的位置移开，而 8ball => 即 31/2 交换，因为交换需要 2 个球，让我们将其四舍五入为 4 个交换。
为什么会这样？
因为它不符合所有规则：

• [5,1,4] [2,6] [11,13] [10,12]不能彼此靠近（中断 5）
• 8ball在一边而不是中间三角形（断点 4）
• [5,4] [6,12] [13,9]不是所有的类型都是一样的（断点 3），而且在集不对角的情况下（再次断点 3）[1,5,4]
• [2]并且与拐角（断点 2）的类型不同[11]

算法

第一步：固定 8ball 将 8ball
换到它的位置。无论如何，它都需要在那里。
这是唯一的旋转机会（以防 8 球从内三角形开始，但位置不正确）

在红色位置计算相同类型的球最多。
数量最高的球会留下来，其余的位置必须换掉。

IF count is 3 {
    #inside triangle will choose 
    IF inside triangle has 2 of a kind, that type stays (in the red spots)
    ELSE pick random
}

开始交换：

• 做弯道（选择一个需要改变的球，然后在一个角落里找到一个相反的球）
• 做中间（选择一个需要改变的球，并在一侧的中间找到一个对面的球）
• 如果完成角和中间，则最后一次交换在内三角形中

演示您的示例：

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside is correct, random pick: stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(3)  #move4
Done.

如果随机选择会选择固体留下来：

Pick 6, swap with corners(10)  #move2
Pick 13, swap with corners(1)  #move3
Pick 9, swap with corners(14)  #move4
Done.

演示2：

将 3 改为 7，将“白球 8 号”替换为 15 号球

swap 8 with 3  #move1
count[stripe]=3 [6,13,9]  
count[solid]=3 [5,4,12]
highest count=3, checking inside, inside has 2 of a kind(stripes) => stripes stay
Pick 5, corners() correct, swap with middles(2)  #move2
Pick 4, corners() correct, swap with middles(11)  #move3
Pick 12, corners() correct, swap with middles(15)  #move4
Done.

Have fun!

PS：您可能还喜欢灰色位置的算法变体#2，但是我发现在现实生活中使用红点更容易。counts

有可能的位置。其中，4 个是最终的：球 8 和 9 可以交换，条纹/实心可以反转。我们会说这些位置的距离为 0。15!/(7!7!1!)=51480

对于这 4 个仓位中的每一个，生成所有可能的移动（1 个掉期或 2 个相邻掉期）。对于这些以前从未见过的移动生成的每个位置，请记住使用哪个移动来生成它，并给这些位置距离 1。然后对距离 1 处的每个位置执行相同的操作，并赋予新位置距离 2。继续这样做，直到没有更多的新职位。

这利用了这样一个事实，即正如@DPenner所指出的，旋转总是可以用相邻的移动来代替。

由于掉期是它们自己的反向，因此从位置 A 移动到 B 的移动也是将位置 B 带回 A 的移动。

因此，您最终会得到一个包含所有位置的列表，对于每个不是最终位置的位置，可以肯定的是，这将使其更接近最终位置。

您会发现有 232 个位置至少需要 4 次移动。（编辑：我的邻接表之前包含一个错误。例如：

      6-9,14-15     2-12       2-5,4-7       1-2
    x           x           x           x           o
   x x         x x         8 x         o x         x x
  x o x   =>  x o o   =>  x o o   =>  o 8 o   =>  o 8 o
 o o o x     o o x x     o o x x     x o x x     x o x x
o 8 o o x   o 8 o x o   o x o x o   o x o x o   o x o x o

没有超过 4 次移动的初始位置。

编辑：首先在 8 球中交换的策略不是最佳的。例如：

         5-11     12-13,14-15    4-7,6-10
    x            x            x            x
   o o          o o          o o          o o
  o x o   =>   o 8 o   =>   o 8 o   =>   x 8 x
 x o x x      x o x x      x o x x      o o x o
8 x o x o    x x o x o    x o x o x    x o x o x

但我们可以做得更好：

         3-11       1-2,3-5
    x            x            o
   o o          o 8          x x
  o x o   =>   o x o   =>   o 8 o
 x o x x      x o x x      x o x x
8 x o x o    o x o x o    o x o x o

问题是 x 是错误的角球类型，所以我们输了一步棋。

相反，策略应该是寻找一个不合适的球，但不能与相邻的球交换，因为它们是同一种类的，或者它们已经在位置上。角应该是首选，因为它们具有最少的相邻交换选项。它应该换成适合该位置的正确类型的球。如果第一个球最终位置的球是错误的，则应选择错误位置的相邻球。这样，随后的相邻交换将把这些球放在正确的最终位置。

在上面的（计数器）示例中，8 球需要长时间交换才能到达其最终位置。但是，#5 中的 x 是错误的类型，因此我们改用相邻的 o（第 2 行中的第 2 个）进行交换。

前面的 4 步示例求解如下：

        11-2         12-5        13-3       9-10
    x           x           x           x           x
   x x         o x         o x         o o         o o
  x o x   =>  x o x   =>  x 8 x   =>  x 8 x   =>  x 8 x
 o o o x     o o o x     o o o x     o o o x     o o x o
o 8 o o x   x 8 o o x   x o o o x   x o x o x   x o x o x

第一步，我们选择左下角的 o。第一个 x 位于位置 2。然后我们在 #12 处选择 8，我们可以将其带回家 #5。接下来是底行中间的 o。我们将其与#3处下一个错误放置的x交换。最后，我们交换 #9 和 #10 以获得最终机架。路径与以前不同，但我们仍然用 4 步走完了。

编辑：还有一点：在进行相邻交换时，应优先考虑那些最终没有将两个球都放在最终位置的球。原因是这意味着总共至少需要两步，因此最好尽快迈出第一步。

例如，问题中的齿条可以通过两步解决：（2-4），（5,6）和（3-6），（12-13）。8 球首先被移动到它的最终位置，即使它被交换的白球还没有在它的最终位置。如果先完成两次外围交换 （2-4）、（12-13），您仍然需要两步才能到达最终的机架，总共需要 3 步。