Недавно я обнаружил канал Криса Рамзи на YouTube. Он волшебник. На своем канале он решает сумасшедшие головоломки, среди прочих магических вещей.
В этом видео Крис пытается победить IQ Tester. IQ Tester — простая настольная игра. Это треугольник с 15 возможными положениями. Игра начинается следующим образом: каждая позиция занята фишкой; Во-первых, вы бросаете один колышек на свой выбор. Затем вы должны попытаться получить минимальное количество колышков, прыгая по прямой (как в игре в шашки) и убирая колышек под прыжком.
Например, если мы назовем все узлы буквой и если позиции E и I имеют привязку, но позиция N свободна, действительным прыжком будет E привязка перемещается в Привязка N и I сбрасывается.
Спойлер: Крису нужно несколько попыток, прежде чем он сможет найти лучшее решение, которое состоит в том, чтобы получить только 1 колышек.
После просмотра этого видео я решил, что было бы неплохо решить проблему с помощью Пролога. Я нашел предлог, чтобы использовать свои пыльные знания Пролога!
Во-первых, мы можем записать количество возможных прыжков для каждой позиции:
Это было не очень интуитивно для меня (как и для Криса): наверное, мы все больше привыкли иметь больше возможных движений в середине доски.
Итак, моя идея решить эту проблему состоит в том, чтобы объявить все эти возможные движения фактами на Прологе; у нас будет 36 фактов.
Тогда у нас будет список с пустыми позициями. Давайте рассмотрим, что мы начинаем с удаления привязки J, поэтому мы начинаем с пустой позиции J.
Начните с: List = [J strong>]
Теперь у нас есть 2 возможных движения: (C → J) или (H → J).
Если мы выполняем (C → J), то List = [C, F].
Обратите внимание, что теперь у J есть привязка, и его нужно удалить из списка. Обратите внимание, что для каждого разрешенного перехода мы увеличиваем размер списка пустых узлов на 1.
При всем при этом довольно легко написать рекурсивную функцию на Прологе, которая всегда находит решение для заданной начальной игры.
Моя рекурсивная функция останавливается, печатая последовательность переходов, когда пустых узлов становится 14.
Еще одно возможное решение – подсчет колышков и остановка функции, когда их всего 1, но в этом случае нам нужно больше времени, чтобы проследить трассировку; хотя это более аккуратное решение.
Поэтому я закодировал эту функцию с целью получить совпадение как можно раньше, но это также можно сделать с помощью всего 2 списков и меньшего количества строк кода.
Это выглядит так:
play(?ListOccupiedNodes, ?ListEmptyNodes, []).
Пример:
?- play([j, a, c, b, e, f, g, h, i, k, l, m, n, o], [d], []).
Да (0.00s cpu, решение 1, возможно больше)
РЕШЕНИЕ:
[[a, d], [g, b], [f, d], [l, e], [c, h ], [н, д], [о, ж], [б, ж], [ж, д], [ж, б], [м, д], [б, ж], [к, д]]
Как вы, наверное, знаете, мы можем попросить Prolog получить больше результатов:
РЕШЕНИЕ:
[[a, d], [g, b], [f, d], [l, e], [c, h], [n, e], [o, f ], [б, ж], [ж, г], [ж, б], [м, г], [б, г], [к, г]]
РЕШЕНИЕ:
[[ а, г], [ж, б], [ж, г], [л, д], [в, з], [н, д], [о, е], [б, ж], [м, г], [ж, б], [ж, г], [б, г], [к, г]]
РЕШЕНИЕ:
[[а, г], [ж, б], [ж, г], [л, д], [в, з], [н, д], [б, ж], [м, г], [ж, б], [о, ж], [ф , г], [б, г], [к, г]]
РЕШЕНИЕ:
[[а, г], [г, б], [ж, г], [л, д] , [в, з], [н, д], [б, ж], [м, г], [о, е], [ж, б], [ж, г], [б, ж], [ k, d]]
РЕШЕНИЕ:
[[a, d], [g, b], [f, d], [l, e], [c, h], [n, e ], [б, ж], [о, ж], [ж, г], [ж, б], [м, д], [б, г], [к, г]]
РЕШЕНИЕ:
[[а, г], [ж, б], [ж, г], [л, д], [в, з], [н, д], [б, ж], [о, е], [м, г], [ж, б], [ж, г], [б, г], [к, г]]
РЕШЕНИЕ:
[[а, г], [ж, б], [ж, г], [л, д], [в, з], [н, л], [д, м], [к, з], [л, н], [о , m], [m, d], [b, g], [k, d]]
РЕШЕНИЕ:
[[a, d], [g, b], [f, d] , [л, д], [в, з], [н, л], [д, м], [л, н], [о, м], [к, з], [м, д], [ б , ж], [к, г]]
РЕШЕНИЕ:
[[а, г], [ж, б], [ж, г], [л, д], [в, з] , [н, л], [д, м], [л, н], [к, з], [о, м], [м, д], [б, ж], [к, д]] …
Итак, с помощью нескольких строк кода и алгебраической магии Пролога у нас есть все возможные решения IQ Tester, не впечатляет?
