Солитер — настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita. В СССР выпускалась головоломка под названием Йога.
Первое упоминание об игре относится к временам Людовика XIV, в частности к 1697 году, и связано с королевским двором. Так, 1697 годом помечена гравюра Клода Огюста Берея «Анна де Роан Шабо, принцесса де Субиз», на которой изображена принцесса, играющая в солитер. В августе 1697 во французском литературном журнале Mercure galant было напечатано описание доски, правила и примеры задач. Это первое известное упоминание игры в печати.
В стандартной игре всё поле заполняется колышками, за исключением центрального отверстия. Цель игры — освободить всю доску от колышков, оставив последний колышек в центре доски.
Доска
Существуют две традиционные доски для игры ('.' В качестве начального колышка, 'o' в качестве пустого отверстия): Английская Европейская • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • •
Игра
Разрешённым ходом является прыжок колышка через смежный колышек на свободное отверстие сразу после второго колышка (как в шашках, но движение происходит вертикально или горизонтально, по диагонали двигаться нельзя); затем колышек, через который перепрыгнули, удаляется.
Обозначения в диаграммах ниже: • колышек в отверстии * передвигаемый колышек o пустое отверстие отверстие, с которого был сделан ход конечная позиция колышка отверстие удалённого колышка.
Тогда допустимыми ходами во всех четырёх направлениях будут:
* • o → прыжок вправо
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
Зеркальное обозначение полей используется, кроме всего прочего, поскольку на европейской доске в одном из семейства альтернативных игр игра начинается с некоторого отверстия в произвольном месте и должна закончиться в зеркальном отверстии. На английской доске альтернативные игры начинаются и кончаются в том же самом отверстии.
В европейской версии игры не существует решения с начальным пустым полем в центре, если только не разрешить диагональные ходы. Это легко понять, если учесть аргументы Ганса Цантема (Hans Zantema). Разметим позиции доски буквами 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 (всего 13, но одна свободна), число позиций C тоже 12. После каждого хода число колышков группы A уменьшается или увеличивается на единицу, то же самое происходит с позициями групп B и C. Таким образом, после чётного числа ходов все эти три числа чётны, а после нечётного — нечётны. Таким образом, конечная позиция, в которой остаётся только один колышек, получена быть не может — группа, где окажется колышек, будет иметь сумму единица, в то время как другие два должны иметь сумму ноль.
Есть, однако, некоторые другие конфигурации, в которых можно одно свободное отверстие довести до единственного колышка.
Для решения головоломки полезна тактика, при которой вся доска делится на тройки, а затем тройки удаляются с помощью дополнительного колышка, катализатора. В приведенном примере * является катализатором:
* • o o • • → • → → o • • o
Такая техника может быть использована для трёх колышек в ряд, для блоков 2•3 и фигуры L из 6 колышек (3 в одну сторону и 4 перпендикулярно).
Существуют игры, начинающиеся с двух пустых позиций и завершающиеся двумя колышками в этих позициях. Также можно начинать с одной заранее выбранной позиции и завершать в другой заранее выбранной позиции. На английской доске пустое отверстие может быть в любом месте, а завершиться игра должна в этой же позиции, либо в одной из трёх добавочных допустимых позиций. Так, если начальное пустое поле было в точке a, игра должна завершиться единственным колышком в позициях a, p, O или C.
Изучение игры в солитер Полный анализ игры проведён в книге «Winning Ways for your Mathematical Plays» (ISBN 0-12-091102-7 в Великобритании и ISBN 1-56881-144-6 в США) (том 4, второе издание). В книге введена нотация, названная функция пагоды, которая является сильным средством для доказательства невозможности решения данной (обобщённой) задачи солитера. Задача поиска такой функции формулируется как задача целочисленного линейного программирования (смотрите Kiyomi и Matsui 2001). Ухара и Ивата (Uehara, Iwata, 1990) изучали обобщённые Hi-Q задачи, которые эквивалентны задачам солитера и показали их NP-полноту. Авис и Деза (Avis, Deza, 1996) сформулировали задачу солитера как комбинаторную задачу оптимизации и обсуждали свойство области допустимых решений, называемой конусом солитера. Кийоми и Мацуи (Kiyomi, Matsui, 2001) предложили эффективный метод решения задач солитера.
Неопубликованное исследование 1989 года об обобщённой версии игры на английской доске показало, что каждая допустимая задача в обобщённой игре имеет 29 различных решений, исключая симметрию, поскольку английская доска содержит 9 различных 3×3 подквадратов. Это исследование дало нижнюю границу размера возможных задач 'обратных позиций', в которых первоначально занятые отверстия становятся занятыми, и наоборот. Любое решение такой задачи должно состоять минимум из 11 ходов, независимо от точных формулировок задачи.
С помощью алгебры можно доказать, что имеется только 5 фиксированных точек, где игра может завершиться успешно с одним колышком.
Решения для английской версии игры Кратчайшее решение стандартной английской версии игры состоит из 18 ходов, если считать многократные перепрыгивания за один ход:
Shortest solution to English peg solitaire e-x l-j c-k
• • • • • • • • • • • • * • • • • o • • o • • • • • • • • • • • • • • • • • • • • • o • • • • o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
P-f D-P G-I J-H
• • o • • o • • o • • o • o • o • • o • • o • • • • • o • • • • • o o • • • • • o o • • • • • o o • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • o • • • • • • • o • • o • • • • • • • • • • • •
m-G-I i-k g-i L-J-H-l-j-h
• • o • • o • • o • • o • o • • o • • o • • o • • • • • o o • • o o o • o o o o • • • • • • • • • • • • o • • • • • • o • • • • • o • • • o • • • o • o o • • • o • o o • o • • o • • o • • o • • o • • • • • • • • • • • •
C-K p-F A-C-K M-g-i
• • o • • o • • o • • o • o • • o • • o • • o • o • o o o o o o • o o o o o o • o o o o o o o o o • • • • • o o • • • • o o • • o • • o o • o • • o o • o o o o o • o o o o o • o o o o o o • o o o o • o • o • o o • o • • o • • o o o
a-c-k-I d-p-F-D-P-p o-x
o o o o o o • o o o o o o o o • o o o o o o o o o o o o o o o o o • o • o o o • o o o o o o o o • o o o o o o o o o o o o o o o o • o o o o o o o o o o o o o
Порядок некоторых ходов можно менять. Заметьте, что если использовать * для обозначения отверстий, а o для обозначения колышков, вы можете получить решение головоломки, проследуя решение в обратном порядке, начав с последней картинки и двигаясь к первой. Однако это потребует более 18 ходов.
Решение было найдено в 1912 году Эрнестом Бергхольтом (Ernest Bergholt) и было доказано, что решение кратчайшее Джоном Бисли (John Beasley) в 1964Смотрите доказательство Бисли в Winning Ways for your Mathematical Plays, том 4 (второе издание)..
Это же решение можно видеть на сайте, где также вводится нотация Вольстенхолма, которая разработана, чтобы сделать запоминание решения проще.
Другие решения включены в следующий список. Список имеет формат Начальная позиция: конечная позиция= Далее идут пары: колышек и позиция, на которую он переходит. Пары разделены запятой или косой чертой (косая ставится как завершение группы ходов)
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 ходов, и число Отсутствия Ходов, позиций, в которых продолжение невозможно.
Если позиция может быть получена поворотом либо зеркальным отражением, она считается идентичной.
n ВП ОХ 1 1 0 2 2 0 3 8 0 4 39 0 5 171 0 6 719 1 7 2757 0 8 9751 0 9 31 312 0 10 89 927 1
n ВП ОХ 11 229 614 1 12 517 854 0 13 1 022 224 5 14 1 753 737 10 15 2 598 215 7 16 3 312 423 27 17 3 626 632 47 18 3 413 313 121 19 2 765 623 373 20 1 930 324 925
n ВП ОХ 21 1 160 977 1972 22 600 372 3346 23 265 865 4356 24 100 565 4256 25 32 250 3054 26 8688 1715 27 1917 665 28 348 182 29 50 39 30 7 6
n ВП ОХ 31 2 2
Поскольку максимальное число позиций на каждый ход не превосходит 3626632, а число ходов равно 31, современные компьютеры без труда могут просчитать все позиции за приемлемое время.
Приведённые выше последовательности «ВП» занесены в OEIS под номером A112737. Заметьте, что общее число достижимых позиций (сумма последовательности) равно , в то время как общее число возможных позиций равно , или, примерно, /8 ~ 1 миллиард, если учитывать симметрию. Таким образом, только около 2,2 % всех возможных позиций на доске достижимы, если начинать с пустого центра.
Можно получить все возможные позиции на доске. Результаты, приведённые в таблице, можно получить, используя mcrl2 toolset (смотрите peg_solitaire пример в пакете).
n ВП 1 1 2 4 3 12 4 60 5 296 6 1338 7 5648 8 21 842
n ВП 9 77 559 10 249 690 11 717 788 12 1 834 379 13 4 138 302 14 8 171 208 15 14 020 166 16 20 773 236
n ВП 17 26 482 824 18 28 994 876 19 27 286 330 20 22 106 348 21 15 425 572 22 9 274 496 23 4 792 664 24 2 120 101
n ВП 25 800 152 26 255 544 27 68 236 28 14 727 29 2 529 30 334 31 32 32 5
Решения для европейского варианта игры существует 3 начальных неконгруэнтных позиции, имеющие решения. Это:
1)