Можете ли вы решить загадку восьми королев во время компиляции?
Выберите любой подходящий формат вывода.
Меня особенно интересует решение для метапрограммирования шаблонов на C ++, но вы можете использовать языки с похожими конструкциями, как, например, система типов Haskell.
В идеале ваша метапрограмма будет выводить все решения. Нет жесткого кодирования.
puzzle-solver
compile-time
Р. Мартиньо Фернандес
источник
источник
Ответы:
Моя метапрограмма находит все 92 решения. Они печатаются как сообщения об ошибках:
Это означает, что первая королева должна быть помещена в y = 1, вторая в y = 5, третья в y = 8 и так далее.
Во-первых, некоторые полезные мета-функции:
Затем две интересные мета-функции (обратите внимание на единственное и множественное число):
Переменная
queensхранит координаты y королев, размещенных на доске до сих пор. В следующих трех переменных хранятся строки и диагонали, которые уже заняты ферзями.xиyдолжно быть само за себя.Первый аргумент для
if_then_elseпроверки, заблокирована ли текущая позиция. Если это так, рекурсия останавливается, возвращая (бессмысленный) результат 0. В противном случае ферзь помещается на доску, и процесс продолжается со следующего столбца.Когда х достигает 8, мы нашли решение:
Поскольку
printшаблон не имеет членаsolution, компилятор генерирует ошибку.И наконец, чтобы начать процесс, мы проверяем
valueчлена пустой доски:Полная программа может быть найдена в Ideone .
источник
Я придумал решение, которое использует систему типов Haskell. Я немного погуглил существующее решение проблемы на уровне значений , немного изменил его, а затем поднял до уровня типа. Потребовалось много изобретений. Мне также пришлось включить несколько расширений GHC.
Во-первых, поскольку на уровне типов недопустимы целые числа, мне нужно было заново изобретать натуральные числа, на этот раз в виде типов:
Алгоритм, который я адаптировал, делает сложения и вычитания на натуральных объектах, поэтому мне пришлось их заново изобретать. Функции на уровне типов определяются с использованием классов типов. Это требует расширений для нескольких классов типов параметров и функциональных зависимостей. Классы типов не могут «возвращать значения», поэтому мы используем для этого дополнительный параметр, аналогично PROLOG.
Рекурсия реализована с помощью утверждений классов, поэтому синтаксис выглядит немного назад.
Далее были логические:
И функция для сравнения неравенства:
И списки ...
ifs также отсутствуют на уровне типа ...И с этим все вспомогательные механизмы, которые я использовал, были на месте. Время заняться самой проблемой!
Начиная с функции для проверки правильности добавления ферзя на существующую доску:
Обратите внимание на использование утверждений класса для получения промежуточных результатов. Поскольку возвращаемые значения на самом деле являются дополнительным параметром, мы не можем просто вызывать утверждения напрямую друг от друга. Опять же, если вы использовали PROLOG раньше, вам может показаться, что этот стиль немного знаком.
После того, как я сделал несколько изменений, чтобы убрать необходимость в лямбдах (которые я мог бы реализовать, но я решил уйти на другой день), вот как выглядело оригинальное решение:
mapявляется функцией более высокого порядка. Я думал, что реализация мета-функций более высокого порядка будет слишком хлопотной (опять же лямбда-выражения), поэтому я просто выбрал более простое решение: так как я знаю, какие функции будут отображаться, я могу реализовать специализированные версииmapдля каждой, чтобы они не были функции высшего порядка.И последняя мета-функция может быть написана сейчас:
Все, что осталось, это какой-то драйвер, чтобы уговорить механизм проверки типов для выработки решений.
Предполагается, что эта метапрограмма работает на контроллере типов, поэтому можно запустить
ghciи запросить типqueens eight:Это довольно быстро превысит установленный по умолчанию предел рекурсии (это жалкие 20). Чтобы увеличить этот предел, нам нужно вызвать
ghciс-fcontext-stack=Nопцией, гдеNжелаемая глубина стека (N = 1000 и пятнадцать минут недостаточно). Я еще не видел этот прогон до завершения, так как он занимает очень много времени, но мне удалось подойти к немуqueens four.На Ideone есть полная программа с некоторыми механизмами для красивой печати типов результатов, но они
queens twoмогут работать только без превышения ограничений :(источник
С, через препроцессор
Я думаю, что комитет ANSI сделал осознанный выбор, чтобы не расширять препроцессор C до точки завершения Тьюринга. В любом случае, он не достаточно мощный, чтобы решить проблему восьми королев. Не в общем смысле.
Но это можно сделать, если вы хотите жестко закодировать счетчики циклов. Конечно, нет реального способа зацикливания, но вы можете использовать самостоятельное включение (через
#include __FILE__), чтобы получить ограниченную рекурсию.Несмотря на ужасающее количество повторяющегося контента, позвольте мне заверить вас, что он действительно решает проблему восьми королев с помощью алгоритма. К сожалению, единственное, что я не смог сделать с препроцессором, - это реализовать общую структуру данных стека. В результате мне пришлось жестко кодировать значение,
iгде бы оно ни использовалось, чтобы выбрать другое значение для установки. (В отличие от извлечения значений, что может быть сделано полностью в целом. Вот почему#ifв верхней части файла, который решает, можно ли добавить королеву в текущей позиции, не нужно повторять восемь раз.)Внутри кода препроцессора,
iиjпоказывают текущее положение рассматривается, в то времяr,pиnотслеживать, какие ранги и диагонали в настоящее время недоступны для размещения. Тем не менее, онiтакже удваивается как счетчик, отмечающий текущую глубину рекурсии, так что на самом деле все другие значения фактически используют i как своего рода индекс, так что их значения сохраняются при возобновлении из рекурсии. (А также из-за серьезной трудности изменения значения символа препроцессора без его полной замены.)Скомпилированная программа печатает все 92 решения. Решения встроены непосредственно в исполняемый файл; вывод препроцессора выглядит так:
Это может быть сделано, хотя это явно не должно быть.
источник
Вот решение C ++ 11 без каких-либо шаблонов:
Решение закодировано в виде десятичных цифр, как в ответах FredOverflow. GCC 4.7.1 компилирует вышеуказанный файл в следующий источник сборки с
g++ -S -std=c++11 8q.cpp:Значение символа
places- 84136275, т. Е. Первая ферзь находится на а8, вторая на б4 и т. Д.источник
Шаблон C ++, только с одним шаблоном класса определяется:
поэтому сообщение об ошибке будет выглядеть так:
ошибка C2440: «приведение типа»: невозможно преобразовать из «int» в «char [15863724]»
источник