Одинокий Пег
Peg Solitaire , Solo Noble , Solo Goli , Marble Solitaire или просто Solitaire — настольная игра для одного игрока, предполагающая перемещение колышков по доске с дырочками. В некоторых наборах используются шарики на доске с углублениями. Эта игра известна как пасьянс в Великобритании и как пасьянс с колышками в США, где «пасьянс» теперь является общим названием терпения .
Первые свидетельства игры можно отнести ко двору Людовика XIV и конкретной дате 1697 года, с гравюрой, сделанной десятью годами позже Клодом Огюстом Береем с изображением Анны де Роан-Шабо , принцессы Субиз, с загадкой, сделанной десятью годами позже. ее сторона. Выпуск французского литературного журнала Mercure galant за август 1697 года содержит описание доски, правил и примеры задач. Это первая известная ссылка на игру в печати.
В стандартной игре колышками заполняется вся доска, за исключением центрального отверстия. Цель состоит в том, чтобы, делая правильные ходы, очистить всю доску, за исключением единственного колышка в центральном отверстии.
Доска
[ редактировать ]
Есть две традиционные доски («.» в качестве начального колышка, «о» в качестве начального отверстия):
| Английский | Европейский |
|---|---|
· · ·
· · ·
· · · · · · ·
· · · o · · ·
· · · · · · ·
· · ·
· · ·
|
· · ·
· · · · ·
· · · · · · ·
· · · o · · ·
· · · · · · ·
· · · · ·
· · ·
|
Играть
[ редактировать ]
Правильный ход — перепрыгнуть колышек ортогонально через соседний колышек в лунку на две позиции дальше, а затем убрать перескочивший колышек.
На следующих диаграммах · указывает на колышек в дырке, * выделенный жирным шрифтом указывает на колышек, который необходимо переместить, а o указывает на пустое отверстие. Синий ¤ — это отверстие, из которого переместился текущий колышек; красный * это конечное положение этого колышка, красный o это отверстие в колышке, которое было прыгнуто и удалено.
Таким образом, допустимыми ходами в каждом из четырех ортогональных направлений являются:
* · o → ¤ o * Jump to right
o · * → * o ¤ Jump to left
* ¤ · → o Jump down o *
o * · → o Jump up * ¤
На английской доске первые три хода могут быть такими:
· · · · · · · · · · · ·
· * · · ¤ · · o · · * ·
· · · · · · · · · · o · · · · ¤ o * · · · · o o o · · ·
· · · o · · · · · · * · · · · · · · · · · · · · ¤ · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
Стратегия
[ редактировать ]Существует множество различных решений стандартной задачи, и для их описания используется одна система обозначений, где отверстиям присваиваются буквы (хотя можно использовать и цифры):
English European
a b c a b c
d e f y d e f z
g h i j k l m g h i j k l m
n o p x P O N n o p x P O N
M L K J I H G M L K J I H G
F E D Z F E D Y
C B A C B A
Это обозначение зеркального отображения используется, среди прочего, поскольку на европейской доске один набор альтернативных игр должен начинаться с лунки в некоторой позиции и заканчиваться единственной колышкой в ее зеркальной позиции. На английской доске эквивалентные альтернативные игры должны начинаться с лунки и заканчиваться колышком в той же позиции.
Не существует решения для европейской доски с начальной дыркой, расположенной в центре, если разрешены только ортогональные ходы. Это легко увидеть на примере аргумента Ганса Зантемы . Разделите позиции доски на позиции A, B и C следующим образом:
A B C
A B C A B
A B C A B C A
B C A B C A B
C A B C A B C
B C A B C
A B C
Первоначально, когда свободна только центральная позиция, количество закрытых позиций А равно 12, количество закрытых позиций B — 12, а также количество закрытых позиций C — 12. После каждого хода количество закрытых позиций A увеличивается или уменьшается на один и тот же для количества покрываемых позиций B и количества покрываемых позиций C. Следовательно, после четного числа ходов все эти три числа будут четными, а после нечетного числа ходов все эти три числа будут нечетными. Следовательно, конечная позиция только с одним колышком не может быть достигнута, поскольку для этого потребуется, чтобы одно из этих чисел было единицей (положение привязки, одно - нечетное), а два других числа были нулевыми, следовательно, четными.
Однако существует несколько других конфигураций, в которых одно начальное отверстие можно свести к одному колышку.
Тактика, которую можно использовать, состоит в том, чтобы разделить доску на пакеты по три и полностью очистить (удалить) их, используя один дополнительный колышек, катализатор, который выскакивает , а затем снова возвращается . В приведенном ниже примере * — это катализатор.:
* · o ¤ 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/MK,gM,hL,pF,MK,Fp/pd b: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 b: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» была введена как A112737 в OEIS . Обратите внимание, что общее количество достижимых позиций на доске (сумма последовательности) составляет 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 o · ·
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 · · o · ·
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 · · · o · · ·
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]
Варианты плат
[ редактировать ]Пасьянс «Колышек» разыгрывался на досках других размеров, хотя две, приведенные выше, являются наиболее популярными. В нее также играли на треугольной доске, где разрешены прыжки во всех трех направлениях. Пока вариант имеет правильную «паритетность» и достаточно велик, он, вероятно, будет разрешим.
(1) французский (европейский) стиль, 37 лунок, 17 век;
(2) Й. К. Виглеб, 1779 г., Германия, 45 лунок;
(3) Асимметричная схема 3-3-2-2, описанная Джорджем Беллом, 20 век; [10]
(4) английский стиль (стандарт), 33 лунки;
(5) Алмаз, 41 отверстие;
(6) Треугольный, 15 отверстий.
Серый = дыра для выжившего.
Распространенный треугольный вариант имеет пять колышков на каждой стороне. Решение, при котором последний колышек достигает исходного пустого отверстия, невозможно для отверстия в одном из трех центральных положений. Пустое угловое отверстие можно решить за десять ходов, а пустое среднее отверстие — за девять (Bell 2008):
| Кратчайшее решение треугольного варианта |
|---|
Видеоигра
[ редактировать ]26 июня 1992 года для Game Boy была выпущена видеоигра, основанная на пасьянсе. Игра под простым названием Solitaire была разработана Hect. В Северной Америке DTMC выпустила игру под названием Lazlos' Leap .
В популярной культуре
[ редактировать ]Cracker Barrel предлагает игру за каждым столом в своем месте. Представленная доска треугольной формы с 15 отверстиями.
В «Ковбой Бибоп: Фильм» главный антагонист Винсент Воладжу большую часть свободного времени проводит, раскладывая пасьянс. Вектор для его запланированной биотеррористической атаки тип нанобота хранится в шариках-пасьянсах.
Ссылки
[ редактировать ]- ^ Берлекамп, ER ; Конвей, Дж. Х. ; Гай, РК (2001) [1981], Пути победы для ваших математических игр (2-е изд.), AK Peters/CRC Press, ISBN 978-1568811307 , OCLC 316054929
- ↑ Перейти обратно: Перейти обратно: а б Киёми, М.; Мацуи, Т. (2001), «Алгоритмы на основе целочисленного программирования для решения задач пасьянса с привязками», Proc. 2-й Межд. Конф. Компьютеры и игры (CG 2000): Алгоритмы на основе целочисленного программирования для решения задач пасьянса с привязками , Конспекты лекций по информатике, том. 2063, стр. 229–240, CiteSeerX 10.1.1.65.6244 , doi : 10.1007/3-540-45579-5_15 , ISBN 978-3-540-43080-3
- ^ Уэхара, Р.; Ивата, С. (1990). «Обобщенный Hi-Q является NP-полным». Пер. IEICE . 73 : 270–273.
- ^ Авис, Д .; Деза, А. (2001), «О конусе пасьянса и его связи с многотоварными потоками», Mathematical Programming , 90 (1): 27–57, doi : 10.1007/PL00011419 , S2CID 7852133
- ^ Эйхлер; Хантер; Людвиг (1999), октябрь 07/1999, портит спорт, решение пасьянса с помощью компьютера (на немецком языке), том. 7, с. 218
- ^ «Математика и мозгвита» , Заметки по математике , 28 августа 2012 г. , дата обращения 6 сентября 2018 г.
- ↑ Доказательство Бизли см. в «Пути к победе» , том № 4 (второе издание).
- ^ "солборд" . гитхаб . 31 августа 2020 г. Проверено 31 августа 2020 г.
Реализация расчета перебора пасьянса «Колышек»
- ^ Брассин, Мишель (декабрь 1981 г.), «Откройте для себя... пасьянс», Игры и стратегии (на французском языке)
- ^ См . «Обобщенные перекрестные доски» на странице «Пасьянс «Колышек» Джорджа».
Дальнейшее чтение
[ редактировать ]- Бизли, Джон Д. (1985), Все плюсы и минусы пасьянса «Колышек» , Oxford University Press , ISBN 978-0198532033
- Белл, Дж.И. (2008), «Решение пасьянса с треугольными колышками», Журнал целочисленных последовательностей , 11 : Статья 08.4.8, arXiv : math.CO/0703865 , Bibcode : 2007math......3865B .
- Брюйн, Н.Г. де (1972), «Пасьянс и его связь с конечным полем» (PDF) , Journal of Recreational Mathematics , 5 : 133–137, заархивировано (PDF) из оригинала 9 октября 2022 г.
- Кросс, округ Колумбия (1968), «Квадратный пасьянс и вариации», Журнал развлекательной математики , 1 : 121–123.
- Гарднер, М. , «Математические игры», Scientific American 206 (6): 156–166, июнь 1962 г.; 214 (2): 112–113, февраль 1966 г.; 214 (5): 127, май 1966 г.
- Джефферсон, Крис; и др. (Октябрь 2006 г.), «Моделирование и решение английского пасьянса с колышками», Computers & Operations Research , 33 (10): 2935–2959, CiteSeerX 10.1.1.5.7805 , doi : 10.1016/j.cor.2005.01.018
Внешние ссылки
[ редактировать ]
- Богомольный, Александр, «Пасьянс-колышек и теория групп» , Интерактивные математические сборники и головоломки , получено 7 сентября 2018 г.
- Белые пиксели (24 октября 2017 г.), Пасьянс «Колышек»: легко запоминающееся симметричное решение (видео), Youtube, заархивировано из оригинала 11 декабря 2021 г.
- Разыграйте несколько головоломок пасьянса «Колышек» на sologoli.com