начинается с позиции, в которой все фишки перемешаны. Необходимо, переставляя фишки, вернуться в
исходное положение. Каждым ходом мы двигаем одну фишку на пустое поле. В исходном положении фишки
идут по порядку.
9
1
4
8
1
2
3
4
13
11
5
5
6
7
8
2
10
7
3
9
10 11 12
15 14 12
6
13 14 15
Рис. 13.1: Случайное и конечное состояние игры пятнашки
Программа будет перемешивать фишки и отображать поле для игры. Она будет спрашивать следующий
ход и обновлять поле после хода. Если мы расставим все фишки по порядку, программа сообщит нам об этом
и предложит начать новую игру. В каждый момент мы можем не только сделать ход, но и покинуть игру или
начать всё заново. Известно, что не из любого положения можно расставить фишки по порядку. Поэтому наш
алгоритм перемешивания должен генерировать только такие позиции, для которых решение возможно.
Набросок решения
Программа, которую мы хотим написать, будет вести диалог с пользователем. Она показывает поле для
игры и спрашивает следующий ход. Потом она распознаёт ход, и показывает обновлённое поле. И так далее.
Нам нужно как-то организовать этот диалог.
При этом в программе можно выделить две независимые части. Одна отвечает за сам диалог. Она прини-
мает реплики пользователя и отображает поле для игры. А другая часть отвечает за правила игры пятнашки:
как ходы влияют на поле, какое положение является победным, как перемешивать фишки.
| 201
У нас будет два отдельных модуля: один для описания игры, назовём его Game, а другой для описания
диалога с пользователем. Мы назовём его Loop (петля или цикл), поскольку диалог это зацикленная проце-
дура получения реплики и реакции на реплику.
Такой вот набросок-ориентир. После этого можно приступать к реализации. Но с чего начать?
Каркас. Типы и классы
В Haskell программы обычно начинают строить с каркаса – с типов и классов. Нам нужно выделить ос-
новные сущности и подумать какие типы подходят для их описания лучше всего.
В нашей задаче есть поле с фишками и ходы. Мы делаем ходы и фишки двигаются. Поле – это матрица
или двумерный массив. У нас есть два индекса, которые пробегают значения от нуля до трёх. В каждой
ячейке массива хранятся фишки. Фишки обозначаются целыми числами:
type Pos
= (Int, Int)
type Label
= Int
type Board
= Array Pos Label
Пустую фишку мы будем также обозначать числом. Физически когда мы ходим, мы меняем положение
одной фишки. Но в нашем описании мы меняем местами две фишки, поскольку пустая фишка также обозна-
чается номером. Когда мы ходим, мы меняем положение пустой фишки, одним ходом мы можем сместить
её вверх, вниз, влево или вправо. Введём специальный тип для обозначения ходов:
data Move = Up | Down | Left | Right
Для того чтобы при каждом ходе не искать пустую клетку, давайте сохраним её текущее положение. Тип
Game будет содержать текущее положение пустой клетки и положение фишек:
data Game = Game {
emptyField
:: Pos,
gameBoard
:: Board }
Вот и все типы для описания игры. Сохраним их в модуле Game. Теперь подумаем о типах для диалога
с пользователем. В этом модуле наверняка будет много функций с типом IO, потому что в нём происходит
взаимодействие с игроком. Но, что является каркасом для диалога?
Если мы хотим с кем-нибудь общаться, необходимо чтобы у нас был с собеседником общий язык, он и
будет каркасом для диалога. Вспомним, что мы ожидаем от пользователя. Пользователь может:
• Сделать ход
• Начать новую игру
• Выйти из игры
Если пользователь делает ход мы показываем новое положение поля, если он начинает новую игру мы
показываем ему новую перемешанную позицию, давайте у нас будет разная степень перемешанности фи-
гур. При перемешивании мы стартуем из победного положения и начинаем случайным образом делать хо-
ды. Чем больше ходов мы сделаем тем сложнее будет собрать игру. Поэтому пользователь будет указывать
число шагов для перемешивания при запросе новой игры. Если пользователь попросит закончить игру мы
попрощаемся и выйдем из игры.
На основе этих рассуждений вырисовывается следующий тип для сообщений:
data Query = Quit | NewGame Int | Play Move
Значение типа Query (запрос) может быть константа Quit (выход), запрос новой игры NewGame с числом,