Главная ] Вверх ] Следующая ]

Глава 16. Игра в солитер

«Мне доставляет огромное удовольствие игра под названием солитер, —писал в 1716 году в одном из своих писем немецкий математик Готфрид Лейбниц. — Только играю я в нее не так, как все: по правилам игры полагается, перепрыгнув через клетку, снять стоящую на ней фишку, я же вместо этого предпочитаю восстанавливать разрушенное, то есть заполнять фишками все пустые клетки, через которые перепрыгивает моя фишка. При этом возникает новая задача: как построить из фишек заданную фигуру, если известно, что, следуя обычным правилам, ее можно разрушить. «Но зачем все это?»—спросите вы. Отвечу: «Чтобы совершенствовать искусство изобретать новое, ибо нам необходимо уметь строить все, что только можно придумать, руководствуясь здравым смыслом».

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

Ни одна другая игра с фишками на специальной доске не пользовалась столь широкой известностью в течение продолжительного периода времени, как солитер. Происхождение этой игры неизвестно. Честь ее изобретения иногда приписывают некоему узнику, томившемуся в Бастилии. Судя по французским книгам и статьям, посвященным теории и истории солитера, эта игра была широко распространена во Франции в конце XIX века.

Для игры в солитер нужна доска с лунками, в которые кладутся шарики, или отверстиями, в которые втыкаются обычные колышки. С не меньшим успехом в солитер можно играть фишками или монетками, начертив доску на листке бумаги (рис. 90).

 

37

 

47

 

57

 

 

 36 

46 

56 

 

15

 

25

 

35

 

45

 

55

 

65

 

75

 

14

 

24

 

34

 

44

 

54

 

64

 

74

 

13

 

23

 

33

 

43

 

53

 

63

 

73

 

 

32

 

42

 

52

 

 

31

 

41

 

51 

 

Рис. 90   Доска для игры в солитер.

Именно на такой доске с тридцатью тремя клетками чаще всего играют в солитер в Англии, Соединенных Штатах Америки и в России. Французы дополняют эту доску еще четырьмя клетками, центры которых обозначены на рис. 90 четырьмя черными точками. В остальных странах Западной Европы можно встретить обе разновидности досок, однако французский вариант распространен гораздо меньше, Это объясняется, по-видимому, тем, что на французской доске не-возможно оставить в конце игры одну фишку, если в начале партии были заняты все клетки, кроме центральной. Клетки принято нумеровать двузначными числами: первая цифра означает номер столбца, считая по порядку слева направо, вторая — номер строки, отсчитываемый снизу вверх.

Основная и, как правило, единственная разновидность игры начинается с того, что на все клетки доски, кроме центральной, расставляются фишки. Цель игры состоит в том, чтобы после ряда «прыжков» на доске осталась всего одна фишка. Решение выглядит особенно изящно, если эта последняя фишка остается в центральной клетке. «Прыжок» означает следующее: фишка переносится на свободную клетку через любую соседнюю фишку, которая при этом снимается с доски. Прыжки эти очень напоминают прыжки в шашках. Единственное отличие состоит лишь в том, что при игре в солитер фишки можно переставлять влево, вправо, вверх и вниз, но запрещается ходить по диагонали.

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

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

 Рис. 91    Традиционные задачи, в которых последняя фишка должна оставаться в центре доски.

В каждом случае последнюю фишку надо оставить в центре. «Латинский крест», например, решается в пять ходов: 45-25, 43-45, 55-35, 25-45, 46-44.

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

Рис. 92    Фигуры, которые должны остаться на доске в конце игры.

Ниже приведена программа на NP-языке для решения головоломки. Так как количество прыжков известно из условий задачи, для каждого прыжка создается запись класса Jump (см. ограничение Main.InsJumps) и для каждой позиции создается записи класса Check (см. ограничение Main.InsChecks), отражающее состояние клетки. В задаче заданы начальная и конечная позиции; внесение этих позиций в модель производится ограничениями Main.InitStarts и Main.InitEnds. В задаче нужно минимизировать количество ходов, что учитывает ограничение Main.Optimum. Классы Jump и Check содержат ограничения, обеспечивающие правила игры: связывают текущее состояние игры, прыжок и следующее состояние.

