八皇后老問題

八皇后是個很簡單的老問題,用 Erlang 解起來特別快。

問題是在 8×8 棋盤要擺上八只皇后,使皇后彼此不互相攻擊。皇后棋是西洋棋最威猛的一隻,攻擊範圍包含了四方和四條對角線,也就是米字形。

解決這個問題,首先可以將皇后可能站的位置編碼。想像任何一盤已經把皇后擺好的棋盤,從一邊望去,必定是每一行只有一只皇后、每列只有一只皇后。我們可以用一列列表就把這種情況表達出來:

        [3,6,2,7,5,1,8,4]

列表的每一格表示獨一的行,格子中的數字彼此不同,於是每一格的數字表示獨一的列。在 Erlang 語言可以用一句產生一列各自為獨一的數字:

        lists:seq(1,8)        % Generate [1,2,3,4,5,6,7,8]

但 [1,2,3,4,5,6,7,8] 這一列數字表示的皇后是互相攻擊的,要想辦法打亂數字的順序,變成像 [3,6,2,7,5,1,8,4] 的情況。於是,需要有一個排列函數。

排列函數很好寫,像以下這樣:空序列的排列只有一種空序列的樣子,而任何其他序列的排列,是先把每一個數字拿出來做頭,其他部份取排列分別跟頭相接。利用 Erlang 的列表解析 (List Comprehension) 語法可以很快寫好。

        perms([]) ->
            [[]];
        perms(Xs) ->
            [ [H|T] || H <- Xs,
                        T <- perms(Xs--[H]) ].

以上產生的任何一種排列情況,都已經把皇后向四方攻擊的可能性排除掉了。但還需要檢查對角線攻擊的情況。我用 attack_diag/2 和 attack_diag/3 檢查對角線攻擊方式,檢查在第一行的某個數字位置是否會攻擊第二、三、四及之後每一行的數字位置。 attack_diag/2 的二個參數,第一個參數是第一行的數字,第二個參數是第二、三行及之後每一行的數字。 attack_diag/3 是 attack_diag/2 的延伸,分別討論向斜上攻擊和向斜下攻擊二種情況,增加了一個參數表示上下方向。

attack_diag(M, Ns) ->
    attack_diag(M, up, Ns) ++ attack_diag(M, down, Ns).
attack_diag(_, _, []) ->
    [];
attack_diag(M, up, [N|_]) when M-1 =:= N ->
    [N];
attack_diag(M, down, [N|_]) when M+1 =:= N ->
    [N];
attack_diag(M, up, [_|Ns]) ->
    attack_diag(M-1, up, Ns);
attack_diag(M, down, [_|Ns]) ->
    attack_diag(M+1, down, Ns).

使用 attack_diag/2 的效果是,可以檢查出第一行的數字攻擊到之後各行的哪些數字。處理結果如下例:

> eightq:attack_diag(3, [1,2,6,4,7]).
[6]
> eightq:attack_diag(3, [4,1]).
[1,4]
> eightq:attack_diag(3, [6,2,7,5,1,8,4]).
[]

有了 attack_diag/2 之後,可以將檢查規則加入之前的 perms/1 ,修改成 perms_allow/1 :

        perms_allow([]) ->
            [[]];
        perms_allow(Xs) ->
            [ [H|T] || H <- Xs,
                        T <- perms_allow(Xs--[H]),
                        attack_diag(H,T) == []  ].

最後加上程式的開頭:

        -module(eightq).
        -export([start/1]).

        start(N) ->
                perms_allow(lists:seq(1,N)).

執行情況:

> eightq:start(8).
[[1,5,8,6,3,7,2,4],
 [1,6,8,3,7,4,2,5],
 [1,7,4,6,8,2,5,3],
 [1,7,5,8,2,4,6,3],
 [2,4,6,8,3,1,7,5],
 [2,5,7,1,3,8,6,4],
 [2,5,7,4,1,8,6,3],
 [2,6,1,7,4,8,3,5],
 [2,6,8,3,1,4,7,5],
 [2,7,3,6,8,5,1,4],
 [2,7,5,8,1,4,6,3],
 [2,8,6,1,3,5,7,4],
 [3,1,7,5,8,2,4,6],
 [3,5,2,8,1,7,4,6],
 [3,5,2,8,6,4,7,1],
 [3,5,7,1,4,2,8,6],
 [3,5,8,4,1,7,2,6],
 [3,6,2,5,8,1,7,4],
 [3,6,2,7,1,4,8,5],
 [3,6,2,7,5,1,8,4],
 [3,6,4,1,8,5,7,2],
 [3,6,4,2,8,5,7|...],
 [3,6,8,1,4,7|...],
 [3,6,8,1,5|...],
 [3,6,8,2|...],
 [3,7,2|...],
 [3,7|...],
 [3|...],
 [...]|...]
>
廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Fun。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s