這個其實是個很有名的問題，可是我直到最近才好好的(？)把這個題目給好好的做了一下。看來有人問問題還是比較有壓力快快的解出問題XD

從西洋棋說起

這是一個由西洋棋來的問題，問說是否可以找到一種放置八個皇后的方法，使得八個皇后不會相互吃到對方，也就是說整個棋盤會被八個皇后給蓋住。

在軍中的時候，其實有跟資工的同梯談過這個問題，他說這種題目通常有兩種重要的取向，一個是最快解出一組解，另一個是最快解出所有的解。

不過因為我用的語言不是C/C++，感覺也不用跟別人爭什麼最快，就開開心心的解就好了。

八城堡問題？

我在公車上想這個問題的時候，第一個跑入腦中的就是「八城堡問題」。我得說，可能真的找不到這個名字的問題，不過我覺得是個很好的簡化。

其實我們做的事情就是將皇后換成了城堡，不過這個問題就簡單很多了，因為只要是一個一到八的排列就是解答了。例如給出[1, 2, 3, 4, 5, 6, 7, 8]，就對應到(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8)這八個點，很明顯就是個八城堡的解。我們得到了一組八城堡的解，也就快得到一組八皇后的解了，因為我們只要去看檢查對角線的方向，是不是有蓋到對方，就可以知道是不是一組八皇后的解了。

解法

有了想法，實現就不難，下面附上我的ruby寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env ruby
require "set"

def layout(perm)
  (0 ... 8).each do |i|
    perm.each do |x|
      print i == x ? ' Q' : ' .'
    end
    puts
  end
end

Array(0 ... 8).permutation(8) do |perm|
  if Array(0 ... 8).map { |i| perm[i] - i }.to_set.size == 8 &&
     Array(0 ... 8).map { |i| perm[i] + i }.to_set.size == 8
    layout(perm)
    break
  end
end

果然是很輕鬆就解決了XD，希望還有寫出下一個更快速的解法的機會:P