Использование Джулии для решения головоломок — это весело!
Прежде чем я начну, я хотел бы сделать небольшое объявление. Если вас интересует язык Julia, приглашаем вас принять участие в 4-дневном кратком курсе Введение в Julia для науки о данных, который будет организован в Массачусетском технологическом институте с 17 по 20 января 2023 года. Приглашаются все желающие. Вы можете найти PDF с расписанием здесь.
Теперь мы можем вернуться к обычному ведению блога.
После моего недавнего поста о головоломке, покрывающей рыцаря меня попросили добавить еще один контент для решения головоломок. Поэтому сегодня я хочу представить вам, как можно решить задачу Путешествие рыцаря с помощью Джулии.
Код в этом посте тестировался на Julia 1.8.2 и Plots.jl 1.35.0.
Головоломка 🧩
Рассмотрим прямоугольную сетку. Ставим шахматного коня на одну из клеток этой сетки. Шахматный конь может ходить на две клетки по вертикали и на одну по горизонтали или на две клетки по горизонтали и на одну клетку по вертикали.
Мы хотим найти последовательность ходов коня, чтобы он посетил каждую клетку сетки ровно один раз и вернулся на исходную позицию.
Я покажу вам, как найти решение этой проблемы (или узнать, что задача невыполнима) для произвольных размеров сетки. Далее мы увидим решение для стандартной шахматной доски с 8 рядами и 8 столбцами.
Код 🧑💻
В решении ключевым объектом, который мы будем отслеживать, является grid
. Это будет матрица, хранящая последовательные ходы коня. В этой матрице запись 0
означает, что клетка еще не посещала ее, а положительная запись указывает номер хода, когда клетка была посещена. Итак, число 1
— это начальная позиция коня.
Чтобы отслеживать местоположение рыцаря в сетке, мы будем использовать 2-кортеж, содержащий текущую строку и столбец местоположения рыцаря. В коде он называется p
.
Сначала мы создаем вспомогательную функцию listoptions
. Он принимает grid
и p
в качестве аргументов и возвращает вектор возможных ходов коня с p
на еще не посещенные поля. Вот его реализация:
listoptions(grid, p) = [p .+ d for d in ((1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)) if get(grid, p .+ d, -1) == 0]
Обратите внимание, как хорошо в этом случае работает функция get
. Мы используем его для получения значения -1
в случае, если p .+ d
не находится в пределах grid
(поэтому такие недопустимые ходы отбрасываются).
Пришло время представить ключевую функцию, которая будет обрабатывать обход grid
рыцарем:
function knight_jump!(grid=fill(0, 8, 8), p=(1, 1), i=1) grid[p...] = i if i == length(grid) p1 = Tuple(findfirst(==(1), grid)) return extrema(abs, p .- p1) == (1, 2) ? grid : nothing end v = listoptions(grid, p) sort!(v, by=np -> length(listoptions(grid, np))) for np in v knight_jump!(grid, np, i + 1) !== nothing && return grid end grid[p...] = 0 return nothing end
Позвольте мне объяснить, как это работает. Аргументы grid
и p
уже обсуждались. Дополнительный аргумент i
хранит номер хода. Функция возвращает grid
, если найдено допустимое решение, и nothing
, если приемлемое решение не найдено. Этот инвариант имеет решающее значение, так как мы будем использовать его для выполнения поиска в глубину действительного рыцарского тура.
Сначала мы устанавливаем grid
в позиции p
на i
, чтобы записать текущее размещение рыцаря.
Далее в i == length(grid)
проверке мы проверяем, попали ли мы в последнее свободное место на сетке. Если это так, мы проверяем, является ли текущая позиция p
прыжком конем от начальной позиции коня (обозначается p1
в коде). Если это так, мы возвращаем grid
. В противном случае тур недействителен и мы возвращаем nothing
.
Если наш тур еще не завершен, мы сохраняем в векторе v
возможные ходы, которые мы можем сделать дальше. Теперь применяется важная часть алгоритма. Сортируем v
по правилу Варнсдорфа, то есть ставим квадраты с наименьшим количеством перемещений вперед перед вектором. Затем мы рекурсивно посещаем их и пытаемся решить головоломку. Если нам это удастся, то есть когда рекурсивный вызов knight_jump!
не вернет nothing
, мы закончим и вернем результат. Если мы терпят неудачу для всех значений в v
, это означает, что попытка посещения p
была неверным выбором. В этом случае нам нужно сбросить grid
так, чтобы в позиции p
было 0
и вернуть nothing
(чтобы сигнализировать о проблеме).
Результат ❓
Давайте проверим, как решение выглядит на сетке 8x8 (которая используется по умолчанию в нашем коде):
julia> res = knight_jump!() 8×8 Matrix{Int64}: 1 16 51 34 3 18 21 36 50 33 2 17 52 35 4 19 15 64 49 56 45 20 37 22 32 55 44 63 48 53 42 5 61 14 57 54 43 46 23 38 28 31 62 47 58 41 6 9 13 60 29 26 11 8 39 24 30 27 12 59 40 25 10 7
Сначала мы видим, что решение действительно найдено (поскольку мы не получили nothing
от вызова). Во-вторых, визуальный осмотр решения показывает, что решение действительно правильное.
Давайте дополнительно визуализируем его, чтобы упростить анализ. Сначала мы преобразуем матрицу res
в вектор moves
последовательных расположений рыцарей, хранящихся в виде кортежей. Затем мы добавляем первое местоположение в конец этого вектора (так как у нас есть цикл). Наконец, мы рисуем шахматную доску с последовательными ходами коня, представленными линиями.
julia> using Plots julia> moves = Tuple.(CartesianIndices(res)[sortperm(vec(res))]) 64-element Vector{Tuple{Int64, Int64}}: (1, 1) (2, 3) (1, 5) ⋮ (6, 3) (4, 4) (3, 2) julia> push!(moves, first(moves)) 65-element Vector{Tuple{Int64, Int64}}: (1, 1) (2, 3) (1, 5) ⋮ (4, 4) (3, 2) (1, 1) julia> plot(getindex.(moves, 1), getindex.(moves, 2); legend=false, size=(400, 400), color=:blue, marker=:o, markerstrokecolor=:blue, xlim=(0.5, 8.5), ylim=(0.5, 8.5), minorticks=2, minorgrid=true, grid=false, xticks=(0:9, [""; 'A':'H'; ""]), yticks=0:9, minorgridalpha=1.0, showaxis=false)
Результирующий график выглядит следующим образом:
Домашнее задание 📝
Поскольку пост я начал с анонса краткого курса, позвольте мне ненадолго переключиться в режим чтения лекций. Для этой головоломки у меня есть следующие упражнения для тренировки мышцы Юлии:
- Проверьте, не нужно ли нам когда-нибудь вернуться в алгоритм, так как, возможно, мы решим проблему с первой попытки благодаря правилу Варнсдорфа?
- Измеряйте производительность кода.
- Есть ли у вас идеи, как можно улучшить его скорость (подсказка: подумайте, как можно уменьшить количество аллокаций и избежать сортировки)
- Проверьте, что произошло бы, если бы мы не использовали правило Варнсдорфа. Два естественных правила-кандидата: посещение квадратов в случайном порядке и посещение квадратов в порядке, полученном функцией
listoptions
. - Предлагаемое решение использует рекурсию. Поскольку у Джулии есть ограничение на глубину рекурсии, код не будет работать должным образом для больших сеток. Сначала найдите этот предел. Во-вторых, подумайте, как бы вы могли переписать программу, чтобы в ней не использовалась рекурсия.
Выводы
Надеюсь, вам понравилась головоломка и представленное решение. Если вы застряли на каких-либо частях домашнего задания, мы можем обсудить их в январе 2023 года в MIT на кратком курсе или просто связаться со мной в Julia Discourse или Julia Slack, и я с удовольствием отвечу на ваши вопросы.
Первоначально опубликовано на https://bkamins.github.io 11 ноября 2022 г.