這個其實是個很有名的問題,可是我直到最近才好好的(?)把這個題目給好好的做了一下。看來有人問問題還是比較有壓力快快的解出問題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 |
|
果然是很輕鬆就解決了XD,希望還有寫出下一個更快速的解法的機會:P