Ход конём

Есть проблема, которая очень подходит для решения с помощью недетерминированности. Скажем, у нас есть шахматная доска и на ней только одна фигура – конь. Мы хотим определить, может ли конь достигнуть определённой позиции в три хода. Будем использовать пару чисел для представления позиции коня на шахматной доске. Первое число будет определять столбец, в котором он находится, а второе число – строку.

Создадим синоним типа для текущей позиции коня на шахматной доске.

type KnightPos = (Int, Int)

Теперь предположим, что конь начинает движение с позиции (6, 2). Может ли он добраться до (6, 1) именно за три хода? Какой ход лучше сделать следующим из его нынешней позиции? Я знаю: как насчёт их всех?! К нашим услугам недетерминированность, поэтому вместо того, чтобы выбрать один ход, давайте просто выберем их все сразу! Вот функция, которая берёт позицию коня и возвращает все его следующие ходы:

moveKnight :: KnightPos –> [KnightPos]

moveKnight (c,r) = do

   (c',r') <– [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

              ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

              ]

   guard (c' `elem` [1..8] && r' `elem` [1..8])

   return (c',r')

Конь всегда может перемещаться на одну клетку горизонтально или вертикально и на две клетки вертикально или горизонтально, причём каждый его ход включает движение и по горизонтали, и по вертикали. Пара (c', r') получает каждое значение из списка перемещений, а затем функция guard заботится о том, чтобы новый ход, а именно пара (c', r'), был в пределах доски. Если движение выходит за доску, она возвращает пустой список, что приводит к неудаче, и вызов return (c', r') не обрабатывается для данной позиции.

Эта функция может быть записана и без использования списков в качестве монад. Вот как записать её с использованием функции filter:

moveKnight :: KnightPos –> [KnightPos]

moveKnight (c,r) = filter onBoard

   [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

   ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

   ]

   where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]

Обе версии делают одно и то же, так что выбирайте ту, которая кажется вам лучше. Давайте опробуем функцию:

ghci> moveKnight (6, 2)

[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]

ghci> moveKnight (8, 1)

[(6,2),(7,3)]

Работает чудесно! Мы берём одну позицию и просто выполняем все возможные ходы сразу, так сказать.

Поэтому теперь, когда у нас есть следующая недетерминированная позиция, мы просто используем операцию >>=, чтобы передать её функции moveKnight. Вот функция, принимающая позицию и возвращающая все позиции, которые вы можете достигнуть из неё в три хода:

in3 :: KnightPos –> [KnightPos]

in3 start = do

   first <– moveKnight start

   second <– moveKnight first

   moveKnight second

Если вы передадите ей пару (6, 2), результирующий список будет довольно большим. Причина в том, что если есть несколько путей достигнуть определённой позиции в три хода, ход неожиданно появляется в списке несколько раз.

Вот предшествующий код без использования нотации do:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

Однократное использование операции >>= даёт нам все возможные ходы с начала. Когда мы используем операцию >>= второй раз, то для каждого возможного первого хода вычисляется каждый возможный следующий ход; то же самое верно и в отношении последнего хода.

Помещение значения в контекст по умолчанию с применением к нему функции return, а затем передача его функции с использованием операции >>= – то же самое, что и обычное применение функции к данному значению; но мы сделали это здесь, во всяком случае, ради стиля.

Теперь давайте создадим функцию, которая принимает две позиции и сообщает нам, можем ли мы попасть из одной в другую ровно в три хода:

canReachIn3 :: KnightPos –> KnightPos –> Bool

canReachIn3 start end = end `elem` in3 start

Мы производим все возможные позиции в пределах трёх ходов, а затем проверяем, находится ли среди них искомая.

Вот как проверить, можем ли мы попасть из (6,2) в (6,1) в три хода:

ghci> (6, 2) `canReachIn3` (6, 1)

True

Да! Как насчёт из (6, 2) в (7, 3)?

ghci> (6, 2) `canReachIn3` (7, 3)

False

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