Как эффективно набирать бильярд для игры с 8 мячами?

Ответ 1

ВНИМАНИЕ! Этот ответ был написан до требования к ротации. Соблюдайте свою осторожность:)

Вот мой первоначальный взгляд на проблему.

Первое, что нужно сделать, это вычислить четность внешнего - +1, если он будет соответствовать "полосам в углах", -1, если он будет соответствовать "твердым телам в углах", +0, если это 8 мячей. Это дает нам диапазон от +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, все комбинации двух смежных свопов, разделяющих шарик, могут быть произведены не соседним свопом одинаково, поэтому мы должны учитывать гораздо меньшую сложность сразу.

Закажите все остальные ходы по этому приоритету:

-A своп между двумя соседними шарами снаружи "стоит 4" (2, если он наш последний)

-A своп между двумя соседними шарами, один снаружи, равен "2" (1, если он наш последний)

-A своп между двумя шарами снаружи - "стоит 2"

-A своп между двумя шарами, один снаружи, "стоит 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 хода.

EDIT: Это хорошо работает для примера в открытии сообщения, решая его в два хода:

Это имеет четность +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 хода:

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.

Ответ 3

Есть 15!/(7!7!1!)=51480 возможные позиции. Из них 4 являются окончательными: шары 8 и 9 можно обменивать, а полосы/твердые тела могут быть отменены. Мы скажем, что эти позиции находятся на расстоянии 0.

Для каждой из этих 4 позиций генерируйте все возможные ходы (1 своп или 2 смежных свопа). Для каждой позиции, созданной этими движениями, которые ранее не были замечены, помните, какой шаг использовался для ее создания, и дайте этим позициям расстояние 1. Затем сделайте то же самое для каждой позиции на расстоянии 1 и дайте новым позициям расстояние 2. Держите делая это до тех пор, пока не появятся новые позиции.

Это позволяет использовать тот факт, что, как указывал @DPenner, вращения всегда можно заменить смежным перемещением.

Так как свопы являются их собственными обратными, переход из положения A в B также является перемещением, которое займет позицию B назад к A.

Итак, вы получаете список всех позиций и для каждой позиции, которая не является конечной позицией, шаг, который с уверенностью приблизит его к конечной позиции.

Вы обнаружите, что есть 232 позиции, которые занимают не менее 4 ходов. (EDIT: моя таблица смежности содержала ошибку раньше.) Например:

      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 ходов.

EDIT: стратегия замены в 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 шара требуется длинный своп, чтобы добраться до его конечной позиции. Однако x в # 5 является неправильным видом, поэтому вместо этого мы обмениваемся смежным 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 находится в положении два. Затем мы выбираем 8 в # 12, и мы можем доставить домой до №5. Затем в середине нижней строки. Мы обмениваем его со следующим неправильно размещенным x на # 3. Наконец, мы заменили # 9 и # 10, чтобы получить финальную стойку. Путь отличается от предыдущего, но мы все равно сделали это за 4 хода.

EDIT: Еще один момент: при выполнении смежных свопов предпочтение следует отдавать тем, у кого не заканчиваются оба шара в их конечном положении. Причина в том, что это означает, что во всех требуется как минимум два хода, поэтому лучше всего сделать первый шаг как можно скорее.

Например, стойка в вопросе может быть решена двумя ходами: (2-4), (5,6) и (3-6), (12-13). Сначала 8 мячей были перенесли в свое окончательное положение, хотя белый шар, с которым он был заменен, еще не находится в своем последнем положении. Если сначала выполнялись два обменных интервала (2-4), (12-13), вам все равно нужно два хода, чтобы добраться до финальной стойки, взяв субоптимальные 3 ходовых значения.

Ответ 4

Это был сложный, глубоко разочаровывающий и забавный вопрос сразу. Моя гипотеза такова, что следующее оптимальное решение:

• Выберите, будут ли полосы или твердые тела в углах основаны на методе паритета Паташу.
• Без поворотов
• В каждом временном измерении сделайте ход, который будет самым высоким, за исключением случаев, когда движение +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).

Ответ 5

Салют, сначала я должен сказать, что это была очень интересная и интересная проблема, и кое-что, о чем я не думал, когда ломался, хотя на 15 общих шарах некоторые дополнительные шаги не были бы важны.

Из описания и изображения стеллажа мы получаем следующие правила:

• углы всегда одного типа.
• Середина каждой стороны всегда та же, что и угол
• каждый набор из 2 шаров, касающихся углов, всегда имеет тот же тип (и противоположный тип как угол).
• внутри треугольника всегда есть 8ball, полоса и твердое тело (и 8ball сверху)
• по бокам, шары рядом друг с другом всегда будут чередовать тип

Поскольку @DPenner указано в Lemma 1, вращения не нужны, поскольку они могут быть заменены свопом при условии, что стоимость будет одинаковой. Если вы поклонник Rubick и решили использовать их, вам понадобится только один.

Невозможно решить менее 4 свопов! (всегда)

Пример вашего примера лучше всего доказать это, так как вы считаете, что вам нужно выбить 6 цветных шариков со своих позиций и 8ball = > , что 3 & frac12; свопы и потому, что своп нуждается в 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)

Алгоритм

1-й шаг: исправьте 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.

demo2:

изменил 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 серые позиции, но мне было легче использовать сценарий реального времени для использования красных пятен.