Использование Джулии для решения головоломок — это весело!

Прежде чем я начну, я хотел бы сделать небольшое объявление. Если вас интересует язык 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 г.