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

У тебя 2 восьмерки, мошенник.

В данном примере решение занимает 2 хода:

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

Оптимальное решение лучше всего найти, настроив задачу для динамического программирования (DP). Поскольку задача является многоступенчатой ​​с фиксированными затратами и отсутствием неопределенностей, будет существовать матрица DP, которая оптимально решает проблему.

Чтобы создать матрицу: обратите внимание, что с учетом симметрии восьмерка может находиться в одном из 9 положений. Твердые тела можно расположить примерно (14 выберите 7)/2=1716 различных способов. Это означает, что общее количество конфигураций стоек составляет около 1716 * 9 = 15 444. Таким образом, у вас есть 15 444 различных возможных состояния. Подсчитайте стоимость перехода из любого из этих состояний в любое другое. В результате получается матрица из 15 444 * 15 444 ячеек, или около четверти миллиарда ячеек. Определите все ячейки конечного состояния. Чтобы решить матрицу, вы выполняете поиск в ширину от начального состояния до конечного состояния (или до тех пор, пока не достигнете общей стоимости, превышающей текущую минимальную стоимость). Сделав это, вы наверняка найдете все пути с наименьшими затратами.

Обратите внимание, что приведенное выше решение несколько наивно и может быть оптимизировано различными способами, чтобы получить меньшую матрицу. Например, вы можете использовать вращательную симметрию, чтобы уменьшить количество ячеек и добавить стоимость 1 (за вращение стойки) к путям, которые являются правильными, за исключением того, что восьмерка находится в одном из нижних центральных положений.

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.

Для каждой из этих 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 ходов.

РЕДАКТИРОВАТЬ: Стратегия замены восьмерки сначала не оптимальна. Например:

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

РЕДАКТИРОВАТЬ: Еще один момент: при выполнении смежных обменов предпочтение следует отдавать тем, которые не заканчиваются с обоими шарами в их конечном положении. Причина в том, что это означает, что всего требуется как минимум два хода, поэтому лучше сделать первый ход как можно раньше.

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

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

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

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

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

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

Ваше примерное изображение лучше всего доказывает это, в любом случае вам нужно сместить 6 шаров color со своих позиций, а 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)

Алгоритм

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

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

• Выберите, будут ли полосы или сплошные цвета находиться в углах на основе метода четности Паташу.
• Нет поворотов
• При каждом измерении времени делайте ход, который принесет наибольшее количество очков, за исключением случаев, когда ход +3 может поставить восьмерку в центр.
• В случае ничьей выбор не имеет значения? Изменить: см. примечание внизу. С галстуками сложно.

(Я оцениваю ходы в соответствии с чистой разницей в количестве мячей в правильных позициях.)

Вот две стойки для примера:

    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 вращение против часовой стрелки и наоборот.

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

Лемма 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).