Реализация Восемь (не атакующих) рыцарей с использованием Prolog

Question

В настоящее время я работаю над алгоритмом, который пытается найти все решения на вопрос: «Сколько способов разместить 8 Рыцарей на плате 8x8 в таком что никто из них не может атаковать друг друга? "

Теперь я смог применить решение 8 Queens 8x8 для аналогичных проблем в отношении 8 Bishops и 8 Rooks из алгоритма 8 Queens, который я нашел в Интернете. (Поскольку епископы и ладьи перемещаются либо по диагонали, либо по горизонтали/по вертикали по всей доске, это очень похоже на алгоритм Квинса)

Вот что я до сих пор.

solution([]). 
solution([X/Y|Others]) :- 
    solution(Others), 
    member(Y, [1, 2, 3, 4, 5, 6, 7, 8]), 
    noattack(X/Y, Others). 


noattack(_,[]). 
noattack(X/Y, [X1/Y1|Others]):- 
     Y1 - Y =\= 2, X1 - X =\= 1 
    ; Y - Y1 =\= 2, X1 - X =\= 1 
    ; Y1 - Y =\= 2, X - X1 =\= 1 
    ; Y - Y1 =\= 2, X - X1 =\= 1 
    ; Y1 - Y =\= 1, X1 - X =\= 2 
    ; Y - Y1 =\= 1, X1 - X =\= 2 
    ; Y1 - Y =\= 1, X - X1 =\= 2 
    ; Y - Y1 =\= 1, X - X1 =\= 2 
    ; noattack(X/Y, Others).  

template([1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8]). 

main :- 
    open('knights.out',write,ID), 
    ( (template(X), solution(X), write(ID,X), nl(ID), fail) 
     ; close(ID) 
    ). 

В принципе, я более или менее моделируется этот алгоритм выключения стандартного алгоритма 8-Квинс Пролога, но вместо сравнения Y и Y1 для потенциальных «горизонтальных» потенциальных атак и Y1-Y = \ = X1 - X и Y1-Y = \ = X - X1 для диагональных потенциальных атак, как я это делал с королевой, на этот раз я сравниваю каждое точное местоположение следующего возможного пятна с тем, где может атаковать нынешний рыцарь, и объединяет его с чем-то, что объединяется с noattack. (Извините, будучи студентом CS, сфокусированным на Python, я действительно сосать, объясняя это. Если вы не встанете до этого момента, пожалуйста, проверьте http://www.javaist.com/blog/2008/11/06/eight-queens-problem-in-prolog/). Он отлично справляется с объяснением, что такое алгоритм 8 Queens.

Теперь стандартный способ запускать это будет.

?- template(A), solution(A). 

, а затем на первом объединении, нажать «» для того, чтобы распечатать все решения в gprolog или swiprolog интерактивной консоли. Для 8 ферзей существует только 32 решения, поэтому можно просто перейти по строкам в последовательности обратного отслеживания и подсчитать 32 для проверки алгоритма. Но для задачи 8 Рыцарей было бы 379978716 действительных решений (согласно http://oeis.org/search?q=nonattacking%20knights&sort=&language=&go=Search). Именно в этом возникает «основная» функция в конце. Это в основном выводит каждое объединение в файл под названием «knights.out», поэтому я могу открыть его в редакторе кода, чтобы увидеть, есть ли строки 379978716.

Выполнение некоторых вычислений Я подсчитал, что выходной файл должен быть где-то около 14 концертов, но мой алгоритм в настоящее время производит файл размером более 70G (возможно, это может быть бесконечный цикл, но мой Linux Partitian может хранить только 70G, не знаю). Но в любом случае этот алгоритм несколько раз подсчитывается, и я не знаю, как это исправить.

Любая помощь будет оценена по достоинству. (Для Brevity я не загрузил код для восьми епископов и восьми ладьи, но если вам интересно, я держу их здесь: https://github.com/gilgameshskytrooper/eightqueens)

Answer 1

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

noattack(X/Y, [X1/Y1|Others]):- 
    Y1 - Y =\= 2, X1 - X =\= 1; 
    Y - Y1 =\= 2, X1 - X =\= 1; 
    Y1 - Y =\= 2, X - X1 =\= 1; 
    Y - Y1 =\= 2, X - X1 =\= 1; 
    Y1 - Y =\= 1, X1 - X =\= 2; 
    Y - Y1 =\= 1, X1 - X =\= 2; 
    Y1 - Y =\= 1, X - X1 =\= 2; 
    Y - Y1 =\= 1, X - X1 =\= 2; 
    noattack(X/Y, Others). 

Вы могли бы просто использовать абс и написать:

noattack(X/Y, [X1/Y1|Others]):- 
    Y =\= Y1, 
    abs(Y1-Y) =\= abs(X1-X), 
    noattack(X/Y,Others). 

В приведенном выше предиката нам не нужно писать: Х = \ = X1, так как из-за шаблона мы предполагаем, что X отличны.

Это не отвечает на вопрос, но это намного лучший способ написать его, и он не вписывается в комментарий ...