如何有效地架起台球8球游戏？
由于八球比赛的撞球可以在多种规则下完成，下面是我所说的撞球：
即8球必须在中心，沿着两侧的条纹和固体必须交替。 剩下的两个球（条纹和实心）并不重要。
假设你刚刚完成了一场比赛，收集球，把它们放在架子上，并继续安排他们开始一个新的。 他们现在是随机的顺序。 你如何继续？
免责声明：油漆艺术如下
一个简单的方法是按顺序开始，顶部 – >底部和左 – >右。
所以举个例子，我们假设1在正确的位置。 5不是，我们把它换成2 ，然后我们把4换成3 （或8 ），但是这样做已经是效率低下了，因为我们已经把4移到了中心位置，或者把4移到了4的位置 – 也就是不是它必须在哪里结束。
也有决定哪些types的球我们想要在angular落里被做。 你如何决定这个前期？ 你应该考虑到已经有多less球？ 在我的例子中，如果你想要灰色的angular落，你已经有3个（球1,10,14）。 如果你想要在angular落里的白色的，你只有2个在位（2,11）。 这件事情呢？
为了使这个正式化，我们可以假设有这个 二 我们可以做三个操作：
- 交换两个相邻的球
- 交换两个不相邻的球
- 旋转机架
既然我们可以用双手，假设我们可以平行第一个操作（同时交换两个球），而我们一次只能交换两个不相邻的球。
什么方法最适合这个任务，以最小化时间（以所描述的时间单位）？ 贪婪是最好的吗？ （我想我是这样做的，当我把它们架起来的时候）
编辑：根据现有的（或以前的答案） – 你可能会认为有更多的条纹比实体的angular落意味着步伐会喜欢angular落 – 并不是说这是不正确的，但如果你做出这个假设，请certificate。
注意！ 这个答案是在轮换要求之前写的。 谨慎行事:)
这是我最初看到的问题。
要做的第一件事就是计算外部奇偶性 – 如果它适合“angular落中的条纹”，则为+1;如果适合“angular落中的实体”，则为-1;如果是8个球，则为+0。 这给了我们从+12到-12的范围，我们瞄准了我们更接近的极端。 （如果+0，select+12或随机）
例如，这是+1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +0 -1，因此它是在angular落中倾斜的实体-1：
xoxxo xoxo 8 xo ox o
接下来要做的是把8号球移到中间。 如果你可以做两个相邻的交换，它将两个球移动到位，而不是一个相邻的交换，只移动一个球进入位置（或者一个非相邻的，如果它在一个angular落），这样做。
xoxxo x 8 xo oxo ox o
在我们移动8球之后，两个相邻交换共享一个球的所有组合都可以通过非相邻交换来产生，所以我们不得不一次考虑更less的复杂性。
按此优先顺序排列所有剩余的移动：
– 在外面的两个相邻球之间的交换是“价值4”（如果它是我们的最后一个）
– 两个相邻的球（一个在外面）之间的交换是“价值2”（如果它是我们的最后一个）
– 外面两个球之间的交换是“价值2”
– 两个球之间的交换，一个在外面，是“价值1”
并从上到下执行它们。
所以我们移动顶部的o，左边的（4），右边的（2）中的o，（2）中的左下angular的o，然后将x顶部与中间的（2）中的o交换， 。 我们最终做了2-2-1系列的五次交换，所以有三步棋。
oxoxo x 8 xx ooo xx o
（值得注意的是，如果我们瞄准angular落里的条纹，那么这个解决scheme的速度就会一样快）。
xxoox o 8 ox oxo xo x
我认为这是不可能的，需要4回合，但我还没有certificate自己呢。
另一个实例：
这有一个+1的平价，所以我们的目标是在angular落里的条纹：
8 ooox ooox oxx xx x
交换8球与中心x（1-）
xooox ooox o 8 x xx x
交换两个相邻的外部，4点（1-1）
xooox ooox x 8 x ox x
将相邻边缘交换到中心，2点（1-2-）
xooox ooxo x 8 x ox x
边对边交换，2点（1-2-1-）
xoxox ooxo x 8 x oo x
3招。
编辑：这个作品相当不错，在开幕post中的例子，解决它在两个步骤：
这有一个+1的平价，所以我们的目标是在angular落里的条纹：
xxoox ooxo oo 8 xx x
交换8边x边，然后o中心（解决两个边）（2-）
xxoox ooxo o 8 x xo x
交换邻近的o和x在左上和左下（解决四个边缘）（2-2-）
xoxox ooxo x 8 x oo x
2招。
你有两个八个球，骗子。
在给定的例子中，解决scheme需要2个步骤：
2-5，3-8
3-4，11-12
通过为dynamic编程 （DP）configuration问题，可以find最佳解决scheme。 由于这个问题是多阶段的，固定成本，没有不确定性，所以存在一个最优解决问题的DPmatrix。
要创buildmatrix：请注意，考虑到对称性，8球可以在9个位置之一。 固体可以按约（14选7）/ 2 = 1716不同的方式排列。 这意味着机架configuration的总数大约是1716 * 9 = 15,444。 因此，你有15,444个不同的可能状态。 计算从这些状态到其他任何状态的成本。 这产生了15444 * 15444个单元的matrix，或约十亿分之十亿的单元。 识别所有的最终状态单元。 为了解决matrix问题，您可以从开始状态向前search，直到您达到结束状态（或者直到您达到的成本总额大于您当前的最低成本）。 通过这样做，你将可以find所有成本最低的path。
请注意，上述解决scheme有些天真，可以通过各种方式进行优化，以生成更小的matrix。 例如，您可以使用旋转对称来减less单元格数量，并将成本为1（用于旋转机架）添加到正确的path，除了将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.
有15!/(7!7!1!)=51480可能的位置。 其中4个是最终的：球8和9可以交换，条纹/固体可以颠倒。 我们会说这些位置在距离0。
对于这四个仓位中的每一个，都会产生所有可能的移动（1个掉期或2个相邻掉期）。 对于这些移动所产生的以前没有看到的每个位置，请记住使用哪个移动来生成它，并将这些位置的距离设置为1.然后对距离为1的每个位置执行相同的操作，并将新位置的距离设为2。这样做直到没有更多的新职位。
正如@DPenner所指出的那样，这可以利用这样的事实：旋转总是可以被相邻的移动所取代。
由于掉期是他们自己的逆转，所以从A到B的转移也是将B转回到A的转移。
所以，最后你会得到所有职位的清单，而对于每一个不是最终职位的职位，这个举动都会使得职位更接近最终职位。
你会发现有232个职位需要至less4个步骤。 （编辑：我的邻接表包含一个错误较早。）例如：
6-9,14-15 2-12 2-5,4-7 1-2 xxxxo xxxx 8 xoxxx xox => xoo => xoo => o 8 o => o 8 o oooxooxxooxxxoxxxoxx o 8 ooxo 8 oxooxoxooxoxooxoxo
没有初始职位需要超过4步。
编辑：交换8球的战略是不是最佳的。 例如：
5-11 12-13,14-15 4-7,6-10 xxxx oooooooo oxo => o 8 o => o 8 o => x 8 x xoxxxoxxxoxxooxo 8 xoxoxxoxoxoxoxxoxox
但我们可以做得更好：
3-11 1-2,3-5 xxo ooo 8 xx oxo => oxo => o 8 o xoxxxoxxxoxx 8 xoxooxoxooxoxo
问题在于x是angular落里错误的一种，所以我们失去了一个动作。
相反，策略应该是寻找一个不合适的球，但不能与邻近的球交换，因为它们是相同的，或者它们已经在位。 angular落应该是首选，因为他们有相邻的掉期选项最less。 应该用正确types的球交换位置。 如果第一个球的最后位置的球是错误的，那么应select错误位置的相邻球。 这样，随后的相邻交换将把这些球放在正确的最终位置。
在上面的（反击）例子中，8球需要很长的交换才能到达最后的位置。 然而，＃5中的x是错误的types，所以相反，我们与第二行中的第二个相邻的o交换。
先前的4个动作的例子解决如下：
11-2 12-5 13-3 9-10 xxxxx xxoxoxoooo xox => xox => x 8 x => x 8 x => x 8 x oooxoooxoooxoooxooxo o 8 ooxx 8 ooxxoooxxoxoxxoxox
在第一步，我们select在左下angular的o。 第一个x在第二个位置。 然后我们在＃12挑8，我们可以带回家＃5。 下排中间的o是下一个。 我们用＃3下一个错误放置的x交换它。 最后，我们交换＃9和＃10来获得最终的机架。 path与以前不同，但我们仍然做了4步。
编辑：还有一点：在执行相邻掉期时，应该优先考虑那些不会以两个球最终位置结束的人。 原因是这意味着至less需要两个动作，所以最好先尽快动一下。
例如，问题中的机架可以通过两个步骤解决：（2-4），（5,6）和（3-6），（12-13）。 8号球首先被移动到了最后的位置，尽pipe被交换的白球尚未进入最后的位置。 如果两轮交换（2-4），（12-13）先完成，则仍然需要两次移动才能到达最后一个机架，总共得到次优3次。
Salut，首先我必须说这是一个非常有趣和有趣的问题，而且我没有想到什么时候打架，尽pipe总共有15个球，一些额外的移动并不重要。
从racking的描述和形象，我们得到以下规则 ：
- angular落总是相同的types
- 每一边的中间总是和angular落一样的types
- 每一组接触angular的两个球总是相同的types（和angular落相反的types）
- 里面的三angular形总是有8个球，一个条纹和一个固体（而8球在上面）
- 在侧面，彼此靠近的球总是交替的types
正如Lemma 1 @DPenner所说，旋转是不必要的，因为它们可以用交换来代替，只要成本是相同的。 如果你是一个拉比克迷，并select使用它们，你只需要一个。
不能less于4次掉期解决！ （ 总是 ）
您的示例图像最好是certificate这一点，无论您如何计算，您需要从其位置移出6个颜色的球，而8ball =>这是3½交换，因为交换需要2个球，让我们轮换到4个交换。
为什么是这样？
因为它不符合所有规则：
-
[5,1,4][2,6][11,13][10,12]不能靠近对方（rest5） -
8ball在一边而不在中间的三angular形（中断4） -
[5,4][6,12][13,9]不是全部相同的types（中断3），而在[1,5,4]的情况下，该集合不与angular落相对（再次中断3 ） -
[2]和[11]与angular落不同（中断2）
algorithm
第一步：修复8ball
把8球换成它的位置。 无论如何，它将需要在那里。
这是旋转的唯一机会（如果8球在三angular形内部开始，但位置不正确）
在红色的位置Count相同types的球 。
最高数量的球停留，剩下的点必须被换出。
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 }
开始交换：
- 做angular落（select一个需要改变的球，在angular落find一个相反的球）
- 做中间球（select一个需要改变的球，并在中间find一个相反的球）
- 如果angular落和middles完成，最后一个交换是在三angular形内
演示你的例子：
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.
如果随机select将select固体停留：
Pick 6, swap with corners(10) #move2 Pick 13, swap with corners(1) #move3 Pick 9, swap with corners(14) #move4 Done.
DEMO2：
用7换了3，用15号球代替了“8号白球” 
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：你也可能喜欢algorithm变化＃2来counts灰色的位置，但是我发现使用红色斑点的实际场景更容易。
这一直是一个具有挑战性，令人沮丧和有趣的问题。 我的猜想是，以下是一个最佳的解决scheme：
- 根据Patashu的奇偶校验方法select条纹还是实体
- 没有旋转
- 每一次测量，除了一个+3的移动可以把8球放在中心以外，其他的得分最高
- 如果配合，select不重要？ 编辑：请参阅底部的注释。 关系是困难的。
（我根据正确位置的球数差异进行得分动作。）
以下是两个示例机架：
x 8 xxoo ooxoox ooxxoxxx 8 oooxoxxox
如果我们从左到右，从上到下编号为1到15，第一个机架解决为（2-4 / 3-5）（5-11）（10-13），第二个机架解决为（4 -8 / 11-12）（5-10）（1-5）。
我最近的一个certificate的尝试有一部分失败，只有11个不同的机架对称（上面显示的两个是失败的变体）。 这里有两个我在我的尝试中发现的引物，希望能帮助别人certificate。
引理1：旋转是不必要的
请注意，如果我们需要在解决scheme中的某个点进行轮换，则何时（旋转不会改变任何可用的交换）无关紧要。 此外，我们只需要最多一次旋转，因为2个顺时针旋转= 1个逆时针旋转，反之亦然。
所以，如果需要的话，让我们select旋转我们的最后一步。 在这一点上，由于外部的旋转对称，外部必须是正确的。 所以八球将在三个中央球之一。 如果它在正确的位置，我们不需要旋转。 否则，我们可以使用它，但注意交换也将完成机架。 因此在最佳解决scheme中是不必要的。
引理2：贪婪是最好的，如果它解决了在3下移动机架
让策略A是贪婪的解决scheme，策略B是任何试图更快的非贪婪解决scheme。 B必须至less做出一次非贪婪的举动。 必要的话，这不可能是最后一步。 因此，如果A轮n次完成一个机架， B必须在n-2或更早的时候进行非贪婪的移动。 这意味着如果A在2圈或更less的时间内解决了机架，这是最佳的。
编辑：那么，我刚刚运行我的程序testingalgorithm，发现它甚至不一致。 事实上，这种关系似乎很难打破。 考虑下面的机架：
x oo xox x 8 ox xooxo
我的algorithm将执行以下移动序列之一：（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） （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）。 前两个解决scheme在最佳的2个时间度量中，但其他解决scheme在3个时间度量中。 问题在于（14-15）和（9-10）开关在第二回合中毁了一个可能的+4移动。 对这种算法的修改可能需要先行先行，然后很快就会变得复杂。 我开始认为没有“简单”的解决scheme，而@JeffreySax的解决scheme是要走的路。 另外请注意，这个机架也击败了贪婪的解决scheme。 贪婪的解决scheme可以做（13-14 / 10-15）（5-8）（7-8）或（13-14 / 10-15）（7-8）（5-8）。
