有關國際象棋的問題很多,八皇後問題就是其中相當著名的一個。在 8×8 的國際象棋棋盤中,放入 8 個皇後,使它們不互相攻擊,共有多少種方法呢?

國際象棋中皇後的威力巨大,攻擊範圍是同一行、同一列以及同一斜行,是以,符合條件的 8 個皇後必須都不在同一行、同一列或者同一斜行上。
由于每一行中隻能放入一個皇後,是以可以使用一個長度為 8 的序列,依次設入每行中皇後所在的列數,以此來表示皇後的放置狀态。當某一行還沒有置入皇後時,即該行沒有一列上有皇後,記為 0;而每次置入新的皇後時,如果列數不是序列中已有的,就說明沒有皇後在同一列中。這樣,不同行、不同列就能很容易的判定了。
那麼,在置入新的皇後時,就隻需要保證它與已有的皇後都不在同一斜行上了。如果一個皇後在 m 行 k 列,那麼在 m+n 行,最多隻有兩個位置和它在同一斜行上,而且這兩個位置距離它的橫向距離等于縱向距離,也就是說最多
隻有 (m+n,k+n) 和 (m+n,k-n) 這兩個位置與這個皇後在同一斜行上。
這樣,隻要把每個皇後在每一行的所有情況都檢查一遍,就可以知道共有多少種情況滿足要求了。
經過上面的抽象分析,我們隻需要在集算器中,通過循環計算來完成這些判斷就行了。具體代碼如下:
第 1 行,A1 就是記錄皇後放置狀态的序列;B1 定義了一個變量 i,用來在計算時記錄目前放置皇後的行。
第 2 行代碼,每循環一次,就把目前行的皇後下移 1 列,用這樣的方法周遊行中每個位置。
第 3 行代碼,如果棋子移到了第 9 列,說明目前行的棋子已經完成了所有位置的循環,此時,應該把目前行的記錄複原為 0,并将 i 減 1,可以傳回去繼續上一行的周遊;特别的,當第 1 行也全部循環後,說明完成了周遊,此時 i 被設為 0,停止循環。
第 4 行代碼,在移動第 1 行皇後時,可以不用判斷,直接開始放置第 2 個皇後。
第 6 行代碼,判斷已放好的皇後中,是否存在同一列的;
第 7 行代碼,判斷已放好的皇後中,是否存在同一斜行的。如果既沒有同一列的,也沒有同一斜行的,就可以繼續放置下一行的皇後了。
如果此時 8 個皇後都放置成功,則在第 9 行代碼中記錄下目前每個皇後的位置。
經過計算,A10 中結果如下:
可以在 C1 中檢視具體結果:
當然,還可以用經典的遞歸方式解決這個問題,集算器中遞歸調用子函數的方法的代碼如下:
在 A2 定義的子程式中,在一個新行中嘗試放置皇後,在 B2 中循環每一個可能的列。
A5 中的子程式用來判斷新的一行是否可以使用指定的列,其中在 C5 中檢視是否本列已存在皇後,第 6 行檢視是否已有皇後在同一斜行,在這樣的情況下說明不能放置。如果某一列可以放置,則判斷是否 8 個皇後都放置成功,如果已全部設定成功則記錄在 C1 中。如果未放置滿,則遞歸調用 A2 中的子程式,繼續在下一行放置。這種方法的代碼更易了解,計算結果與前面的方法是相同的。