2008年2月12日 星期二

Problem 167 The Sultan's Successors,權位的繼承者

這個題目的重點在你會不會解西洋棋的八個皇后問題。也就時在西洋棋盤(8x8)上,放八個皇后,八個皇后互不侵犯,誰也不能吃誰。如果學過演算法,這個題目應該不算難。在蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊,2004年),第五章介紹回溯方法的應用。所以只要完成該n-queen的程式碼,就可以將所有八個皇后全部的編排位置排出來,排出來之後,再以題目提供的數字,將皇后所佔領的格子中的數字加總,將最大的加總保留下來,並印出,就大功告成了。

主程式呼叫的部份如下,BSIZE為8。queens是將皇后在第一列的位置排出來後,進行呼叫,其中也用到了遞迴。
for (j=0;j<BSIZE;j++)
{
column[0]=j;
queens(0);
}
printf("%5d\n", max);

p167題目連結
回ACM題庫目錄
回首頁

沒有留言: