Рекурсия — чрезвычайно мощная техника программирования. К сожалению, большинство задач, особенно вводные, охватывают тривиальные примеры, такие как вычисление факториала (5! = 120), которое также можно выполнять итеративно. Таким образом, они не могут передать полезность рекурсии как способа разложения проблемы на повторяющийся набор шагов.

Рекурсию можно эффективно использовать для решения кажущихся сложными задач, основанных на интуиции, таких как решение судоку или поиск выхода из лабиринта. Компьютер решает эти проблемы, требующие интеллекта, памяти и опыта, просто перебирая все возможные решения и отбрасывая те, которые ведут в тупик. Этот метод программирования называется обратным отслеживанием.

В случае решения судоку это происходит примерно следующим образом:

  1. У нас есть действующая судоку? Да, тогда СТОП. Нет, тогда переходите к шагу 2.

2. Попробуйте ввести действительное число (это означает, что оно еще не существует в столбце строки или подсетке 3 x 3) в пустом квадрате. Перейти к шагу 3.

3. Судоку все еще действителен, и у нас есть другой номер, который мы можем попробовать? Да, затем перейдите к шагу 4. Нет, затем перейдите к шагу 5.

4. Если это так, (рекурсивно) попробуйте другое действительное число в другом пустом квадрате, т.е. перейдите к шагу 2.

5. Если нет, вернитесь и попробуйте другое действительное число в первом пустом квадрате, т.е. вернитесь к шагу 2, но попробуйте номер, который мы еще не пробовали.

Хотя может показаться тривиальным написать это на английском языке, на самом деле реализовать это с точными инструкциями, которые может выполнить компьютер, — непростая задача. Я постараюсь написать этот код с нуля в следующем посте, если найду время и мотивацию. А пока давайте обойдемся более простой задачей — ходом коня.

«Ход конем — это последовательность ходов коня на шахматной доске, при которой конь посещает каждую клетку ровно один раз». — Википедия

Это обычная задача первого или второго года обучения, которую задают студентам бакалавриата по информатике. Эту проблему можно решить с помощью поиска с возвратом, но более эффективное решение можно найти за O(n) (линейное) время, используя правило Варнсдорфа. (Вы можете прочитать о том, как это работает, нажав на ссылку выше.) Обратите внимание, что правило Варнсдорфа является эвристикой (не алгоритмом), т.е. оно не гарантирует работу во всех случаях или преобразованиях задачи, но оно работает хорошо для проблемы под рукой.

Я предпочитаю JavaScript, потому что мы действительно можем легко увидеть эту анимацию, которая довольно крута и легко реализуема с помощью JS. Мы не будем использовать какие-либо библиотеки или фреймворки, чтобы все было просто и прозрачно.

Давайте начнем!

Рисуем доску:

Все, что это делает, это создает клетчатый узор 8 x 8 и добавляет значок рыцаря в верхнем левом квадрате. Чередующийся шаблон работает, добавляя индекс строки и столбца, а затем чередуя в зависимости от того, является ли сумма нечетной или четной.

Далее нам нужно посчитать количество ходов нам нужна простая функция, которая пригодится для проверки того, что мы не покидаем шахматную доску, пытаясь сделать ход конем. Это просто проверка того, что индекс строки или столбца позиции коня находится в диапазоне от 0 до 7.

Теперь нам нужно создать изображение ниже, которое показывает количество ходов, которые конь может сделать по доске с заданного поля.

Обратите внимание, что из внешних квадратов выходит меньше ходов, и, выбирая первым квадрат с наименьшим количеством исходящих ходов, эвристика устраняет вероятность того, что конь застрянет во время обхода.

Последняя сложная задача, которая остается сейчас, — начать тур и рекурсивно завершить его.

Мы сначала проверяем, если мы сделали. Если нет, то мы находим следующий ход, находя клетку с наименьшим количеством исходящих ходов. Затем мы помечаем текущую клетку как занятую, устанавливая количество исходящих ходов на произвольно большое число (в данном случае 100), чтобы мы не возвращались к ней во время обхода. Затем нам нужно также уменьшить исходящие очки соседних клеток на 1, так как этот ход был сделан и, следовательно, текущая клетка недоступна для перемещения. Наконец, мы добавляем номер хода в текущую клетку, обновляем положение коня и готовимся к следующему ходу, снова вызывая функцию тура.

Чтобы заставить это анимироваться, все, что нам нужно сделать, это отложить вызов следующего тура на полсекунды, чтобы наш мозг мог обработать изменение положения коня как движение. Я знаю, я знаю - это техника анимации для бедняков, но добавление сложности анимации также не является целью этого поста. Оберните вызов в setTimeout, и мы готовы к работе!

И мы все сделали! Вот видео того, как это выглядит:

Я использовал рыцаря Пикачу, чтобы оживить обстановку! Надеюсь, вам понравился пост! Не стесняйтесь оставлять комментарии о том, что вы хотите, чтобы я рассказал дальше.

Исходный код: https://github.com/mihir478/knights-tour-js