Peg Solitaire , Solo Noble , Solo Goli , Marble Solitaire или просто Solitaire — настольная игра для одного игрока, предполагающая перемещение колышков по доске с дырочками. В некоторых наборах используются шарики на доске с углублениями. Эта игра известна как пасьянс в Великобритании и как пасьянс с колышками в США, где «пасьянс» теперь является общим названием терпения .
Первые свидетельства игры можно отнести ко двору Людовика XIV и конкретной дате 1697 года, с гравюрой, сделанной десятью годами позже Клодом Огюстом Береем с изображением Анны де Роан-Шабо , принцессы Субиз, с загадкой, сделанной десятью годами позже. ее сторона. Выпуск французского литературного журнала Mercure galant за август 1697 года содержит описание доски, правил и примеры задач. Это первая известная ссылка на игру в печати.
В стандартной игре колышками заполняется вся доска, за исключением центрального отверстия. Цель состоит в том, чтобы, делая правильные ходы, очистить всю доску, за исключением единственного колышка в центральном отверстии.
Есть две традиционные доски («.» в качестве начального колышка, «о» в качестве начального отверстия):
Допустимый ход — перепрыгнуть колышек ортогонально через соседний колышек в лунку, расположенную на две позиции дальше, а затем убрать перескочивший колышек.
На следующих рисунках ·обозначен колышек в отверстии, *жирным шрифтом обозначен колышек, который нужно переместить, и oуказано пустое отверстие. Синий ¤— это отверстие, из которого переместилась текущая привязка; красный цвет *— это конечное положение этого колышка, красный o— это отверстие в колышке, которое было прыгнуто и удалено.
Таким образом, допустимыми ходами в каждом из четырех ортогональных направлений являются:
* · o → ¤ o * Перейти вправо
o · * → * o ¤ Перейти влево
* ¤ · → o Спрыгнуть вниз o *
o * · → o Перейти вверх * ¤
На английской доске первые три хода могут быть такими:
· · · · · · · · · · · · · · * · · ¤ · · o · · * ·· · · · · · · · · · о · · · · ¤ о * · · · · оо о · · ·· · · o · · · · · · · * · · · · · · · · · · · · ¤ · · ·· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Существует множество различных решений стандартной задачи, и для их описания используется одна система обозначений, где отверстиям присваиваются буквы (хотя можно использовать и цифры):
английский европейский abcabc Defydefzгийклмгийклмnopx PON nopx PONМЛКДЖИХГМЛКДЖИХГ ФЕДЗФЕДИ КБАКБА
Это обозначение зеркального отображения используется, среди прочего, поскольку на европейской доске один набор альтернативных игр должен начинаться с лунки в некоторой позиции и заканчиваться единственной колышкой в ее зеркальной позиции. На английской доске эквивалентные альтернативные игры должны начинаться с лунки и заканчиваться колышком в той же позиции.
Не существует решения для европейской доски с начальной дыркой, расположенной в центре, если разрешены только ортогональные ходы. Это легко увидеть на примере аргумента Ганса Зантемы . Разделите позиции доски на позиции A, B и C следующим образом:
АВС АБКАБАБКАБКАБКАВКАБКАБКАВС БКАВС АВС
Первоначально, когда свободна только центральная позиция, количество закрытых позиций А равно 12, количество закрытых позиций B — 12, а также количество закрытых позиций C — 12. После каждого хода количество закрытых позиций A увеличивается или уменьшается на один и тот же для количества покрываемых позиций B и количества покрываемых позиций C. Следовательно, после четного числа ходов все эти три числа будут четными, а после нечетного числа ходов все эти три числа будут нечетными. Следовательно, конечная позиция только с одним колышком не может быть достигнута, поскольку для этого потребуется, чтобы одно из этих чисел было единицей (положение привязки, одно - нечетное), а два других числа были нулевыми, следовательно, четными.
Однако существует несколько других конфигураций, в которых одно начальное отверстие можно свести к одному колышку.
Тактика, которую можно использовать, состоит в том, чтобы разделить доску на пакеты по три и полностью очистить (удалить) их, используя один дополнительный колышек, катализатор, который выскакивает , а затем снова возвращается . В приведенном ниже примере * — это катализатор.:
* · o ¤ o * o * · * o ¤ · → · → o → o · · ¤ о
Эту технику можно использовать с леской из 3, блоком из 2,3 и L-образной формой с 6 колышками с основанием длиной 3 и стойкой длиной 4.
Другие альтернативные игры включают начало с двумя пустыми лунками и завершение двумя колышками в этих лунках. Также начиная с одного отверстия здесь и заканчивая одним колышком там . На английской доске лунка может быть где угодно, а последняя колышек может оказаться только там, где разрешено количество, кратное трем. Таким образом , дырка в точке a может оставить только один колышек в точках a , p , O или C.
Известен тщательный анализ игры. [1] В этом анализе введено понятие, называемое функцией пагоды , которое является сильным инструментом, позволяющим показать невыполнимость данной обобщенной задачи пасьянса с привязками.
Решение для нахождения функции пагоды, демонстрирующее невыполнимость данной задачи, формулируется как задача линейного программирования и разрешимо за полиномиальное время. [2]
В статье 1990 года были рассмотрены обобщенные задачи Hi-Q, которые эквивалентны задачам пасьянса с привязками, и показана их NP-полнота . [3]
В статье 1996 года задача пасьянса с привязкой была сформулирована как задача комбинаторной оптимизации и обсуждались свойства допустимой области, называемой «конус пасьянса». [4]
В 1999 году пасьянс «Колышек» был полностью решен на компьютере с помощью исчерпывающего перебора всех возможных вариантов. Это было достигнуто за счет использования симметрий, эффективного хранения созвездий досок и хеширования. [5]
В 2001 году был разработан эффективный метод решения задач-пасьянсов. [2]
Неопубликованное исследование 1989 года обобщенной версии игры на английской доске показало, что каждая возможная задача в обобщенной игре имеет 2–9 возможных различных решений, исключая симметрии, поскольку английская доска содержит 9 различных подклеток размером 3×3. Одним из последствий этого анализа является установление нижней границы размера возможных проблем «перевернутой позиции», при которых первоначально занятые ячейки остаются пустыми, и наоборот. Любое решение такой задачи должно содержать минимум 11 ходов, независимо от точных деталей задачи.
С помощью абстрактной алгебры можно доказать , что существует только 5 фиксированных позиций на доске, где игра может успешно закончиться с одним колышком. [6]
Самое короткое решение стандартной английской игры включает 18 ходов, считая несколько прыжков за один ход:
Это решение было найдено в 1912 году Эрнестом Бергхольтом и оказалось кратчайшим из возможных Джоном Бисли в 1964 году. [7]
Это решение также можно увидеть на странице, где также представлена нотация Вольстенхолма, предназначенная для облегчения запоминания решения.
Другие решения включают следующий список. В них используются обозначения
x:x=ex,lj,ck,Pf,DP,GI,JH,mG,GI,ik,gi,LJ,JH,Hl,lj,jh,CK,pF,AC,CK,Mg,gi,ac, ck,kI,dp,pF,FD,DP,Pp,ox x:x=ex,lj,xe/hj,Ki,jh/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK,pF/CK,DF,AC,JL,CK, LJ/PD,GI,mG,JH,GI,DP/Ox j:j=lj,Ik,jl/hj,Ki,jh/mk,Gm,Hl,fP,mk,Pf/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK, pF/CK,DF,AC,JL,CK,LJ/Jj i:i=ki,Jj,ik/lj,Ik,jl/AI,FD,CA,HJ,AI,JH/mk,Hl,Gm,fP,mk,Pf/ai,ca,fd,hj,ai, jh/gi,Mg,Lh,pd,gi,dp/Ki e:e=xe/lj,Ik,jl/ck,ac,df,lj,ck,jl/GI,lH,mG,DP,GI,PD/AI,FD,CA,JH,AI,HJ/pF, MK,gM,JL,MK,Fp/hj,ox,xe d:d=fd,xe,df/lj,ck,ac,Pf,ck,jl/DP,KI,PD/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/МК,gM,hL,пФ,МК,Фп/пд б:b=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, ox/xe/AI/BJ,JH,Hl,lj,jb б:x=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, ox/xe/AI/BJ,JH,HL,lj,ex a:a=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/dp,gi,pd,Mg,Lh,gi/ia a:p=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/dp,gi,pd,Mg,Lh,gi/dp
Единственное место, где может оказаться одиночный колышек, — это центр или середина одного из краев; при последнем прыжке всегда будет возможность выбрать, закончить ли его в центре или на краю.
Ниже приводится таблица количества ( Возможные позиции на доске ) возможных позиций на доске после n прыжков, а также вероятность того , что тот же самый колышек будет перемещен для дальнейшего прыжка ( Нет дальнейших прыжков ). Интересно отметить, что самый короткий путь провалить игру — это шесть ходов, а решение (помимо вращений и отражений) уникально. Пример: 4 → 16; 23 → 9; 14 → 16; 17 → 15; 19 → 17; 31 → 23. (В этом обозначении колышки нумеруются слева направо, начиная с 0, и перемещаясь вниз по каждой строке и в крайнее левое положение после того, как каждая строка отмечена.)
ПРИМЕЧАНИЕ. Если одно положение доски можно повернуть и/или перевернуть в другое положение доски, положения доски считаются идентичными.
Поскольку прыжков может быть только 31, современные компьютеры могут легко изучить все игровые позиции за разумное время. [8]
Вышеупомянутая последовательность «PBP» была введена в OEIS как A112737 . Обратите внимание, что общее количество достижимых позиций на доске (сумма последовательности) составляет 23 475 688, а общее количество возможных позиций на доске составляет 8 589 934 590 (33 бит-1) (2 ^ 33), поэтому только около 2,2% всех возможных позиций на доске могут быть доступны. можно добраться, начиная с пустого центра.
Также возможно генерировать все позиции на доске. Результаты, приведенные ниже, были получены с использованием набора инструментов mCRL2 (см. пример peg_solitaire в раздаче).
В приведенных ниже результатах он сгенерировал все позиции на доске, которых он действительно достиг, начиная с свободного центра и заканчивая центральной лункой.
Имеются 3 исходные несовпадающие позиции, которые имеют решения. [9] Это:
1)
0 1 2 3 4 5 6 0 о · · 1 · · · · · 2 · · · · · · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Возможное решение: [2:2-0:2, 2:0-2:2, 1:4-1:2, 3:4-1:4, 3:2-3:4, 2:3-2: 1, 5:3-3:3, 3:0-3:2, 5:1-3:1, 4:5-4:3, 5:5-5:3, 0:4-2:4, 2:1-4:1, 2:4-4:4, 5:2-5:4, 3:6-3:4, 1:1-1:3, 2:6-2:4, 0: 3-2:3, 3:2-5:2, 3:4-3:2, 6:2-4:2, 3:2-5:2, 4:0-4:2, 4:3- 4:1, 6:4-6:2, 6:2-4:2, 4:1-4:3, 4:3-4:5, 4:6-4:4, 5:4-3: 4, 3:4-1:4, 1:5-1:3, 2:3-0:3, 0:2-0:4]
2)
0 1 2 3 4 5 6 0 · · · 1 · · о · · 2 · · · · · · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Возможное решение: [1:1-1:3, 3:2-1:2, 3:4-3:2, 1:4-3:4, 5:3-3:3, 4:1-4: 3, 2:1-4:1, 2:6-2:4, 4:4-4:2, 3:4-1:4, 3:2-3:4, 5:1-3:1, 4:6-2:6, 3:0-3:2, 4:5-2:5, 0:2-2:2, 2:6-2:4, 6:4-4:4, 3: 4-5:4, 2:3-2:1, 2:0-2:2, 1:4-3:4, 5:5-5:3, 6:3-4:3, 4:3- 4:1, 6:2-4:2, 3:2-5:2, 4:0-4:2, 5:2-3:2, 3:2-1:2, 1:2-1: 4, 0:4-2:4, 3:4-1:4, 1:5-1:3, 0:3-2:3]
и 3)
0 1 2 3 4 5 6 0 · · · 1 · · · · · 2 · · · о · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Возможное решение: [2:1-2:3, 0:2-2:2, 4:1-2:1, 4:3-4:1, 2:3-4:3, 1:4-1: 2, 2:1-2:3, 0:4-0:2, 4:4-4:2, 3:4-1:4, 6:3-4:3, 1:1-1:3, 4:6-4:4, 5:1-3:1, 2:6-2:4, 1:4-1:2, 0:2-2:2, 3:6-3:4, 4: 3-4:1, 6:2-4:2, 2:3-2:1, 4:1-4:3, 5:5-5:3, 2:0-2:2, 2:2- 4:2, 3:4-5:4, 4:3-4:1, 3:0-3:2, 6:4-4:4, 4:0-4:2, 3:2-5: 2, 5:2-5:4, 5:4-3:4, 3:4-1:4, 1:5-1:3]
Пасьянс «Колышек» разыгрывался на досках других размеров, хотя две, приведенные выше, являются наиболее популярными. В нее также играли на треугольной доске, где разрешены прыжки во всех трех направлениях. Пока вариант имеет надлежащую «паритетность» и достаточно велик, он, вероятно, будет разрешим.
Распространенный треугольный вариант имеет пять колышков на каждой стороне. Решение, при котором последний колышек достигает исходного пустого отверстия, невозможно для отверстия в одном из трех центральных положений. Пустое угловое отверстие можно решить за десять ходов, а пустое среднее отверстие — за девять (Bell 2008):
26 июня 1992 года для Game Boy была выпущена видеоигра, основанная на пасьянсе. Игра под простым названием Solitaire была разработана Hect. В Северной Америке DTMC выпустила игру под названием Lazlos' Leap .
Cracker Barrel предлагает игру за каждым столом в своем месте. Представленная доска треугольной формы с 15 отверстиями.
В «Ковбой Бибоп: Фильм» главный антагонист Винсент Воладжу проводит большую часть своего свободного времени, раскладывая пасьянс. Вектор его запланированной биотеррористической атаки, тип нанобота , хранится в шариках-пасьянсах.
Реализация расчета перебора пасьянса «Колышек»
