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

Question

因为8球比赛的台球可以在多种规则下进行,所以我所说的是货架:

即,8球必须位于中心,并且沿着侧面,条纹和固体必须交替.剩下的两个球(条纹和实心)无关紧要.

假设你刚刚完成游戏,收集球,将它们放入机架并继续安排它们开始一个新的.他们现在是随机的.你怎么办？

_{免责声明:油漆艺术如下}

一个简单的方法是按顺序开始,top - > bottom和left - > right.

因此,例如,我们假设1处于正确的位置.5不,我们与它交换2,然后我们交换4与3(或8),但这已经是低效的,因为我们无论是移动4到中心或8在4的位置-即不是它必须是在结束.

还有决定我们想要在角落里制作哪种类型的球.你是如何预先决定的？你应该考虑到已有多少球？在我的例子中,如果你想要角落里的灰色,你已经有3个(球1,10,14).如果你想要角落里的白色,你只有2个(2,11).这有关系吗？

为了形式化,我们可以假设有 二 我们可以做的三项操作:

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

由于我们可以使用双手,让我们假设我们可以并行第一个操作(同时交换两个球),而我们一次只能交换两个不相邻的球.

什么方法最适合这项任务,最大限度地减少时间(以所描述的时间单位)？贪婪是最好的吗？(我想,当我把它们架起来时,我就是这样做的)

编辑:根据现有(或以前的答案) - 您可能会认为角落中的条纹比条纹更多意味着大步更喜欢角落 - 不是说它不是真的,但如果你做出这个假设,请证明它.

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'(如果它是我们的最后一个)

- 外面两个球之间的交换是"值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

交换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招.