說明
西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在棋盤上，1970年與1971年， E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。解法
關於棋盤的問題，都可以用遞迴求解，然而如何減少遞迴的次數？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就不用再檢查了，這個方法稱為分支修剪。
所以檢查時，先判斷是否在已放置皇后的可行進方向上，如果沒有再行放置下一個皇后，如此就可大大減少遞迴的次數，例如以下為修剪過後的遞迴檢查行進路徑：
八個皇后的話，會有92個解答，如果考慮棋盤的旋轉，則旋轉後扣去對稱的，會有12組基本解。
實作：C Java Python Scala Ruby
#include <stdio.h>
#include <stdlib.h>
#define N 8
// int num; // 解答編號
void backtrack(int* column, int* rup, int* lup, int* queen, int); // 遞迴求解
int main(void) {
//num = 0;
int column[N+1]; // 同欄是否有皇后，1表示有
int rup[2*N+1]; // 右上至左下是否有皇后
int lup[2*N+1]; // 左上至右下是否有皇后
int queen[N+1] = {0};
int i;
for(i = 1; i <= N; i++)
column[i] = 1;
for(i = 1; i <= 2*N; i++)
rup[i] = lup[i] = 1;
backtrack(column, rup, lup, queen, 1);
return 0;
}
void printQueen(int* queen) {
int x, y;
// printf("\n解答 %d\n", ++num);
for(y = 1; y <= N; y++) {
for(x = 1; x <= N; x++) {
printf(" %c", queen[y] == x ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
}
void backtrack(int* column, int* rup, int* lup, int* queen, int i) {
if(i > N) {
printQueen(queen);
}
else {
int j;
for(j = 1; j <= N; j++) {
if(column[j] == 1 &&
rup[i+j] == 1 && lup[i-j+N] == 1) {
queen[i] = j;
// 設定為佔用
column[j] = rup[i+j] = lup[i-j+N] = 0;
backtrack(column, rup, lup, queen, i+1);
column[j] = rup[i+j] = lup[i-j+N] = 1;
}
}
}
}
public class Queen {
// 解答
private int[] queen = new int[8+1];
// 同欄是否有皇后，1表示有
private int[] column = new int[8+1];
// 右上至左下是否有皇后
private int[] rup = new int[2*8+1];
// 左上至右下是否有皇后
private int[] lup = new int[2*8+1];
public void backtrack() {
for(int i = 1; i <= 8; i++)
column[i] = 1;
for(int i = 1; i <= 2*8; i++)
rup[i] = lup[i] = 1;
backtrack(1);
}
private void backtrack(int i) {
if(i > 8) {
print();
}
else {
for(int j = 1; j <= 8; j++) {
if(column[j] == 1 &&
rup[i+j] == 1 &&
lup[i-j+8] == 1) {
queen[i] = j;
// 設定為佔用
column[j] = rup[i+j] = lup[i-j+8] = 0;
backtrack(i+1);
column[j] = rup[i+j] = lup[i-j+8] = 1;
}
}
}
}
private void print() {
for(int y = 1; y <= 8; y++) {
for(int x = 1; x <= 8; x++) {
System.out.print(queen[y] == x ? " Q" : " .");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
Queen queen = new Queen();
queen.backtrack();
}
}
def queenss(n):
def placeQueens(k):
if k == 0:
return [[]]
else:
return [[(k, column)] + queens
for queens in placeQueens(k - 1)
for column in range(0, n) if isSafe((k, column), queens)]
return placeQueens(n)
def isSafe(queen, queens):
for q in queens:
if inCheck(queen, q):
return False
return True
def inCheck(q1, q2):
return (q1[0] == q2[0] or # 同列
q1[1] == q2[1] or # 同行
abs(q1[0] - q2[0]) == abs(q1[1] - q2[1])) # 對角線
for qs in queenss(8):
for q in qs:
print(q, end="")
print()
- Scala（摘自 Programming in Scala 23.2）
def queens(n: Int): List[List[(Int, Int)]] = {
def placeQueens(k: Int): List[List[(Int, Int)]] = {
if(k == 0)
List(List())
else
for {
queens <- placeQueens(k - 1)
column <- 1 to n
queen = (k, column)
if isSafe(queen, queens)
} yield queen :: queens
}
placeQueens(n)
}
def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) =
queens forall (q => !inCheck(queen, q))
def inCheck(q1: (Int, Int), q2: (Int, Int)) =
q1._1 == q2._1 || // 同列
q1._2 == q2._2 || // 同行
(q1._1 - q2._1).abs == (q1._2 - q2._2).abs // 對角線
queens(8).foreach(q => {
q.foreach(print)
println()
})class Queen
def initialize
@queen = Array.new(8 + 1, 0)
@column = Array.new(8 + 1, 0)
@rup = Array.new(2 * 8 + 1, 0)
@lup = Array.new(2 * 8 + 1, 0)
end
def backtrack
1.upto(8) { |i|
@column[i] = 1
}
1.upto(2 * 8) { |i|
@rup[i] = @lup[i] = 1
}
__backtrack(1)
end
def __backtrack(i)
if i > 8
layout
else
1.upto(8) { |j|
if @column[j] == 1 && @rup[i + j] == 1 && @lup[i - j + 8] == 1
@queen[i] = j
@column[j] = @rup[i + j] = @lup[i - j + 8] = 0;
__backtrack(i + 1);
@column[j] = @rup[i + j] = @lup[i - j + 8] = 1;
end
}
end
end
private :__backtrack
def layout
1.upto(8) { |y|
1.upto(8) { |x|
print @queen[y] == x ? " Q" : " ."
}
puts
}
puts
end
end
queen = Queen.new
queen.backtrack