說明
西洋棋中的皇后可以直線前進,吃掉遇到的所有棋子,如果棋盤上有八個皇后,則這八個皇后如何相安無事的放置在棋盤上,1970年與1971年, E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。
解法
關於棋盤的問題,都可以用遞迴求解,然而如何減少遞迴的次數?在八個皇后的問題中,不必要所有的格子都檢查過,例如若某列檢查過,該該列的其它格子就不用再檢查了,這個方法稱為分支修剪。
所以檢查時,先判斷是否在已放置皇后的可行進方向上,如果沒有再行放置下一個皇后,如此就可大大減少遞迴的次數,例如以下為修剪過後的遞迴檢查行進路徑:
八個皇后的話,會有92個解答,如果考慮棋盤的旋轉,則旋轉後扣去對稱的,會有12組基本解。
#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()
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
|
|