Русская Википедия:Солитер (игра)

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Значения

Файл:Peg Solitaire 1687 on Portrait of Princess Soubise by Claude-Auguste Berey.jpg
Анна де Роан Шабо, принцесса де Субиз, играющая в солитер, 1697

Солитер — это настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita. В СССР выпускалась головоломка под названием Йога[1].

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

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

Доска

Шаблон:Multiple image Существуют две традиционные доски для игры ('.' В качестве начального колышка, 'o' в качестве пустого отверстия):

Английская Европейская
     • • •
     • • •
 • • • • • • • 
 • • • o • • • 
 • • • • • • • 
     • • •
     • • •
     • • •
   • • • • •
 • • • • • • • 
 • • • o • • • 
 • • • • • • • 
   • • • • •
     • • •
Файл:Solitaire 01.jpg
Английская доска для игры в солитер
Файл:French solitaire.jpg
Европейская доска для игры в солитер

Игра

Файл:PegGame.jpg
мужчина играет в солитер

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

Обозначения в диаграммах ниже:
колышек в отверстии
* передвигаемый колышек
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 ходов, если считать многократные перепрыгивания за один ход:

Решение было найдено в 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

Шаблон:Col-break

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

Шаблон:Col-break

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

Шаблон:Col-break

n ВП ОХ
31 2 2

Шаблон:Col-end

Поскольку максимальное число позиций на каждый ход не превосходит 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

Шаблон:Col-break

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

Шаблон:Col-break

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

Шаблон:Col-break

n ВП
25 800 152
26 255 544
27 68 236
28 14 727
29 2 529
30 334
31 32
32 5

Шаблон:Col-end

Решения для европейского варианта игры

существует 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]

Варианты досок

Солитер играется и на других досках, хотя приведённые две наиболее популярны. Доска может быть треугольной, с ходами в трёх направлениях.

Файл:Peg Solitaire game board shapes.svg
Виды досок для игры в солитер:
(1) Французская (Европейская), 37 отверстий, 17-й век;
(2) Виглеб (Wiegleb) 1779, Германия, 45 отверстий;
(3) Несимметричная доска 3-3-2-2, как описано Джорджем Беллом (George Bell), 20-й век;
(4) Английская (стандартная), 33 отверстия;
(5) Алмаз, 41 отверстие;
(6) Треугольник, 15 отверстий.
Серое поле = где должен оказаться оставшийся последним колышек.

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

  1. Шаблон:Cite web
  2. Шаблон:Cite web
  3. Смотрите доказательство Бисли в Winning Ways for your Mathematical Plays, том 4 (второе издание).
  4. Шаблон:Cite web
  5. 5,0 5,1 Шаблон:OEIS long