Русская Википедия:Солитер (игра)
Солитер — это настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita. В СССР выпускалась головоломка под названием Йога[1].
Первое упоминание об игре можно выявить во дворе Людовика XIV в 1697. Этим годом помечена гравюра Клода Огюста Берея Анна де Роан Шабо, принцесса де Субиз, на которой изображена принцесса, играющая в солитер. В августе 1697 во французском литературном журнале Mercure galant было напечатано описание доски, правила и примеры задач. Это первое известное упоминание игры в печати.
В стандартной игре всё поле заполняется колышками, за исключением центрального отверстия. Цель игры — освободить всю доску от колышек, оставив последний колышек в центре доски.
Доска
Шаблон:Multiple image Существуют две традиционные доски для игры ('.' В качестве начального колышка, 'o' в качестве пустого отверстия):
Английская | Европейская | ||
---|---|---|---|
• • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • |
• • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • |
Игра
Разрешённым ходом является прыжок колышка через смежный колышек на свободное отверстие сразу после второго колышка (как в шашках, но движение происходит вертикально или горизонтально, по диагонали двигаться нельзя), затем колышек, через который перепрыгнули, удаляется.
Обозначения в диаграммах ниже:
• колышек в отверстии
* передвигаемый колышек
o пустое отверстие
Шаблон:Blue отверстие, с которого был сделан ход
Шаблон:Red конечная позиция колышка
Шаблон:Red отверстие удалённого колышка.
Тогда допустимыми ходами во всех четырёх направлениях будут:
* • o → Шаблон:Blue Шаблон:Red Шаблон:Red прыжок вправо
o • * → Шаблон:Red Шаблон:Red Шаблон:Blue прыжок влево
* Шаблон:Blue • → Шаблон:Red прыжок вниз o Шаблон:Red
o Шаблон:Red • → Шаблон:Red прыжок вверх * Шаблон:Blue
На английской доске первыми тремя ходами могут быть:
• • • • • • • • • • • • • * • • Шаблон:Blue • • o • • Шаблон:Red • • • • • • • • • • • Шаблон:Red • • • • Шаблон:Blue Шаблон:Red Шаблон:Red • • • • o o Шаблон:Red • • • • • • o • • • • • • Шаблон:Red • • • • • • • • • • • • • Шаблон:Blue • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Стратегия
Легко пойти неверным путём, и обнаружить, что два или три пустых отверстия отделяют одинокий колышек. Многие люди так и не смогли решить задачу.
Имеется множество различных решений для стандартной задачи, и для их описания дадим отверстиям буквенные обозначения:
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 Шаблон:Blue Шаблон:Red Шаблон:Red o Шаблон:Red • Шаблон:Red Шаблон:Red Шаблон:Blue • → • → Шаблон:Red → o • • Шаблон:Blue 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 фиксированных точек, где игра может завершиться успешно с одним колышком[2].
Решения для английской версии игры
Кратчайшее решение стандартной английской версии игры состоит из 18 ходов, если считать многократные перепрыгивания за один ход:
Shortest solution to English peg solitaire |
---|
e-x l-j c-k • • • • • • • • • • • Шаблон:Blue • * • • Шаблон:Blue • • o • • o Шаблон:Red • • • • • • • • • • Шаблон:Red • • • • • • Шаблон:Red Шаблон:Red Шаблон:Blue • • • • • Шаблон:Red o • • • • o • • • • • • Шаблон:Red • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • P-f D-P G-I J-H • • o • • o • • o • • o • o Шаблон:Red • o • • o • • o • • • • • Шаблон:Red o • • • • • o o • • • • • o o • • • • • o o • • • • • Шаблон:Blue • • • • • • Шаблон:Red • • • • • • • • • • • • • • • • • • • • • • • • • • • Шаблон:Red • • • • • • Шаблон:Red Шаблон:Red Шаблон:Blue • • • Шаблон:Blue Шаблон:Red Шаблон:Red o • • • • • Шаблон:Blue • • 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 Шаблон:Blue • • Шаблон:Blue Шаблон:Red Шаблон:Red o o Шаблон:Blue Шаблон:Red Шаблон:Red o • o o o Шаблон:Red Шаблон:Red Шаблон:Blue Шаблон:Red Шаблон:Blue o • • • • • • Шаблон:Red • • • • • • o • • • • • • o • • • • • Шаблон:Red o • • • o Шаблон:Red Шаблон:Red Шаблон:Blue • • • o • o o • • • o • o o • Шаблон:Blue Шаблон:Red Шаблон:Blue Шаблон:Red Шаблон:Blue 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 Шаблон:Blue Шаблон:Red Шаблон:Red o o o o • • • • • o o • • Шаблон:Blue • • o o • • o • • o o Шаблон:Red • o • • o o • o Шаблон:Red o o o o • o Шаблон:Red o o o o • o Шаблон:Red o o o o Шаблон:Blue o • o o o o Шаблон:Red • o Шаблон:Red • o Шаблон:Red • o o • o Шаблон:Blue • • o • • Шаблон:Blue Шаблон:Red Шаблон:Blue o o o a-c-k-I d-p-F-D-P-p o-x Шаблон:Blue Шаблон:Red Шаблон:Blue o o o o o o • o Шаблон:Red Шаблон:Blue o o o o o o o • o Шаблон:Blue o o o o Шаблон:Red o o o o o o o o o o o o • o • Шаблон:Red o o o • Шаблон:Red Шаблон:Red Шаблон:Blue o o o Шаблон:Blue Шаблон:Red Шаблон:Red o o o o o • o Шаблон:Red o o o o Шаблон:Red o Шаблон:Red o o o o o o o o o o • o Шаблон:Blue Шаблон:Red Шаблон:Blue o o o o o o o o o o o o Порядок некоторых ходов можно менять. Заметьте, что если использовать * для обозначения отверстий, а o для обозначения колышков, вы можете получить решение головоломки, проследуя решение в обратном порядке, начав с последней картинки и двигаясь к первой. Однако это потребует более 18 ходов. |
Решение было найдено в 1912 году Эрнестом Бергхольтом (Ernest Bergholt) и было доказано, что решение кратчайшее Джоном Бисли (John Beasley) в 1964[3].
Это же решение можно видеть на сайте[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 ходов, и число Отсутствия Ходов, позиций, в которых продолжение невозможно.
Если позиция может быть получена поворотом либо зеркальным отражением, она считается идентичной. Шаблон:Col-begin Шаблон:Col-break
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[5]. Заметьте, что общее число достижимых позиций (сумма последовательности) равно Шаблон:Num[5], в то время как общее число возможных позиций равно Шаблон:Power, или, примерно, Шаблон:Power/8 ~ 1 миллиард, если учитывать симметрию. Таким образом, только около 2,2 % всех возможных позиций на доске достижимы, если начинать с пустого центра.
Можно получить все возможные позиции на доске. Результаты, приведённые в таблице, можно получить, используя mcrl2 toolset (смотрите peg_solitaire пример в пакете). Шаблон:Col-begin Шаблон:Col-break
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)
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):
Кратчайшее решение треугольного варианта |
---|
* = колышек, который делает следующий ход; Шаблон:Blue = отверстие, освободившееся в результате хода; Шаблон:Red = удалённые колышки (через которые перепрыгнули); Шаблон:Blue = отверстие, в котором оказался колышек после хода; • • • * Шаблон:Blue • • • • • • • * Шаблон:Red Шаблон:Blue • • • • • • * • • Шаблон:Blue • • Шаблон:Blue Шаблон:Red • • • • • • • • • • • • • • Шаблон:Red • • * Шаблон:Blue • * * • o • • Шаблон:Blue Шаблон:Red Шаблон:Blue * • o Шаблон:Blue Шаблон:Red Шаблон:Blue • o • Шаблон:Blue o • o • • o • o o o o o Шаблон:Blue Шаблон:Blue * * Шаблон:Blue Шаблон:Blue o o o o Шаблон:Red o Шаблон:Red o Шаблон:Blue Шаблон:Blue o Шаблон:Red Шаблон:Red o o Шаблон:Blue o o Шаблон:Blue Шаблон:Blue • • Шаблон:Blue o Шаблон:Red Шаблон:Red o o o Шаблон:Blue Шаблон:Blue o o • Шаблон:Red o o Шаблон:Red o o * * o • o Шаблон:Blue Шаблон:Blue o • o o o o * o o o o Шаблон:Blue o o Шаблон:Blue o o |
См. также
Примечания
Литература
- Шаблон:Статья.
- Шаблон:Книга
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья 206 (6): 156—166, June 1962; 214 (2): 112—113, Feb. 1966; 214 (5): 127, May 1966.
- Шаблон:Книга.
- Шаблон:Статья.
Ссылки
- HTML5 версия Albino Tonnina
- Игра Солитер и её связь с конечными полями
- Игра Солитер и теория групп
- Шаблон:Cite web
- Шаблон:Cite web
- Солитер на прямоугольной доске 12 F3
- Классические доски игры Солитер F1
- Игра Солитер на доске 16 F2
- Игра Солитер на доске 25 F2
- Солитер Шаблон:Wayback Пошаговое решение английской версии игры Солитер
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Смотрите доказательство Бисли в Winning Ways for your Mathematical Plays, том 4 (второе издание).
- ↑ Шаблон:Cite web
- ↑ 5,0 5,1 Шаблон:OEIS long