使用Prolog實現八（非攻擊）騎士

我目前正在研究一種算法，該算法試圖找到問題的所有解決方案，「在這樣的一個8x8板上放置8個騎士有多少種方法？他們都不會互相攻擊嗎？「使用Prolog實現八（非攻擊）騎士

現在我已經能夠應用8皇后8x8板解決方案來解決我在網上找到的8皇后算法中8個主教和8個車的類似問題。（由於Bishops和Rooks在對角線方向上或水平/垂直方向移動，這與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皇后的Prolog算法的，但不是比較Y和Y1爲潛在的「水平」潛在的攻擊和Y1-Y = \ = X1 - X而Y1-Y = \ = X-X1對於對角線潛在的攻擊，就像我對皇后所做的一樣，這次我將下一個可能點的每個確切位置與當前騎士可以攻擊的任何位置進行比較，並將其統一爲某種與之相統一的東西noattack。（對不起，作爲一名Python專業的CS學生，我真的很想解釋這一點，如果你沒有起牀，請查看http://www.javaist.com/blog/2008/11/06/eight-queens-problem-in-prolog/）他很好地解釋了8皇后算法是什麼。

現在運行這個的標準方法是。

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

，然後在第一個統一的，按「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，所以我不會不知道）。但無論哪種方式，這種算法是雙重計數幾次，我不知道如何解決這個問題。

任何幫助，將不勝感激。（爲了簡潔起見，我沒有上傳八主教和八個白嘴鴉的代碼，但是如果您有興趣，我可以將它們保留在這裏：https://github.com/gilgameshskytrooper/eightqueens）

來源

2016-11-06 Gilgamesh Skytrooper

14GB？你可以在Prolog中計算答案！你甚至可以算出解決方案。 '圖書館（clpfd）'是一種方式！ – false

你需要額外的圓括號圍繞你的複雜情況！你正在列舉幾乎所有的可能性！ – false

我完全不理解的一件事：你可以將32名騎士置於8x8棋盤上，而不會攻擊另一名棋子。那麼，爲什麼你只想放置8個？ – false

您在註釋中指出的解決方案不正確。我會建議一些改進：相反的：

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).

你可以簡單地使用ABS和寫：

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

在上面的謂詞，我們並不需要這樣寫：X = \ = X1，因爲由於模板我們假定X是不同的。

這並不回答這個問題，但這是一個更好的方式來寫它，它不適合在評論中...

來源

2016-11-06 09:43:17 coder

OP的解決方案**不是正確的！請使用'listing'來查看爲什麼 – false

要告訴你真相我沒有看到它，因爲我認爲他把所有案件沒有腹肌，但你是對的，我會編輯這部分... – coder

@false如果你聲稱我的答案是不正確的，我同意。告訴我輸出應該在14 GB左右，但是我得到的文件要大得多。當你說使用列表，你的意思是有一個prolog謂詞/函數可以幫助嗎？ –

使用Prolog實現八（非攻擊）騎士

回答

相關問題