西洋棋的皇后，可以直走，橫走，或是斜走．是西洋棋中最為強力的一枚棋子．在正式的規則中只有一個．

而著名的的八皇后問題，則是要在一個標準的西洋棋盤上，放下八個皇后，而且皇后之間不會互相攻擊．例如以下是其中一種解法：

很明顯，答案一定不只這一種，那我們有沒有辦法利用演算法找出全部的解答呢？

這個問題的本質跟全排列問題差不多，決策樹的每一層表示棋盤的每列，每個節點可以做的選擇是，在一行的任意行放一個皇后．

讓我們來看看程式碼

    var strings: List<Array<Array<String>>> = ArrayList()

這邊對於檢查的issValid做了一點優化，因為我們皇后是從上往下一行一行放，所以只要檢查正上方，左上方，右上方的三個方向．

而backtrack就是在決策樹行走的指標，row跟col可以控制目前檢索的節點，而isValid可以進行剪枝．

當n=8的時候，就是著名的８皇后問題，數學家高斯窮極一生也沒有想出來．

但是在這個演算法之下，時間複雜度仍然是n^n+1的指數程度．而且沒有辦法優化了．在n=10的時候，就花費大量的時間了．

所以，如果題目改成只要找到一個解答，那我們就能夠修改演算法，不用把所有的答案算出來，就能夠大幅降低演算法的時間．看好題目的需求，來設計演算法，這個技巧以後也會常常用到．