[FGISC。Nanro] 未來開端

這次我們來談談八皇后問題。


＊先備知識
    首先我們先來了解一下西洋棋中的皇后
    皇后允許的攻擊範圍如下：
    ↖↑↗
    ←‧→  就是以那個點為中心，直線延伸的八方向
    ↙↓↘  詳細介紹可以看：http://140.112.12.122/chess/p2queen.htm

    另外，棋盤上欄列的定義如下

     ↓欄(column)
    ┌┬┬┬┬┬┬┬┐
    ├┼┼┼┼┼┼┼┤}列(row)
    ├┼┼┼┼┼┼┼┤
    ├┼┼┼┼┼┼┼┤
    ├┼┼┼┼┼┼┼┤
    ├┼┼┼┼┼┼┼┤
    ├┼┼┼┼┼┼┼┤
    ├┼┼┼┼┼┼┼┤
    └┴┴┴┴┴┴┴┘
＊八皇后問題介紹
    八皇后問題(The 8-Queens Problem)
    其實他是屬於n皇后問題(the N Queens Problem)中的一種，
    不過因為西洋棋盤是8*8的平面，所以八皇后問題就成了n皇后問題中的經典
    講完了介紹，那麼，這個問題的定義到底是什麼呢？
    簡單的來說如下：
    「給你八個皇后，要如何把他們相安無事地放在西洋棋盤中而不會受到彼此的攻擊？」
  //(1970年與1971年， E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。)

＊概念
    這個問題一般而言，我們使用遞迴來實做，其基本的概念與DFS大致相似：
    逐列將皇后放上棋盤，一步步嘗試各種可能性，也就是第一列放完→放第二列....
    而每列又有八欄位置可以選擇(當然，這八欄中一定有會被先前皇后攻擊的範圍)
    如果放到沒辦法放了，數量卻不到8，那麼就可以確認此條路無解，return回去
    看看之前哪條路還沒走過，逐步的試下去。
    以八皇后來說，本題會有92種解，扣掉鏡射旋轉，會有12種的基本解。
    //筆者才疏學淺，尚不懂如何扣掉鏡射選轉，歡迎先輩加以補充

＊技巧
    在筆者初次撰寫此程式時，便用了最直觀的方式：開一個二維陣列代表棋盤
    慢慢地放棋子上去，慢慢地把它標記掉
    但實際上，這樣會多出很多很多不必要的檢查程序
    所以我們可以觀察一下棋盤，其實因為皇后的攻擊範圍是很乾淨俐落的直線
    我們以列為基準來看：
    當該列已被放置皇后，那麼那列就不可能有其他的皇后。
    同樣地它放置的那行，以及他的兩個斜行也不可能有其他皇后
    筆者後來得知這即為「剪枝」的技巧，也就是把不可能的直接剪掉，
    用上面的概念時作，就不需要一格格的檢查
    另外，斜行的處理在實例中有提示。

＊實例
    模擬實例請看http://aikosenoo.googlepages.com/8queens.pdf

＊練習題
    ACM Q167 The Sultan's Successors
        http://luckycat.kshs.kh.edu.tw/homework/q167.htm
        很單純的八皇后，令Max去比較其和即可
    ACM Q750 8 Queens Chess Problem
        http://luckycat.kshs.kh.edu.tw/homework/q750.htm
        750與基礎的八皇后只差在搜尋下一個的技巧不同。
    ACM Q11085 Back to the 8-Queens
        http://luckycat.kshs.kh.edu.tw/homework/q11085.htm
        可先建表，之後逐一比較即可
        //這裡便可以看出有無排除旋轉鏡射的差距
        //排行最佳秒數為0.008，筆者為0.025

＊參考資料
    http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/EightQueen.htm
    http://140.112.12.122/chess/p2.htm

大概先介紹到這裡，有任何問題與建議歡迎提出:)