八皇后問題

八皇后問題

八皇后問題,是一個古老而著名的問題,是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾於1848年提出:在8×8格的西洋棋上擺放八個皇后,使其不能互相攻擊,即任意兩個皇后都不能處於同一行、同一列或同一斜線上,問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜誌上不同的作者發表了40種不同的解,後來有人用圖論的方法解出92種結果。計算機發明後,有多種計算機語言可以解決此問題。

基本介紹

  • 中文名:八皇后
  • 外文名:Eight queens
  • 類別:問題
  • 時間:1848年
問題介紹,問題算法,JS,C++,Pascal,Java,Erlang,python,C#,圖形實現,回溯算法,版本一,Qbasic,獨立解,

問題介紹

八皇后問題是一個以西洋棋為背景的問題:如何能夠在 8×8 的西洋棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后?為了達到此目的,任兩個皇后都不能處於同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題:這時棋盤的大小變為n1×n1,而皇后個數也變成n2。而且僅當 n2 ≥ 1 或 n1 ≥ 4 時問題有解。
八皇后問題最早是由國際西洋棋棋手馬克斯·貝瑟爾於1848年提出。之後陸續有數學家對其進行研究,其中包括高斯和康托,並且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲·諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年,S.岡德爾提出了一個通過行列式來求解的方法,這個方法後來又被J.W.L.格萊舍加以改進。
艾茲格·迪傑斯特拉在1972年用這個問題為例來說明他所謂結構性編程的能力。
八皇后問題出現在1990年代初期的著名電子遊戲第七訪客中。

問題算法

JS

function queen(a,cur){    if(cur==a.length){console.log(a);return};    for(var i=0;i<a.length;i++){        a[cur]=i;flag=true;        for(var j=0;j<cur;j++){            var ab=i-a[j];            if(a[j]==i||(ab>0?ab:-ab)==cur-j){flag=false;break};        };        if(flag){queen(a,cur+1)};    };};queen([1,1,1,1,1,1,1,1],0) 

C++

#include<iostream>using namespace std;static int gEightQueen[8] = { 0 }, gCount = 0;void print()//輸出每一種情況下棋盤中皇后的擺放情況{    for (int i = 0; i < 8; i++)    {           int inner;        for (inner = 0; inner < gEightQueen[i]; inner++)            cout << "0";            cout <<"#";        for (inner = gEightQueen[i] + 1; inner < 8; inner++)            cout << "0";        cout << endl;    }    cout << "==========================\n";}int check_pos_valid(int loop, int value)//檢查是否存在有多個皇后在同一行/列/對角線的情況{    int index;    int data;    for (index = 0; index < loop; index++)    {        data = gEightQueen[index];        if (value == data)            return 0;        if ((index + data) == (loop + value))            return 0;        if ((index - data) == (loop - value))            return 0;    }    return 1;}void eight_queen(int index){    int loop;    for (loop = 0; loop < 8; loop++)    {        if (check_pos_valid(index, loop))        {            gEightQueen[index] = loop;            if (7 == index)            {                gCount++, print();                gEightQueen[index] = 0;                return;            }            eight_queen(index + 1);            gEightQueen[index] = 0;        }    }}int main(int argc, char*argv[]){    eight_queen(0);    cout << "total=" << gCount << endl;    return 0;}

Pascal

program queen;vara:array[1..8]of longint;//記錄皇后的行坐標b,c,d:array[-7..16]of longint;//行,右上,右下斜線的占位標誌m,ans:longint;procedure queen(j:longint);vari:longint;begin    if j>8 then    begin        inc(ans);//滿足條件,找到一種方案        exit;    end;    for i:=1 to 8 do//每個皇后位置有八種可能        if(b[i]=0)and(c[i+j]=0)and(d[j-i]=0)then//如果位置沒有被占則運行        begin            a[j]:=i;//皇后放置在此行            b[i]:=1;//占領第i行            c[i+j]:=1;//占領右上            d[j-i]:=1;//占領右下            queen(j+1);//遞歸            b[i]:=0;//回溯,恢復行占位標誌            c[i+j]:=0;//回溯,恢復斜上方(右上)占位標誌            d[j-i]:=0;///回溯,恢復斜下方(右下)占位標誌        end;end;begin//主程式    for m:=-7 to 16 do//數據初始化為0    begin        b[m]:=0;//行數據初始化為0        c[m]:=0;//右上數據初始化為0        d[m]:=0;//右下數據初始化為0    end;    ans:=0;    queen(1);//開始放置第一個皇后    writeln(ans);end.

Java