Project Soliter

Module Main 
' Игра в солитер
' http://np-soft.ru/npproject/projects/puzzles/gardner/16/index.htm
Var Board{} =                            ' Множество доски для игры в солитер
{       37, 47, 57,
        36, 46, 56,
15, 25, 35, 45, 55, 65, 75,
14, 24, 34, 44, 54, 64, 74,
13, 23, 33, 43, 53, 63, 73,
        32, 42, 52,
        31, 41, 51}
Var ValidMoves() As Integer = {1: -1, 2:1, 3: -10, 4:10, 5:9, 6: -9, 7:11, 8: -11}
Field Starts{} As Integer                ' Множество начальных фишек
Field Ends{} As Integer                  ' Множество конечных фишек
Var JumpCount = Abs(Starts) - Abs(Ends)  ' Количество прыжков

Con InsJumps As                          ' Создание экземпляров классов прыжков
  ForAll(j In {1..JumpCount}, Append(Jump, Me : j))

Con InsChecks As                         ' Создание экземпляров классов клеток
  ForAll(j In {1..JumpCount+1},          ' 
    ForAll(b In Board, Append(Check, Me : 100*j + b)))

Con InitStarts As                        ' Установка начальной позиции
  ForAll(b In Board,
    Check(100+b).Value = Exists(c In Starts, c = b))

Con InitEnds As                          ' Установка конечной позиции
  ForAll(b In Board,
    Check((JumpCount+1)*100+b).Value = Exists(c In Ends, c = b))

Con Optimum As ' Требуется минимизировать количество ходов
  Minimize(Sum(j In Jump, j.IsNewMove))  

Class Jump
Var StartPos As Board     ' Стартовая позиция прыжка
Var DelPos As Board       ' Позиция, через которую производится прыжок
Var EndPos As Board       ' Конечная позиция прыжка
Var Delta As {1..8}       ' Возможные направления прыжка
Var IsNewMove As Boolean  ' Флажок начала нового хода

Con Hints As
  Hint(StartPos : 100-Me, Delta : 100-Me)

Con Save As
  Store(StartPos, EndPos)

Con StartDel As           ' Вычисление позиции промежуточной клетки
  DelPos = StartPos + Sum(i In {1..8}, (Delta = i)* ValidMoves(i))

Con EndDel As             ' Вычисление конечной позиции прыжка по начальной
  EndPos = 2*DelPos  - StartPos ' позиции и промужуточной

Con CalcNewMove As        ' Вычисление флажка нового хода
  (Me = 1 ==> IsNewMove = 1) And
  (Me > 1 ==> IsNewMove <=> Jump(Me-1).EndPos <> StartPos)

Class Check
Var Value As Boolean  ' Value = 1 - значит фишка стоит, Value = 0 - фишки нет
Var J = Me \ 100      ' Номер позиции (возникает после J-1 прыжков)
Var Pos = Me Mod 100  ' Позиция (см. множество Main.Board)

Con ValidJump As      ' Прыжок возможен, если стартовая и промежуточная клетки
                      ' имеют фишки, а конечная - нет
  J <= JumpCount ==>  ' (для последней позиции J будет больше числа прыжков)
  (Not Value ==> Jump(J).StartPos<>Pos And Jump(J).DelPos<>Pos) And
  (Value ==> Jump(J).EndPos<>Pos)

Con CalcValue As      ' Вычисление новой позиции по предыдущему ходу
  J > 1 ==>
    Value = If(Pos = Jump(J-1).StartPos Or Pos = Jump(J-1).DelPos, 0,
            If(Pos = Jump(J-1).EndPos, 1, Check(Me-100).Value))

Скачать проект.