Пасьянс с колышками (или Solo Noble ) - это настольная игра для одного игрока, включающая перемещение колышков на доске с отверстиями. В некоторых наборах используются шарики в доске с углублениями. Игра известна в Соединенном Королевстве просто как Solitaire, а карточные игры называются « Терпение» . Его также называют Brainvita (в основном в Индии , где под этим названием продаются коммерческие наборы).
Первые свидетельства игры можно проследить до двора Людовика XIV и точную дату - 1697 год, с гравюрой, сделанной десятью годами позже Клодом Огюстом Берем Анны де Роган-Шабо , принцессы Субизы, с загадкой автора ее сторона. В августовском выпуске 1687 года французского литературного журнала Mercure galant содержится описание доски, правила и примеры задач. Это первое известное упоминание об игре в печати.
Стандартная игра заполняет всю доску колышками, кроме центрального отверстия. Цель состоит в том, чтобы, делая правильные ходы, опустошить всю доску, за исключением единственного колышка в центральном отверстии.
Доска
Есть две традиционные доски ('.' В качестве начального штифта, 'o' как начальное отверстие):
английский | Европейский |
---|---|
· · · · · · · · · · · · · · · · · O · · · · · · · · · · · · · · · · · | · · · · · · · · · · · · · · · · · · · O · · · · · · · · · · · · · · · · · · · |
Играть
Допустимым ходом является перепрыгивание колышка перпендикулярно соседнему колышку в отверстие на расстоянии двух позиций, а затем удаление колышка, сошедшего с места.
На следующих схемах значок ·
указывает на колышек в отверстии, *
жирным шрифтом обозначается колышек, который необходимо переместить, и o
указывает на пустое отверстие. Синий ¤
- это отверстие, из которого переместился текущий колышек; красный *
- это конечное положение этого колышка, красный o
- это отверстие колышка, который был снят и снят.
Таким образом, допустимые ходы в каждом из четырех ортогональных направлений:
* · O → ¤ o * Перейти вправо
o · * → * o ¤ Перейти влево
* ¤ · → o Спрыгнуть o *
о * · → о Подпрыгните * ¤
На английской доске первые три хода могут быть такими:
· · · · · · · · · · · · · * · · ¤ · · o · · * ·· · · · · · · · · · О · · · · ¤ о * · · · · оо о · · ·· · · О · · · · · · * · · · · · · · · · · · · · ¤ · · ·· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·· · · · · · · · · · · · · · · · · · · · · · · · ·
Стратегия
Есть много различных решений стандартной проблемы, и одна нотация, используемая для их описания, присваивает отверстиям буквы:
Английский европейский abcabc Defydefzghijklmghijklmnopx PON nopx PONMLKJIHGMLKJIHG ФЭДЗФЕДЫ CBACBA
Это обозначение зеркального отображения используется, помимо прочего, поскольку на европейской доске один набор альтернативных игр должен начинаться с дырки в некоторой позиции и заканчиваться одиночным колышком в его зеркальной позиции. На английской доске эквивалентные альтернативные игры должны начинаться с дырки и заканчиваться колышком в той же позиции.
Не существует решения для европейской доски с начальной дырой в центре, если разрешены только ортогональные ходы. Это легко увидеть из аргументации Ханса Зантема . Разделите доски на позиции A, B и C следующим образом:
ABC ABCABABCABCABCABCABCABCABC BCABC ABC
Первоначально, когда свободна только центральная позиция, количество покрытых позиций A равно 12, количество покрытых позиций B равно 12, а также количество покрытых позиций C равно 12. После каждого хода количество покрытых позиций A увеличивается или уменьшается на один, и то же самое для количества покрытых позиций B и количества покрытых позиций C. Следовательно, после четного числа ходов все эти три числа будут четными, а после нечетного числа ходов все эти три числа будут нечетными. Следовательно, конечная позиция только с одним колышком не может быть достигнута, так как для этого потребуется, чтобы одно из этих чисел было равно единице (положение колышка, одно нечетное), в то время как два других числа равны нулю, следовательно, четным.
Однако существует несколько других конфигураций, в которых одно начальное отверстие может быть уменьшено до одного штифта.
Тактика, которую можно использовать, состоит в том, чтобы разделить доску на пакеты по три и полностью очистить (удалить) их, используя один дополнительный колышек, катализатор, который выскакивает, а затем снова прыгает обратно . В приведенном ниже примере * обозначает катализатор:
* · O ¤ o * o * · * o ¤ · → · → o → o · · ¤ o
Эта техника может использоваться с линией 3, блоком 2 · 3 и L-образной формой с 6 штифтами с основанием длиной 3 и стойкой длиной 4.
Другие альтернативные игры включают начало с двумя пустыми отверстиями и завершение с двумя колышками в этих отверстиях. Также начиная с одного отверстия здесь и заканчивая одним колышком там . На английской доске отверстие может быть где угодно, а последний колышек может заканчиваться только там, где разрешено число, кратное трем. Таким образом , отверстие в может оставить только одну затычку в виде , р , О или С .
Исследования пасьянса колышек
Известен тщательный анализ игры. [1] В этом анализе было введено понятие, называемое функцией пагоды, которое является мощным инструментом для демонстрации невозможности данной обобщенной проблемы с колышками.
Решение для поиска функции пагоды, которая демонстрирует невозможность данной задачи, формулируется как задача линейного программирования и разрешима за полиномиальное время. [2]
В статье 1990 г. были рассмотрены обобщенные задачи Hi-Q, которые эквивалентны задачам с колышками, и показана их NP-полнота . [3]
В статье 1996 года проблема пасьянса с привязкой сформулирована как задача комбинаторной оптимизации и обсуждаются свойства допустимой области, называемой «конусом пасьянса». [4]
В 1999 году пасьянс «колышек» был полностью решен на компьютере путем тщательного перебора всех возможных вариантов. Это было достигнуто за счет использования симметрии, эффективного хранения комбинаций плат и хеширования. [5]
В 2001 году был разработан эффективный метод решения задач пасьянса с колышками. [2]
Неопубликованное исследование 1989 года, посвященное обобщенной версии игры на английской доске, показало, что каждая возможная задача в обобщенной игре имеет 2 9 возможных различных решений, исключая симметрии, поскольку английская доска содержит 9 различных подквадратов 3 × 3. Одним из следствий этого анализа является определение нижней границы размера возможных проблем «перевернутого положения», в которых первоначально занятые ячейки остаются пустыми, и наоборот. Любое решение такой задачи должно содержать минимум 11 ходов, независимо от точных деталей задачи.
Используя абстрактную алгебру , можно доказать, что есть только 5 фиксированных позиций на доске, где игра может успешно закончиться с одним колышком. [6]
Решения английской игры
Самое короткое решение стандартной английской игры включает 18 ходов, считая несколько прыжков за один ход:
Кратчайшее решение пасьянса "Английский колышек" |
---|
ex lj ck · · · · · · · · · · · ¤ · * · · ¤ · · O · · O O · · · · · · · · · · O · · · · · · * O ¤ · · · · · * o ·· · · O · · · · · · * · · · · · · · · · · · · · · · · · ·· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·· · · · · · · · · · · · · · · · · · · · · · · · · Pf DP GI JH · · O · · o · · o · · o · O * · o · · o · · o ·· · · · O o · · · · · oo · · · · · oo · · · · · oo ·· · · · ¤ · · · · · · * · · · · · · · · · · · · · · · ·· · · · · · · · · · · О · · · · · · * о ¤ · · · ¤ о * о · · · · · ¤ · · o · · o · · · · · · · · · · · · mGI ik gi LJHljh · · O · · o · · o · · o · O · · o · · o · · o ·· · · · Oo ¤ · · ¤ o * oo ¤ o * o · ooo * o o o o o· · · · · · O · · · · · · O · · · · · · O · · · · · О О· · · О * о о · · · о · оо · · · о · оо · ¤ о о о о о · · O · · o · · o · · o · · · · · · · · · · · · CK pF ACK Mgi · · O · · o · · o · · o · O · · o · · o · · o ·o · oooooo · oooooo · ooooo o o * oooo· · · · · Oo · · ¤ · · oo · · o · · oo o · o · · oo· O * oooo · o o oooo · o * oooo ¤ o · oooo o · o * · o o · oo · o ¤ · · o · · o o ¤ ooo ackI dpFDPp ox ¤ о о оооем · O o ¤ oooooоо · О О оооо о oooooooooooo · o · o ooo · * o o ooo ¤ o * ooooo · o * oooo o o o ooooooooo о · о о о о ооо ооооооооо Порядок некоторых ходов можно поменять. Обратите внимание, что если вы вместо этого думаете о * как о дырке, а o как о колышек, вы можете решить головоломку, следуя решению в обратном порядке, начиная с последней картинки, идя навстречу первому. Однако для этого требуется более 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, пФ, МК, 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 прыжок, современные компьютеры могут легко изучить все игровые позиции за разумное время. [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 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]
Варианты платы
В пасьянс «Колышек» играли на досках других размеров, хотя два из них, приведенные выше, являются наиболее популярными. В нее также играли на треугольной доске с разрешенными прыжками во всех трех направлениях. Пока вариант имеет надлежащую «четность» и достаточно велик, он, вероятно, будет разрешим.
Обычный треугольный вариант имеет пять штифтов сбоку. Решение, при котором последний штифт достигает начального пустого отверстия, невозможно для отверстия в одном из трех центральных положений. Пустое угловое отверстие может быть решено за десять ходов, а пустое центральное отверстие - за девять (Bell 2008):
Кратчайшее решение треугольного варианта |
---|
* = колышек, чтобы двигаться дальше; ¤ = отверстие, созданное движением; o = штифт снят; * = дыра заполнена прыжком; · · · * ¤ · · · · · · · * о ¤ · · · · · · * · · ¤ · · * о · · · · · · · · · · · · · · O · · * * · * * · O · · ¤ о * * · O * O ¤ · O · * O · O · · O · ооооо * * * * ¤ ¤ оооо о о о о * * о о о оо * оо ¤ ¤ · · ¤ о о о ооо * * оо · о оо о о o * * o · o ¤ ¤ o · oooo * oooo ¤ oo * oo |
Видео игра
26 июня 1992 года для Game Boy была выпущена видеоигра, основанная на пасьянсе «колышек». Игра, названная просто «Пасьянс», была разработана Hect. В Северной Америке DTMC выпустила игру под названием «Lazlos 'Leap».
Рекомендации
- ^ Берлекамп, ER ; Конвей, JH ; Гай, RK (2001) [1981], Winning Ways for your Mathematical Plays (softback)
|format=
requires|url=
( help ) (2nd ed.), AK Peters / CRC Press, ISBN 978-1568811307, OCLC 316054929 - ^ а б Киёми, М .; Мацуи, Т. (2001), "Алгоритмы на основе целочисленного программирования для задач пасьянса с привязкой", Proc. 2-й Int. Конф. Компьютеры и Игры (CG 2000): Integer программирования алгоритмы , основанные на колышек пасьянсов проблемы , Lecture Notes в области компьютерных наук, 2063 , стр 229-240,. CiteSeerX 10.1.1.65.6244 , DOI : 10.1007 / 3-540-45579-5_15 , ISBN 978-3-540-43080-3
- ^ Uehara, R .; Ивата, С. (1990). «Обобщенный Hi-Q является NP-полным». Пер. IEICE . 73 : 270–273.
- ^ Авис, Д .; Деза, А. (2001), "О пасьянса конуса и его отношение к мульти-товарных потоков", Математическое программирование , 90 (1): 27-57, DOI : 10.1007 / PL00011419 , S2CID 7852133
- ^ Эйхлер; Jager; Людвиг (1999), c't 07/1999 Spielverderber, Solitaire mit dem Computer lösen (на немецком языке), 7 , стр. 218
- ^ "Mathematics and brainvita" , Заметки по математике , 28 августа 2012 г. , данные получены 6 сентября 2018 г.
- ^ Для доказательства Бизли см. Winning Ways , том № 4 (второе издание).
- ^ «солборд» . github . 2020-08-31 . Проверено 31 августа 2020 .
Реализация вычисления грубой силы в пасьянсе Peg
- ^ Брассин, Мишель (декабрь 1981 г.), "Découvrez ... le solitaire", Jeux et Stratégie (на французском языке)
дальнейшее чтение
- Бисли, Джон Д. (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