534. Weak Queens(弱皇后)
http://projecteuler.net/problem=534
傳統的八皇后問題(eight queens puzzle)是一個在8*8的棋盤上放置八個西洋棋皇后，
使得任意兩個皇后都無法威脅到彼此的著名問題。在准許解的形式能以旋轉或映射的方式
重現(譯注：視為不同解)，若為八個皇后則可以發現一共存在著92種不同形式的解。一般
的情況是要求在n*n棋盤上放置n個皇后的不同擺放方式的數目。例如，對於n=4，你可以
發現2種不同的擺放方式。
讓我們定義在n*n棋盤上的弱皇后(weak queens)為一件可以在水平方向移動任意方格數，
但在垂直或對角線方向只能移動最大n-1-w個方格數的新作品，w被稱為弱係數(weakness
factor)，0<=w<n。例如，一個在n*n棋盤上被放置在最底層方格且弱係數w=1的弱皇后無法
威脅到最高層的弱皇后，因為弱皇后必須移動n-1個垂直或對角線方向的方格數才能到達
那裡，但卻只能在這些方向上移動n-2個方格數。相較之下，弱皇后在水平方向卻毫無阻礙
，可以威脅到其所在列上的每一個方格，無關乎它在該列上的目前位置為何。
令Q(n,w)為可在n*n棋盤上擺放n個弱係數為w的弱皇后，使得沒有任意兩個皇后可以威脅
到彼此的方法數。例如，我們可以發現Q(4,0)=2，Q(4,2)=16且Q(4,3)=256
n-1
令S(n)= Σ Q(n,w)
w=0
你可以得到S(4)=276及S(5)=3347
試求出S(14)
--
經典的八皇后問題。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.71.37.180
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1448184544.A.499.html
※ 編輯: utomaya (219.71.37.180), 11/22/2015 17:34:20