public class Queen {    private int[] column; //同欄是否有皇后,1表示有    private int[] rup; //右上至左下是否有皇后    private int[] lup; //左上至右下是否有皇后    private int[] queen; //解答    private int num; //解答編號    public Queen() {        column = new int[8+1];        rup = new int[(2*8)+1];        lup = new int[(2*8)+1];        for (int i = 1; i <= 8; i++)            column[i] = 0;        for (int i = 1; i <= (2*8); i++)            rup[i] = lup[i] = 0;  //初始定義全部無皇后        queen = new int[8+1];    }    public void backtrack(int i) {        if (i > 8) {            showAnswer();        } else {            for (int j = 1; j <= 8; j++) {                if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) {                    //若無皇后                    queen[i] = j; //設定為占用                    column[j] = rup[i+j] = lup[i-j+8] = 1;                    backtrack(i+1);  //循環調用                    column[j] = rup[i+j] = lup[i-j+8] = 0;                }            }        }    }    protected void showAnswer() {        num++;        System.out.println("\n解答" + num);        for (int y = 1; y <= 8; y++) {            for (int x = 1; x <= 8; x++) {                if(queen[y]==x) {                    System.out.print("Q");                } else {                    System.out.print(".");                }            }            System.out.println();        }    }    public static void main(String[] args) {        Queen queen = new Queen();        queen.backtrack(1);    }}

Erlang

-module(queen).-export([printf/0, attack_range/2]).-define(MaxQueen, 4).%尋找字元串所有可能的排列%perms([]) ->% [[]];%perms(L) ->% [[H | T] || H <- L, T <- perms(L -- [H])].perms([]) ->[[]];perms(L) ->[[H | T] || H <- L, T <- perms(L -- [H]), attack_range(H,T) == []].printf() ->L = lists:seq(1, ?MaxQueen),io:format("~p~n", [?MaxQueen]),perms(L).%檢測出第一行的數字攻擊到之後各行哪些數字%left向下行的左側檢測%right向下行的右側檢測attack_range(Queen, List) ->attack_range(Queen, left, List) ++ attack_range(Queen, right, List).attack_range(_, _, []) ->[];attack_range(Queen, left, [H | _]) when Queen - 1 =:= H ->[H];attack_range(Queen, right, [H | _]) when Queen + 1 =:= H ->[H];attack_range(Queen, left, [_ | T]) ->attack_range(Queen - 1, left, T);attack_range(Queen, right, [_ | T]) ->attack_range(Queen + 1, right, T).

python

def queen(A, cur=0):    if cur == len(A):        print(A)        return 0    for col in range(len(A)):        A[cur], flag = col, True        for row in range(cur):            if A[row] == col or abs(col - A[row]) == cur - row:                flag = False                break        if flag:            queen(A, cur+1)queen([None]*8)

C#

using System;using System.Collections.Generic;namespace EightQueens_CSharp{    public class EightQueens    {        private List<int[]> solutions;        public List<int[]> GetSolutions(int queenCount)        {            solutions = new List<int[]>();            List<int> queenList = new List<int>();            for (int i = 0; i < queenCount; i++)            {                queenList.Add(0);            }            putQueen(queenCount, queenList, 0);            printSolutions(solutions);            return solutions;        }                private void putQueen(int queenCount, List<int> queenList, int nextY)        {            for (queenList[nextY] = 0; queenList[nextY] < queenCount; queenList[nextY]++)            {                if (checkConflict(queenList, nextY) == false)                {                    nextY++;                    if (nextY < queenCount)                    {                        putQueen(queenCount, queenList, nextY);                    }                    else                    {                        solutions.Add(queenList.ToArray());                        Console.WriteLine(string.Join(", ", queenList));                    }                    nextY--;                }            }        }                private bool checkConflict(List<int> queenList, int nextY)        {            for (int positionY = 0; positionY < nextY; positionY++)            {                if (Math.Abs(queenList[positionY] - queenList[nextY]) == Math.Abs(positionY - nextY) || queenList[positionY] == queenList[nextY])                {                    return true;                }            }            return false;        }                private void printSolutions(List<int[]> solutions)        {            int count = 0;            foreach (var solution in solutions)            {                Console.WriteLine("Solution: {0}", count++);                int queenCount = solution.Length;                for (int i = 0; i < queenCount; i++)                {                    printLine(solution[i], queenCount);                }                Console.WriteLine("------------------");            }        }                private void printLine(int pos, int width)        {            for (int i = 0; i < width; i++)            {                if (pos == i)                {                    Console.Write(" x");                }                else                {                    Console.Write(" .");                }            }            Console.WriteLine();        }    }}

圖形實現

簡述
對於八皇后問題的實現,如果結合動態的圖形演示,則可以使算法的描述更形象、更生動,使教學能產生良好的效果。下面是用Turbo C實現的八皇后問題的圖形程式,能夠演示全部的92組解。八皇后問題動態圖形的實現,主要應解決以下兩個問題。
主程式
//eigqueprob.h#include "stdio.h"#define N 8 // N 表示皇后的個數 用來定義答案的結構體typedef struct{    int line; // 答案的行號      int row; // 答案的列號 }ANSWER_TYPE;// 用來定義某個位置是否被占用 typedef enum{    notoccued = 0, // 沒被占用  occued = 1 // 被占用     occued = 1}IFOCCUED;// 該列是否已經有其他皇后占用 IFOCCUED rowoccu[N];// 左上-右下對角位置已經有其他皇后占用 IFOCCUED LeftTop_RightDown[2 * N - 1];// 右上-左下對角位置已經有其他皇后占用IFOCCUED RightTop_LefttDown[2 * N - 1];// 最後的答案記錄 ANSWER_TYPE answer[N];/* 尋找下一行占用的位置 */void nextline(int LineIndex){    static int asnnum = 0; /* 統計答案的個數 */    int RowIndex = 0; /* 列索引 */    int PrintIndex = 0;/* 按列開始遍歷 */    for (RowIndex = 0; RowIndex < N; RowIndex++)    {        /* 如果列和兩個對角線上都沒有被占用的話,則占用該位置 */        if ((notoccued == rowoccu[RowIndex]) && (notoccued == LeftTop_RightDown[LineIndex - RowIndex + N - 1]) && (notoccued == RightTop_LefttDown[LineIndex + RowIndex]))        {            /* 標記已占用 */            rowoccu[RowIndex] = occued;            LeftTop_RightDown[LineIndex - RowIndex + N - 1] = occued;            RightTop_LefttDown[LineIndex + RowIndex] = occued;            /* 標記被占用的行、列號 */            answer[LineIndex].line = LineIndex; answer[LineIndex].row = RowIndex;            /* 如果不是最後一行,繼續找下一行可以占用的位置 */            if ((N - 1) > LineIndex) {                nextline(LineIndex + 1);            }            /* 如果已經到了最後一行,輸出結果 */            else            {                asnnum++;                printf("\nThe %dth answer is :", asnnum);                for (PrintIndex = 0; PrintIndex<N; PrintIndex++)                {                    printf("(%d,%d) ", answer[PrintIndex].line + 1, answer[PrintIndex].row + 1);                }                /* 每10個答案一組,與其他組隔兩行 */                if ((asnnum % 10) == 0)                    printf("\n\n");            }            /* 清空占用標誌,尋找下一組解 */            rowoccu[RowIndex] = notoccued;            LeftTop_RightDown[LineIndex - RowIndex + N - 1] = notoccued;            RightTop_LefttDown[LineIndex + RowIndex] = notoccued;        }    }}int main(){    int i = 0;    /* 調用求解函式*/    nextline(i);    /* 保持螢幕結果*/    getchar();    return 1;}

回溯算法

版本一

(a)為解決這個問題,我們把棋盤的橫坐標定為i,縱坐標定為j,i和j的取值範圍是從1到8。當某個皇后占了位置(i,j)時,在這個位置的垂直方向、水平方向和斜線方向都不能再放其它皇后了。
用語句實現,可定義如下三個整型數組:a[8],b[15],c[24]。其中:
a[j-1]=1 第j列上無皇后
a[j-1]=0 第j列上有皇后
b[i+j-2]=1 (i,j)的對角線(右上至左下)無皇后
b[i+j-2]=0 (i,j)的對角線(右上至左下)有皇后
c[i-j+7]=1 (i,j)的對角線(左上至右下)無皇后
c[i-j+7]=0 (i,j)的對角線(左上至右下)有皇后
(b)為第i個皇后選擇位置的算法如下:
for(j=1;j<=8;j++) /*第j個皇后在第j行*/
if ((i,j)位置為空)) /*即相應的三個數組的對應元素值為1*/
{占用位置(i,j) /*置相應的三個數組對應的元素值為0*/
if i<8
為i+1個皇后選擇合適的位置;
else 輸出一個解
}
(2)圖形存取
在Turbo C語言中,圖形的存取可用如下標準函式實現:
size=imagesize(x1,y1,x2,y2) ;返回存儲區域所需位元組數。
arrow=malloc(size);建立指定大小的動態區域點陣圖,並設定一指針arrow。
getimage(x1,y1,x2,y2,arrow);將指定區域點陣圖存於一緩衝區
putimage(x,y,arrow,copy)將點陣圖置於螢幕上以(x,y)左上角的區域。
(3)程式清單如下
#include#include#include#includechar n[3]={'0','0'};/*用於記錄第幾組解*/int a[8],b[15],c[24],i;int h[8]={127,177,227,277,327,377,427,477};/*每個皇后的行坐標*/int l[8]={252,217,182,147,112,77,42,7}; /*每個皇后的列坐標*/void *arrow;void try(int i){int j;for (j=1;j<=8;j++)if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行為空*/{ a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/ putimage(h[i-1],l[j-1],arrow,COPY_PUT); /*顯示皇后圖形*/ delay(500);/*延時*/ if(i<8) try(i+1); else /*輸出一組解*/ { n[1]++; if (n[1]>'9') { n[0]++;n[1]='0'; } bar(260,300,390,340);/*顯示第n組解*/ outtextxy(275,300,n); delay(3000); }a[j-1]=1; b[i+j-2]=1; c[i-j+7]=1; putimage(h[i-1],l[j-1],arrow,XOR_PUT); /*消去皇后,繼續尋找下一組解*/ delay(500); }}int main(void){ int gdrive=DETECT,gmode,errorcode;unsigned int size; initgraph(&gdrive,&gmode,""); errorcode=graphresult(); if (errorcode!=grOk) { printf("Graphics error\n");exit(1); } rectangle(50,5,100,40); rectangle(60,25,90,33);/* 畫皇冠 */ line(60,28,90,28); line(60,25,55,15); line(55,15,68,25); line(68,25,68,10); line(68,10,75,25); line(75,25,82,10); line(82,10,82,25); line(82,25,95,15); line(95,15,90,25); size=imagesize(52,7,98,38); arrow=malloc(size); getimage(52,7,98,38,arrow); /* 把皇冠保存到緩衝區*/ clearviewport(); settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4); setusercharsize(3, 1, 1, 1); setfillstyle(1,4); for (i=0;i<=7;i++) a=1; for (i=0;i<=14;i++) b=1; for (i=0;i<=23;i++) c=1; for (i=0;i<=8;i++) line(125,i*35+5,525,i*35+5); /* 畫棋盤 */ for (i=0;i<=8;i++) line(125+i*50,5,125+i*50,285); try(1); /* 調用遞歸函式 */ delay(3000); closegraph(); free(arrow);}#include<stdio.h>#include<memory.h>static int a[9][9],i,j,sum=0,t=1,column_status[9],slash_status[16],back_slash_status[17];int main(){ void print_board(); void go_up(); memset(column_status,0,sizeof(column_status)); memset(slash_status,0,sizeof(slash_status)); memset(back_slash_status,0,sizeof(back_slash_status)); memset(a,0,sizeof(a)); for(i=1;i<=8;i++) for(j=t;j<=8;j++) if(column_status[j]==0 && slash_status[i-j+8]==0 && back_slash_status[i+j]==0) { a[i][j]=1; column_status[j]=1; slash_status[i-j+8]=1; back_slash_status[i+j]=1; if (i==8) { print_board(); if(t==8) { go_up(); i--; break; } elsej=t; } else { t=1;break; } } else if(j==8) { if (i==1)return 0; else { go_up(); i--; break; } } return 0;}void print_board(){ printf("第%d個方案為\n",++sum); for(i=1;i<=8;i++) { for(j=1;j<=8;j++) { if (a[i][j]==1) { printf("@ "); t=j; } else printf("* "); } printf("\n"); }}void go_up(){ i=i-1; for(j=1;j<=8;j++) { if(a[i][j]==1) { a[i][j]=0; column_status[j]=0; slash_status[i-j+8]=0; back_slash_status[i+j]=0; if (j==8) go_up(); else { t=j+1; break; } } }}易語言

