Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS.
Шахматный конь стоит на шахматной доске и задумчиво смотрит в шахматную даль. Сколько разных ходов он может сделать?
Дано: knightNr — номер клетки доски, где стоит конь (от 0 до 63). Надо: movesCount — количество полей, куда он может пойти (от 2 до 8).
Хвала изобретателю шахмат, на доске 64 клетки. Хвала архитектору компьютеров — у типа ulong тоже 64 бита. Это же надо было случиться такому совпадению! Это просто гениально — хранить всю доску в одном целом числе! Для этого решения существует даже специальный термин — bitboard — битовая доска.
Идея решения задачи следующая.
1.Конвертировать номер клетки коня в ulong-значение битовой доски knightNr -> knightBits
2.Установить биты для всех возможных ходов коня
knightBits -> movesBits
3.Подсчитать количество единичных битов
movesBits -> movesCount
Первый шаг выполняется очень просто, нужно нулевой бит сдвинуть влево на указанное количество позиций.
Второй шаг немножко сложнее. Конь может пойти в 8 разных сторон. Мы будем считать эти смещения не «по горизонтали/вертикали», а по битовым позициям. То есть, считаем, на сколько позиций нужно сместить стартовый бит для каждого хода. Потом всё «складываем» операцией логического «или». Начнём перечислять ходы от левой стороны доски к правой:
Правда, классно!? К сожалению, по краям доски есть «чёрные дыры». Например, по этому алгоритму из клетки a4 (бит #24) можно попасть на клетку g2 (бит #14 = 24 - 10), этот прыжок является телепортацией сферического коня в вакууме сквозь чёрную дыру…
Чтобы исключить квантовый скачок коня через край доски, необходимо «отключать» крайние полосы после перемещения. Например, для ходов +6 и -10 (влево на две клетки) необходимо аннулировать полученные значения на вертикалях g и h, так как на этих вертикалях нельзя оказаться после перемещения «влево» на два хода.
Для этого нам понадобится 4 константы битовых сеток, в которых все биты установлены в 1, кроме указанных вертикалей. А именно:
Сверху и снизу шахматной доски тоже есть «чёрные дыры», которые полностью поглощают коня, поэтому отдельно их проверять не нужно.
Теперь алгоритм генерации допустимых ходов коня выглядит так:
Это работает очень (!) быстро. Пара тиков — и у нас битовая карта всех возможных похождений коня. Самое удивительное, что этот алгоритм отлично работает, даже если на доске расположено несколько коней. Он за один раз генерирует все возможные ходы для всех коней! Правда, здорово!?
Осталось подсчитать количество бит
Самый простой способ — сдвигать число на 1 бит вправо и считать единички. Сложность — 64 операции. Память — 64 бита.
Самый быстрый способ — создать кэш/массив на 65536 элементов, в котором записано количество битов для каждого индекса от 0 до 65535. И сложить 4 элемента из этого массива, которые соответствуют очередным 16-битовым сегментам числа. Сложность — 4 операции. Память — 64 килобайта.
Но мы рассмотрим самый хитрый способ, сложность которого равна количеству единичных битов в числе. Поскольку ходов не так много, то этот подход для нас будет самым оптимальным.
Для начала заметим, что вычитая единицу из числа, мы превращаем все «правые» нули в единицы, а самую крайнюю единицу в нуль:
Далее применим операцию логического «и» для этих чисел:
Как видите, таким хитрым способом мы сбросили в нуль самую правую единицу. Повторяем эту операцию, пока не получим в результате нуль. Сколько итераций, столько и единичных битов. Правда, здорово!?
Вот как записывается этот алгоритм полностью:
Задача решена!
У этой задачи есть другое, очень простое, чисто логическое решение: определить удалённость коня от края шахматной доски (в углу 2 хода, на краю 4 хода, в центре 8 ходов). Но если бы мы решали задачу «в лоб» таким образом, то не узнали бы про битовую доску, про вертикальные битовые маски, про алгоритм быстрого подсчёта единичных битов и про чёрные дыры для сферических коней в вакууме…
Теперь мы про это всё знаем. Жизнь шахматного программиста стала более богатой и осмысленной, ура!
Самостоятельное задание: сделайте то же самое для Шахматного короля.
