Пасьянс колышек - Peg solitaire

Принцесса Субиза играть пасьянс, 1697

Пасьянс с колышками (или Solo Noble ) - это настольная игра для одного игрока, включающая перемещение колышков на доске с отверстиями. В некоторых наборах используются шарики в доске с углублениями. Игра известна в Соединенном Королевстве просто как Solitaire, а карточные игры называются « Терпение» . Его также называют Brainvita (в основном в Индии , где под этим названием продаются коммерческие наборы).

Первые свидетельства существования игры можно проследить до двора Людовика XIV и точную дату - 1697 год, с гравюрой, сделанной десятью годами позже Клодом Огюстом Берем Анны де Роган-Шабо , принцессы Субизы, с головоломкой автора ее сторона. В августовском выпуске 1687 года французского литературного журнала Mercure galant содержится описание доски, правила и примеры задач. Это первое известное упоминание об игре в печати.

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

Доска

Английский пасьянс
Европейская доска для пасьянсов

Есть две традиционные доски ('.' В качестве начального штифта, 'o' как начальное отверстие):

английский Европейский 
     · · ·
     · · ·
 · · · · · · · 
 · · · o · · · 
 · · · · · · · 
     · · ·
     · · ·

     · · ·
   · · · · ·
 · · · · · · · 
 · · · o · · · 
 · · · · · · · 
   · · · · ·
     · · ·

Играть

Играть в пасьянс Колышка
Мужчина играет в пасьянс с треугольными колышками в ресторане Cracker Barrel .

Допустимым ходом является перепрыгивание колышка перпендикулярно соседнему колышку в отверстие на расстоянии двух позиций, а затем удаление колышка, сошедшего с места.

На следующих схемах значок ·указывает на колышек в отверстии, *жирный шрифт указывает на колышек, который необходимо переместить, и 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

Первоначально, когда свободна только центральная позиция, количество покрытых позиций A равно 12, количество покрытых позиций B равно 12, а также количество покрытых позиций C равно 12. После каждого хода количество покрытых позиций A увеличивается или уменьшается на один, и то же самое для количества покрытых позиций B и количества покрытых позиций C. Следовательно, после четного числа ходов все эти три числа будут четными, а после нечетного числа ходов все эти три числа будут нечетными. Следовательно, конечная позиция только с одним колышком не может быть достигнута, так как для этого потребуется, чтобы одно из этих чисел было равно единице (положение колышка, одно нечетное), в то время как два других числа равны нулю, следовательно, четным.

Однако существует несколько других конфигураций, в которых одно начальное отверстие может быть уменьшено до одного штифта.

Тактика, которую можно использовать, состоит в том, чтобы разделить доску на пакеты по три и полностью очистить (удалить) их, используя один дополнительный колышек, катализатор, который выскакивает, а затем снова прыгает обратно . В приведенном ниже примере * обозначает катализатор: 

* · o      ¤ o *      o * ·      * o ¤
  ·     →    ·    →     o     →    o
  ·          ·          ¤          o

Эта техника может использоваться с линией 3, блоком 2 · 3 и L-образной формой с 6 штифтами с основанием длиной 3 и стойкой длиной 4.

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

Исследования пасьянса колышек

Известен тщательный анализ игры. Этот анализ ввел понятие, называемое функцией пагоды, которое является сильным инструментом для демонстрации невозможности данной обобщенной проблемы с привязкой к пасьянсу.

Решение для поиска функции пагоды, которая демонстрирует невозможность данной задачи, формулируется как задача линейного программирования и разрешима за полиномиальное время.

В статье 1990 г. были рассмотрены обобщенные задачи Hi-Q, которые эквивалентны задачам с колышками, и показана их NP-полнота .

В статье 1996 года проблема пасьянса с привязкой сформулирована как задача комбинаторной оптимизации и обсуждаются свойства допустимой области, называемой «конусом пасьянса».

В 1999 году пасьянс «колышек» был полностью решен на компьютере путем тщательного перебора всех возможных вариантов. Это было достигнуто за счет использования симметрии, эффективного хранения комбинаций плат и хеширования.

В 2001 году был разработан эффективный метод решения задач пасьянса с колышками.

Неопубликованное исследование 1989 года, посвященное обобщенной версии игры на английской доске, показало, что каждая возможная задача в обобщенной игре имеет 2 9 возможных различных решений, исключая симметрии, поскольку английская доска содержит 9 различных подквадратов 3 × 3. Одним из следствий этого анализа является определение нижней границы размера возможных проблем «перевернутого положения», в которых первоначально занятые ячейки остаются пустыми, и наоборот. Любое решение такой задачи должно содержать минимум 11 ходов, независимо от точных деталей задачи.

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