Qbasic

10 I = 120 A(I) = 130 G = 140 FOR K = I - 1 TO 1 STEP -150 IF A(I) = A(K) THEN 7060 IF ABS(A(I) - A(K)) <> I - K THEN 9070 G = 080 GOTO 10090 NEXT K100 IF I <> 8 THEN 180110 IF G = 0 THEN 180120 FOR L = 1 TO 8130 PRINT USING “##”; A(L);140 NEXT L150 PRINT “*”;160 M = M + 1170 IF M MOD 3 = 0 THEN PRINT180 IF G = 0 THEN 230190 IF I = 8 THEN 230200 I = I + 1210 A(I) = 1220 GOTO 30230 IF A(I) < 8 THEN 270240 I = I - 1250 IF I = 0 THEN 290260 GOTO 230270 A(I) = A(I) + 1280 GOTO 30290 PRINT300 PRINT “SUM=”; USING “##”; M;310 PRINT320 END
高效解法
//8 Queen遞歸算法
//如果有一個Q 為 chess=j;
//則不安全的地方是 k行 j位置,j+k-i位置,j-k+i位置
class Queen8{
static final int QueenMax = 8;
static int oktimes = 0;
static int chess[] = new int[QueenMax];//每一個Queen的放置位置
public static void main(String args[]){
for (int i=0;i placequeen(0);
System.out.println("\n\n\n八皇后共有"+oktimes+"個解法 made by yifi 2003");
}
public static void placequeen(int num){ //num 為當前要放置的行數
int i=0;
boolean qsave[] = new boolean[QueenMax];
for(;i //下面先把安全位數組完成
i=0;//i 是要檢查的數組值
while (i qsave[chess]=false;
int k=num-i;
if ( (chess+k >= 0) && (chess+k < QueenMax) ) qsave[chess+k]=false;
if ( (chess-k >= 0) && (chess-k < QueenMax) ) qsave[chess-k]=false;
i++;
}
//下面歷遍安全位
for(i=0;i if (qsave==false)continue;
if (num chess[num]=i;
placequeen(num+1);
}
else{ //num is last one
chess[num]=i;
oktimes++;
System.out.println("這是第"+oktimes+"個解法 如下:");
System.out.println("第n行: 1 2 3 4 5 6 7 8");
for (i=0;i String row="第"+(i+1)+"行: ";
if (chess==0);
else
for(int j=0;j row+="++";
int j = chess;
while(j System.out.println(row);
}
}
}
//歷遍完成就停止
}
}
c#非遞歸實現
思路
採用的思路大致是這樣:
將一個皇后向下移動一個位置;
如果沒有成功移動(超出邊界),失敗;
如果成功移動,則判斷當前位置是否可用?如果不可用,則重做 1;
繼續給下一個皇后安排位置。
結束條件
如果第一個皇后的所有位置都嘗試完畢仍然沒有可用的解決方案或者最後一個皇后已經安排完畢。
代碼
// AppEntry.csusing System;namespace Chenglin{ class AppEntry { static void Main(string[] args) { int queenNumber = 8; QueenRowCollection q = new QueenRowCollection(queenNumber); bool flag; DateTime timeStarted = DateTime.Now; flag = q.PositionQueens(); TimeSpan ts = DateTime.Now.Subtract( timeStarted ); if( flag ) { Console.WriteLine( q.ToString() ); } else { Console.WriteLine( "Failed" ); } Console.WriteLine( " seconds has been elapsed.", ts.TotalSeconds ); } }}// QueenRowCollection.csusing System;using System.Text;namespace Chenglin{ public class QueenRowCollection { public QueenRowCollection( int numberOfQueens ) { this.numberOfQueens = numberOfQueens; this.rows = new QueenRow[ numberOfQueens ]; } } public bool PositionQueens() { return PositionQueen( 0 ); } private bool PositionQueen( int row ) { if( row>=this.numberOfQueens ) { return true; } QueenRow q = rows[row]; while(q.MoveNext()) { if( PositionAvailable( row, q.CurrentPosition ) ) { // An available position has been found for the current queen, // and try to find a proper position for the next queen. // // If no available position can be found for the next queen, // the current queen should move to the next position and try again. // if( PositionQueen( row+1 ) ) { // Both the current queen and the next queen // have found available positions. // return true; } } } // No position is available for the current queen, // return false; } private bool PositionAvailable( int row, int column ) { for( int i=row-1; i>=0; i-- ) { if( rows.PositionOccupied( column ) ) return false; if( rows.PositionOccupied( column-(i-row) ) ) return false; if( rows.PositionOccupied( column+(i-row) ) ) return false; } return true; } public override string ToString() { StringBuilder s = new StringBuilder(); foreach( QueenRow q in rows ) { s.AppendFormat( "", q, Environment.NewLine ); } return s.ToString(); } private int numberOfQueens; private QueenRow [] rows; }}
1// QueenRow.cs
2using System;
3using System.Text;
4
5namespace Chenglin
6{
7 public class QueenRow
8 {
9 public QueenRow( int numberOfPositions )
10 {
11 this.numberOfPositions = numberOfPositions;
12 this.currentPosition = -1;
13 this.columns = new bool[ numberOfPositions ];
14 }
15
16 public bool MoveNext(){
17 if( currentPosition>=0 && currentPosition 18 columns[currentPosition] = false;
19 }
20
21 if( currentPosition 22 currentPosition ++;
23 columns[currentPosition] = true;
24 return true;
25 }
26 else {
27 currentPosition = -1;
28 return false;
29 }
30 }
31
32 public bool PositionOccupied( int column ){
33 if( column<0 || column>=numberOfPositions ){
34 return false;
35 }
36
37 return columns[column];
38 }
39
40 public override string ToString()
41 {
42 StringBuilder s = new StringBuilder();
43
44 foreach( bool b in columns ){
45 s.AppendFormat( " ", (b ? "*" : "-") );
46 }
47
48 return s.ToString();
49 }
50
51 public int CurrentPosition
52 {
53 get { return currentPosition; }
54 }
55
56 private int currentPosition;
57 private int numberOfPositions;
58 private bool [] columns;
59 }
60}
遞歸實現思路:
按列分別安排皇后(Q),Q數目可隨意指定(由於StackOverFlowException,只能到8)。
Q1可以放在任何位置;
然後嘗試Q2,因為Q1的限制,Q2必須排除第二列與Q1行數插值大於2的位置;
依次嘗試Qm... 如果Qm上沒有剩餘可用位置,則返回Qm-1,同時使Qm-1 放棄剛才使用位置;
當到達結尾Qn時,成功放置,則存儲所有位置,作為一種解法;
當Q1嘗試過首列所有位置後,算法結束。
結果統計並羅列所有解法。
堆疊修改:
“editbin /stack:4048000 D:\aa\ConsoleApplication2.exe”
代碼:
using System;
using System.Collections.Generic;
classMainClass
{
staticvoid Main()
{
int queens = int.Parse(Console.ReadLine());
List<Position> allPositions = GetAllPositions(queens);
int column = 0;
List<List<Position>> solutions = newList<List<Position>>();
EightQueens(queens, allPositions, column, newStack(), solutions);
for (int i = 0; i < solutions.Count; i++)
{
DisplayPositions(solutions[i]);
}
Console.WriteLine(solutions.Count);
Console.Read();
}
#region EightQueens
classStack
{
publicList<Position> CurrentPositions = newList<Position>();
List<KeyValuePair<int, List<Position>>> stack = newList<KeyValuePair<int, List<Position>>>();
publicvoid push(int i, List<Position> p )
{
stack.Add(newKeyValuePair<int, List<Position>>(i, p));
}
publicKeyValuePair<int, List<Position>> pop()
{
KeyValuePair<int, List<Position>> p = stack[stack.Count - 1];
stack.RemoveAt(stack.Count - 1);
return p;
}
publicvoid ClearFromKey(int key)
{
int idx = stack.FindIndex(a=>a.Key == key);
if (idx > -1)
{
stack.RemoveRange(idx, stack.Count - idx);
}
}
publicList<KeyValuePair<int, List<Position>>> StackList
{
get
{
returnthis.stack;
}
}
}
classPosition
{
publicint left;
publicint right;
public Position(int left, int right)
{
this.left = left;
this.right = right;
}
publicint LeftDistence(Position p)
{
returnMath.Abs(this.left - p.left);
}
publicint RightDistence(Position p)
{
returnMath.Abs(this.right - p.right);
}
publicint QueenNumber = -1;
publicbool HasQueen
{
get
{
return QueenNumber != -1;
}
}
}
staticKeyValuePair<bool, int> EightQueens(int queens, List<Position> allPositions, int column, Stack stack, List<List<Position>> solutions)
{
if (column == queens)
{
List<Position> newLst = newList<Position>();
if(solutions.Count > 0)
{
for(int i = 0 ; i < solutions[solutions.Count - 1].Count -1 ; i++)
{
newLst.Add(solutions[solutions.Count - 1][i]);
}
}
solutions.Add(newLst);
return EightQueens(queens, allPositions, column -1, stack, solutions);
}
if (column == 0)
{
stack.ClearFromKey(1);
if (solutions.Count > 0 && solutions[solutions.Count - 1].Count != queens)
{
solutions.RemoveAt(solutions.Count - 1);
}
solutions.Add(newList<Position>());
}
List<Position> results;
if (solutions.Count > 0)
{
results = solutions[solutions.Count - 1];
}
else
{
results = newList<Position>();
}
List<Position> newPositions = newList<Position>();
if (stack.StackList.Exists(a => a.Key == column))
{
newPositions = stack.StackList.Find(a => a.Key == column).Value;
if (newPositions.Count > 0)
{
newPositions.RemoveAt(0);
}
}
else
{
newPositions = allPositions.FindAll(a => a.left == column);
newPositions = FilterPositions(newPositions, results);
stack.push(column, newPositions);
}
if (newPositions.Count > 0)
{
newPositions[0].QueenNumber = column;
results.Add(newPositions[0]);
column = column + 1;
return EightQueens(queens, allPositions, column, stack, solutions);
}
else
{
stack.ClearFromKey(column);
if (stack.StackList.Count > 0 && stack.StackList.Find(a => a.Key == 0).Value.Count > 0)
{
if (results.Count > 0)
{
results.RemoveAt(results.Count - 1);
}
return EightQueens(queens, allPositions, column - 1, stack, solutions);
}
else
{
if (solutions.Count > 0)
{
solutions.RemoveAt(solutions.Count - 1);
}
returnnewKeyValuePair<bool, int>(true, 0);
}
}
}
staticList<Position> GetAllPositions(int queens)
{
List<Position> positions = newList<Position>();
for (int i = 0; i < queens; i++)
{
for (int j = 0; j < queens; j++)
{
positions.Add(newPosition(i, j));
}
}
return positions;
}
staticList<Position>FilterPositions(List<Position>original, Position newPosition)
{
return original.FindAll(a => CheckPosition(a, newPosition));
}
staticList<Position> original, List<Position> newPositions)
{
if (newPositions == null || newPositions.Count == 0)
{
return original;
}
List<Position> ps = newList<Position>();
foreach(Position p in newPositions)
{
original.RemoveAll(a => ! CheckPosition(a, p));
}
foreach (Position p in original)
{
ps.Add(p);
}
return ps;
}
staticBoolean CheckPosition(Position newPosition, Position targetPosition)
{
int left = newPosition.LeftDistence(targetPosition);
int right = newPosition.RightDistence(targetPosition);
if (left < 1 || right < 1 || left == right)
{
returnfalse;
}
returntrue;
}
staticvoid DisplayPositions(List<Position> positions)
{
for (int i = 0; i < positions.Count; i++)
{
Console.Write(positions[i].left);
Console.Write(positions[i].right + ",");
}
Console.WriteLine();
}
#endregion
}
C++代碼#includeusing namespace std;int width=8,lim=(1<void queen(int col,int ld,int rd) //分別是列,正斜線,反斜線,{ //col的二進制位中的1代表該行不能放的地方,ld,rd同理 if(col==lim){ans++;return;} //遞歸終止條件:col的二進制位在width(棋盤寬度)內都是1(放滿了) int pos=lim&~(col|ld|rd); //col,ld,rd都是0的位可以放皇后,pos該位置1 while(pos) { int t=pos&-pos; //取pos最右邊的1位放皇后 pos-=t; queen(col|t,(ld|t)<<1,(rd|t)>>1); //往棋盤的下一行遞歸,左斜線的限制往左,右斜線往右,可以畫圖看看 }}int main(){ queen(0,0,0); // cout< return 0;}C++另外一種方法
#include <iostream>using namespace std;int a[8]; int b[8]; int c=0;bool flag(int pos){ int i; for(i=0;i<pos;++i) { if(a[i]==a[pos]) {return false;} if(a[i]==a[pos]-(pos-i)||a[i]==a[pos+(pos-i)) {return false;} } return true;}void start(int pos){ int i; for(i=0;i<n;++i) { a[pos]=i; if(flag(pos)) { if(pos==7) {c++;} else {start(pos+1);} } } return;}int main(){ int i,j; for(i=0;i<n;i++) a[i]=-1; start(0); cout<<c<<"種方法"; system("pause"); return 0;}Python
#!/usr/bin/env python# 用一維數組模擬,數組中的值代表皇后所在的列,則皇后所有的位置# 的解空間是[0,1,2,3,4,5,6,7]的所有排列。對某一排列肯定滿足不在# 同行同列的要求,只需要判斷對任意兩皇后不在斜對角線上就行# 即: |i - j| != |array[i] - array[j]|def check_diagonal(array): for i in range(len(array)): for j in range(i+1, len(array)): if j-i == abs(array[i] - array[j]): return False return Truedef permutation(array, begin_index): result = 0 if begin_index >= len(array)-1: if check_diagonal(array): #print array result += 1 else: for i in range(begin_index, len(array)): array[begin_index], array[i] = array[i], array[begin_index] result += permutation(array, begin_index+1) array[begin_index], array[i] = array[i], array[begin_index] return resultdef queen(num): array = range(num) return permutation(array, 0)if __name__ == '__main__': print queen(8)
PHP實現
思路:將皇后的位置用一個一維數組保存起來,類似棧,棧底從0開始
/**
* @param $j 下一個皇后可能所在的位置
* @param $queen 存放之前符合所有條件的皇后的位置
* @return boolean 衝突時返回true
*/
function isConflict($j,$queen)
{
for($i = 0,$len = count($queen); $i<$len; $i++)
{
//與$queen中任意皇后在同一列或對角線上
if(in_array(abs($j-$queen[$i]),array(0,($len-$i))))
return true;
}
return false;
}
/**
* 回溯
*/
function backTracking(&$queen,&$j,$num)
{
$j = array_pop($queen);//將棧頂退出,下次循環就$j=$j+1,也就是從下個位置開始
if($j == $num-1)//若退出的是上一行的最後一列
{
if ($queen)//當棧不為空時,繼續回退
{
$j = array_pop($queen);
}
else//棧已空,遍歷結束
{
$j = $num -1;
}
}
}
/**
* @param $num 皇后個數
*
*/
function queens($num)
{
$queen = array();//存放一種結果
$queens = array();//存放所有結果
for($j=0;$j<$num;$j++)
{
if (isConflict($j,$queen))
{
if($j == $num-1)
{
backTracking($queen,$j,$num);
}
}
else
{
array_push($queen,$j);//沒有任何衝突,入棧
$j = -1;//下次循環時, $j = 0
if(count($queen) == $num)//棧滿了,已找到了符合所有條件的所有皇后,保存起來。
{
$queens[] = $queen;
backTracking($queen,$j,$num);
}
}
}
return $queens;
}
PASCAL
program bahuanghou;
var ans:array[1..8] of integer; //記錄答案的數組,記錄在第1到第8行皇后所在的列;
lie:array[1..8] of boolean; //記錄1到8中某列是否已經被另一個皇后占用;
zx:array[2..16] of boolean; //正斜線(左下向右上)數組,該斜線特點為:斜線上每一格的行加列的和一定,和為從2到16.。故可用2到16來表示這15條正斜線,於是該數組記錄了2到16中某條正斜線是否已經被另一個皇后占用;
fx:array[-7..7] of boolean; //反斜線(左上向右下)數組,該斜線特點為:斜線上每一格的行減列的差一定,差為從-7到7。故可用-7到7來表示這15條反斜線,於是該數組記錄了2到16中某條正斜線是否已經被另一個皇后占反;
temp:integer; //記錄總方案數;
procedure print; //該子程式負責輸出方案;
var i:integer;
begin
write('zuobiao');
for i:=1 to 8 do write(' (',i,',',ans[i],')'); //i代表行,ans[i]代表列;
writeln;
end;
procedure search(i:integer); //i為行,即表示放到了第幾個皇后(因為一行有且只有1個皇后);
var j:integer;
begin
if i=9 then //遞歸出口,當搜尋到第九行時,便得到一種方案;
begin
print; //輸出該方案;
inc(temp); //每輸出(得到)一種方案,總方案數變加1;
exit; //退出;
end;
for j:=1 to 8 do if not lie[j] and not zx[i+j] and not fx[i-j] then //當前位置,該列,正斜線,反斜線上均未被另一個皇后占用,即可以擺放一個皇后;
begin
lie[j]:=true; //設定標誌,該行
zx[i+j]:=true; // 該正斜線
fx[i-j]:=true; // 該反斜線上已被皇后占用,不可再放皇后;
ans[i]:=j; //記錄答案(第i行皇后所在列j);
search(i+1); //實行下一層遞歸;
lie[j]:=false; //恢復標誌(回溯);
zx[i+j]:=false;
fx[i-j]:=false;
end;
end;
begin //主程式;
temp:=0; //給總方案數設初值為“0”;
fillchar(lie,sizeof(lie),0); //分別給列
fillchar(zx,sizeof(zx),0); // 正斜線
fillchar(fx,sizeof(fx),0); // 反斜線數組設初值為“假”
search(1); //從第一行開始進行搜尋;
writeln(temp); //再輸出總方案數;
end.
SHELL
#/bin/bash
canSet() { # 檢查是否可放下皇后的子程式.
for ((n=0;n<y;n++)) ;do
((P[$n] == x)) && return 1 # 檢查是否同一行, 如果是返回1 false
((P[$n] == x - n + y )) && return 1 #檢查斜行.
((P[$n] == x + n - y )) && return 1 #檢查另一方向斜行.
done
return 0 # 返回成功.
}
# init
y=0 # y 是行,
for((i=0;i<8;i++)) ;do
P[$i]=-1 # p 是座位array , -1是不在棋盤上.
done
while (((y<8)&&(y>=0)));do #如果y>=8, 即找到結果, 如果y<0, 即找不到結果, 退出回卷
# echo ${P[*]}; # 打開這一註解,可看script 運行過程
f=0 # 設flag = 0, 用它檢查否一整能不能放下皇后
s=${P[$y]}+1 # 每一行皇后放下的列位罝+1
for ((x=s;x<8;x++)); do #其他shell 用 for x in seq $s 7
if canSet ;then #如果可放下, 則
P[$y]=$x #記下皇后位罝
((y++)) # 行位罝加1, 如用其他shell, 用 y=`expr $y + 1`代替
f=1 #設flag=1,即可效皇后.
break #處理下一個皇后
fi
done
if [ $f -eq 0 ];then # 如果整行都不能放下皇后.則
P[$y]=-1 #將皇后由棋盤上拿下.
((y--)) #行位罝-1.
fi
done
echo ${P[*]}; 列印數據

獨立解

在92個解中,很多解在棋盤上有對稱關係,每一個棋子都有8個對稱位置,如果一個解和另外一個解所有的棋子都呈同一種對稱,那么這兩個解之間就是對稱關係。例如右邊兩個解實際上沿著垂直軸翻轉,就是一個,因此不是獨立的。相互間沒有對稱關係的解是獨立解。雖然一個解可以有8個對稱位置,但是有些解經過對稱操作後和沒有操作前是一樣的。
八皇后問題
在一個標準的8×8的棋盤中,92個解當中有12個解是獨立的。8×8棋盤的獨立解如圖所示。
八皇后問題
如果把棋盤從8×8變成N×N, 八皇后問題就變成了N皇后問題。N從4以上都有解,並分別有相應的獨立解。
下面是皇后的數目於解數目的關係
皇后數獨立解全部解111
4
12521061476408129294635210927241134126801217871420013923373712144575236559
比較特殊的是,皇后6x6棋盤的解比5x5少,其餘解的數目隨著皇后數目增加。但似乎無數學表達式可以描述。
pascal的解法是
vari,k,n,h:longint;x:array[1..1000] of longint;function p1(k:longint):boolean;beginp1:=true;for i:=1 to (k-1) doif (x[i]=x[k]) or ((abs(x[i]-x[k]))=(abs(i-k))) then p1:=false;end;procedure p2;beginh:=h+1;end;procedure p3(k:longint);var i:integer;beginif (k=n+1) thenbeginp2;exit;end;for i:=1 to n dobeginx[k]:=i;if p1(k) then p3(k+1);end;end;beginreadln(n);p3(1);write(h);end.
*/public class Queen {int size;int resultCount;public void compute ( int size ) {this.size = size;resultCount = 0;int data[] = new int[size];intcount; // 所有可能的情況個數int i,j;// 計算所有可能的情況的個數count = 1;for ( i=0 ; i count = count * size;}// 對每一個可能的情況for ( i=0 ; i // 計算這種情況下的棋盤上皇后的擺放位置,用 8 進制數表示// 此處可最佳化inttemp= i;for ( j=0 ; j data [j] = temp % size;temp = temp / size;}// 測試這種情況是否可行,如果可以,輸出if (test(data) )output( data );}}/** 測試這種情況皇后的排列是否可行**/public boolean test( int[] data ) {int i,j;for ( i=0 ; i for ( j=i+1 ; j // 測試是否在同一排if ( data == data[j] )returnfalse;// 測試是否在一斜線if ( (data+i) == (data[j]+j) )return false;// 測試是否在一反斜線if ( (data-i) == (data[j]-j) )return false;}}returntrue;}/** 輸出某種情況下皇后的坐標**/public void output ( int[] data ) {int i;System.out.print ( ++resultCount + ": " );for ( i=0 ; i System.out.print ( "(" + i + "," + data + ") " );}System.out.println ();}public static void main(String args[]) {(new Queen()).compute( 8 );}}

相關詞條

熱門詞條

聯絡我們