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

Question

由于 8 球比赛的台球击球可以在多种规则下完成，所以我指的是这样的击球：

即 8 号球必须在中心，并且沿两侧条纹和固体必须交替。剩下的两个球（条纹和实心）无关紧要。

假设您刚刚完成了一场比赛，收集球，将它们放在架子上，然后继续安排它们开始新的比赛。现在它们的顺序是随机的。你如何进行？

_{免责声明：绘画艺术如下}

一个简单的方法是按顺序开始，顶部 -> 底部和左侧 -> 右侧。

例如，我们假设1在正确的位置。5不是，我们将它与 交换2，然后4与3（或与8）交换，但这已经是低效的，因为我们要么将 移动4到中心，要么将8in4的位置 - 即不是它必须在最后的位置.

还有我们想要在角落里制造哪种类型的球的决定。你如何预先决定？你应该考虑有多少球已经到位？在我的例子中，如果你想要角落里的灰色，你已经有 3 个就位（球 1、10、14）。如果你想要角落里的白色的，你只有 2 个就位 (2,11)。这应该重要吗？

为了形式化这一点，我们可以假设有二我们可以做的三个操作：

• 交换两个相邻的球
• 交换两个不相邻的球
• 旋转机架

由于我们可以使用双手，假设我们可以并行化第一个操作（同时交换 2 对球），而我们一次只能交换两个不相邻的球。

什么方法最适合这个任务，使时间最小化（在描述的时间单位中）？贪婪会是最好的吗？（这就是我把它们架起来时的做法，我猜）

编辑：根据现有（或以前的答案） - 您可能会假设角落中的条纹多于实体意味着步幅会更喜欢角落 - 并不是说​​这不是真的，但如果您做出这样的假设，请证明它。

Answer 1

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

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

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

例如，这是 +1 +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顶部与中间的o交换（2） . 我们最终在 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

交换中心 x 的 8 个球 (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

用 x 在边缘交换 8，然后用 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个动作。

Answer 2

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

对于这 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 交换，即第二行中的第二个。

前面有 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 位于位置二。然后我们在#12 选择 8，我们可以把它带回家到 #5。底行中间的 o 是下一个。我们将它与 #3 的下一个错误放置的 x 交换。最后，我们交换#9 和#10 以获得最终机架。路径和以前不同，但我们还是用 4 步走的。

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

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

Answer 3

你有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.

Answer 4

萨鲁特，首先我必须说这是一个非常有趣和有趣的问题，而且是我在打球时没有想到的，尽管总共有 15 个球，一些额外的动作并不重要。

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

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

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

不能在少于 4 次交换中解决！（总是）

您的示例图像最能证明这一点，无论您如何计算，您都需要从它们的位置移走 6 个彩球，而 8ball => 是 3½ 次交换，因为交换需要 2 个球，所以我们将其四舍五入为 4 次交换。
为什么是这样？
因为它不符合所有规则：

• [5,1,4] [2,6] [11,13] [10,12]不能彼此靠近（休息 5）
• 8ball位于一侧而不是中间三角形（中断 4）
• [5,4] [6,12] [13,9]并非都是相同的类型（中断 3），而且在[1,5,4]集合不与角落相对的情况下（再次中断 3）
• [2]并且[11]与角的类型不同（中断 2）

算法

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

Count红色位置同类型球最多。
最高计数的球留下，其余的点必须换掉。

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但我发现在现实生活场景中使用红点更容易。

Answer 5

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

• 根据 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 步内解决机架，则它是最佳的

让策略A成为贪婪的解决方案，让策略B成为任何试图更快的非贪婪解决方案。B必须至少做出一次非贪婪的举动。必然地，这不可能是最后一步。因此，如果A需要 n 轮完成一个机架，则B必须在第 n-2 轮或更早时进行其非贪婪移动。这意味着如果A在 2 圈或更短的时间内解决齿条问题，这是最佳的。

---

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

    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)。