Решения английской игры

Самое короткое решение стандартной английской игры включает 18 ходов, считая несколько прыжков за один ход:

Это решение было найдено в 1912 году Эрнестом Бергхолтом, а в 1964 году Джон Бизли доказал, что оно является самым коротким.

Это решение также можно увидеть на странице, где также представлена ​​нотация Вольстенхольма , которая предназначена для облегчения запоминания решения.

Другие решения включают следующий список. В них используются обозначения

  • Список стартовых лунок
  • Двоеточие
  • Список конечных целевых колышков
  • Знак равенства
  • Исходный колышек и отверстие назначения (перепрыгнутые колышки оставляются читателю в качестве упражнения)
  • , или / ( косая черта используется для разделения "кусков", например, для удаления шести частей )
 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

Атака грубой силы на стандартный английский пасьянс

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

Ниже приводится таблица по числу ( P жно B Орд P ositions) возможных положений доски после того, как п прыжков, а также возможность того же пешки переехал сделать еще прыжок ( Н о F urther J umps).

ПРИМЕЧАНИЕ: Если одну позицию платы можно повернуть и / или перевернуть в другую позицию, позиции платы считаются идентичными.

Поскольку может быть только 31 прыжок, современные компьютеры могут легко изучить все игровые позиции за разумное время.

Вышеупомянутая последовательность «PBP» была введена в OEIS как A112737 . Обратите внимание, что общее количество доступных позиций платы (сумма последовательности) составляет 23 475 688, в то время как общее количество возможных позиций платы составляет 8 589 934 590 (33 бит-1) (2 ^ 33). Таким образом, только 2,2% всех возможных позиций платы могут быть достигнуто, начиная с свободного центра.

Также возможно сгенерировать все позиции доски. Приведенные ниже результаты были получены с использованием набора инструментов mcrl2 (см. Пример peg_solitaire в распространении).

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

Решения европейской игры

Есть 3 исходные неконгруэнтные позиции, у которых есть решения. Эти:

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) JC Wiegleb, 1779, Германия, 45 лунок;
(3) Асимметричный 3-3-2-2, описанный Джорджем Беллом, 20 век;
(4) английский стиль (стандарт), 33 лунки;
(5) ромб, 41 лунка;
(6) Треугольник, 15 отверстий.
Серый = дыра для выжившего.

Обычный треугольный вариант имеет пять штифтов сбоку. Решение, при котором последний штифт достигает начального пустого отверстия, невозможно для отверстия в одном из трех центральных положений. Пустое угловое отверстие может быть решено за десять ходов, а пустое центральное отверстие - за девять (Bell 2008):

Видео игра

26 июня 1992 года для Game Boy была выпущена видеоигра, основанная на пасьянсе «колышек». Игра, названная просто «Пасьянс», была разработана Hect. В Северной Америке DTMC выпустила игру под названием «Lazlos 'Leap».

использованная литература

дальнейшее чтение

  • Бисли, Джон Д. (1985), Все аспекты пасьянса Peg , 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
  • Кросс, округ Колумбия (1968), «Квадратный пасьянс и вариации», Журнал развлекательной математики , 1 : 121–123
  • Гарднер М. , «Математические игры», Scientific American 206 (6): 156–166, июнь 1962 г .; 214 (2): 112–113, февраль 1966 г .; 214 (5): 127, май 1966 г.
  • Джефферсон, Крис; и другие. (Октябрь 2006 г.), «Моделирование и решение английского пасьянса с привязкой», Компьютеры и исследования операций , 33 (10): 2935–2959, CiteSeerX  10.1.1.5.7805 , doi : 10.1016 / j.cor.2005.01.018

внешние ссылки

  • Богомольный, Александр, "Peg Solitaire and Group Theory" , Interactive Mathematics Miscellany and Puzzles , данные получены 7 сентября 2018 г.
  • Белые пиксели (24 октября 2017 г.), Peg Solitaire: Легко запоминающееся симметричное решение (видео), Youtube
  • Играйте в несколько версий пасьянса Peg, включая английский, европейский, треугольный, шестиугольный, пропеллерный, минимальный, 4 отверстия, 5 отверстий, легкую вертушку, Banzai7, мегафон, сову, звезду и стрелу на pegsolitaire.org