毕业设计 帮帮忙

Question

八皇后算法的分析和实现   高手帮帮忙！！要有思路的 最好有源代码  谢谢了 

Answer 1

八皇后
 
【问题描述】在一个８×８格子的棋盘上，要布局八个皇后，条件是不能出现两个皇后在同一行或同一列或同一斜线的情况，以防“相互攻击”，请问共有多少种合理的布局方式，每一种布局的具体情况如何？
【分析】显然问题的键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／ 斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。从下图可以验证上面的说法：　对于一组布局我们可以用一个一维数组来表示：X:ARRAY [1..8] OF INTEGER;X[I]的下标I表示第I个皇后在棋盘的第I行，X[I]的内容表示在第I行的第X[I]列，例如：X[3]=5就表示第3个皇后在第3 行的第5列。在这种方式下，要表示两个皇后A和B不在同一列或斜线上的条件可以描述为：X[A]<>X[B] AND ABS(A-B)<>ABS(X[A]-X[B]){A和B分别表示两个皇后的行号}
【解法】有了上面的分析，相信大家可以找到不同的算法，这里我们提供三种，当然稍加改动就可推广到Ｎ皇后问题
PROGRAM QN(INPUT,OUTPUT);{递归算法}
CONST N=8;
VAR
　CONT,I:INTEGER;
　A:ARRAY[1..N] OF BYTE;{存放正确的一组解}
　C:ARRAY[1..N] OF BOOLEAN;{存放某一列放皇后的情况，用于判断是否有同列的情况}
　L:ARRAY[1-N..N-1] OF BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为＼}
　R:ARRAY[2..2*N] OF BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为／}　PROCEDURE PR;
　VAR
　　I:INTEGER;
　BEGIN
　　FOR I:=1 TO N DO WRITE(A[I]:4);
　　INC(CONT);
　　WRITELN(" CONT=",CONT);
　END;　PROCEDURE TRY(I:INTEGER);
　VAR
　J:INTEGER;　　PROCEDURE ERASE(I:INTEGER);
　　BEGIN
　　　C[J]:=TRUE;
　　　L[I-J]:=TRUE;
　　　R[I+J]:=TRUE;
　　END;
　BEGIN
　　FOR J:=1 TO N DO
　　BEGIN
　　　IF C[J] AND L[I-J] AND R[I+J] THEN
　　　BEGIN
　　　　A[I]:=J;
　　　　C[J]:=FALSE;
　　　　L[I-J]:=FALSE;
　　　　R[I+J]:=FALSE;
　　　　IF I<N THEN TRY(I+1) ELSE PR;
　　　　ERASE(I);
　　　END;
　　END;
　END;BEGIN
　FOR I:=1 TO N DO C[I]:=TRUE;
　FOR I:=1-N TO N-1 DO L[I]:=TRUE;
　FOR I:=2 TO 2*N DO R[I]:=TRUE;
　CONT:=0;
　I:=1;
　TRY(I);
　WRITELN;
　WRITELN("PROGRAM END.");
　READLN;
END.PROGRAM HUANGHOU(INPUT,OUTPUT);{迭代回溯算法}
CONST N=8;
VAR
　K:INTEGER;
　X:ARRAY[1..N] OF INTEGER;　FUNCTION PLACE(K:INTEGER):BOOLEAN;
　VAR
　　I:INTEGER;
　BEGIN
　　I:=1;
　　WHILE I<K DO
　　BEGIN
　　　IF (ABS(X[I]-X[K])=ABS(I-K)) OR (X[I]=X[K]) THEN
　　　BEGIN
　　　　PLACE:=FALSE;
　　　　EXIT;
　　　END;
　　　I:=I+1;
　　END;
　　PLACE:=TRUE;
　END;　PROCEDURE PRN;
　VAR
　　I:INTEGER;
　BEGIN
　　FOR I:=1 TO N DO WRITE(X[I]:4);
　　WRITELN;
　END;　PROCEDURE NQUEENS(N:INTEGER);
　BEGIN
　　X[1]:=0;
　　K:=1;
　　WHILE K>0 DO
　　BEGIN
　　　X[K]:=X[K]+1;
　　　WHILE ((X[K]<=N) AND (NOT PLACE(K))) DO X[K]:=X[K]+1;
　　　IF X[K]<=N THEN
　　　BEGIN
　　　　IF K=N THEN PRN
　　　　ELSE
　　　　BEGIN
　　　　　K:=K+1;
　　　　　X[K]:=0;
　　　　END;
　　　END
　　　ELSE K:=K-1;
　　END;
　END;BEGIN
　NQUEENS(N);
　READLN;
END.program bahh;{递归回溯算法}
var
 stack:array[1..20] of byte;
 n,total:integer; procedure make(l:integer);
 var
  i,j:integer;
  att:boolean;
 begin
  if l=n+1 then
  begin
   inc(total);
   writeln("No:",total);
   for j:=1 to n do writeln(" ",stack[j],"*");
   writeln;
   exit;
  end;
  for i:=1 to n do
  begin
   att:=false;
   stack[l]:=i;
   for j:=1 to l-1 do
    if(abs(l-j)=abs(stack[j]-i))or(i=stack[j]) then
    begin
     att:=true;
     j:=l-1;
    end;
   if not att then make(l+1);
  end;
 end;
begin
 total:=0;
 fillchar(stack,sizeof(stack),0);
 write("n=");
 readln(n);
 make(1);
 writeln("Total=":9,total);
 readln;
end.PROGRAM BHH(INPUT,OUTPUT);{穷举算法：最好理解，但效率最低}
CONST N=8;
VAR
　I1,I2,I3,I4,I5,I6,I7,I8:INTEGER;
　X:ARRAY [1..N] OF INTEGER;　PROCEDURE PRINT;{输出正确的解}
　VAR
　　I:INTEGER;
　BEGIN
　　FOR I:=1 TO N DO WRITE(X[I]);
　　WRITELN;
　END;　FUNCTION CHECK():BOOLEAN;
　VAR
　　A,B:INTEGER;
　BEGIN
　　FOR A:=2 TO N DO
　　BEGIN
　　　FOR B:=1 TO A-1 DO
　　　BEGIN
　　　　IF (ABS(X[A]-X[B])=ABS(A-B)) OR (X[A]=X[B]) THEN
　　　　BEGIN
　　　　　CHECK:=FALSE;
　　　　　EXIT;
　　　　END;
　　　END;
　　END;
　　CHECK:=TRUE;
　END;BEGIN
　FOR I1:=1 TO N DO
　　FOR I2:=1 TO N DO
　　　FOR I3:=1 TO N DO
　　　　FOR I4:=1 TO N DO
　　　　　FOR I5:=1 TO N DO
　　　　　　FOR I6:=1 TO N DO
　　　　　　　FOR I7:=1 TO N DO
　　　　　　　　FOR I8:=1 TO N DO
　　　　　　　　BEGIN
　　　　　　　　　X[1]:=I1;
　　　　　　　　　X[2]:=I2;
　　　　　　　　　X[3]:=I3;
　　　　　　　　　X[4]:=I4;
　　　　　　　　　X[5]:=I5;
　　　　　　　　　X[6]:=I6;
　　　　　　　　　X[7]:=I7;
　　　　　　　　　X[8]:=I8;
　　　　　　　　　IF CHECK() THEN PRINT;
　　　　　　　　END;
　READLN;
END.

Answer 2

public class Queen {    // 同栏是否有皇后，1表示有     private int[] column;    // 右上至左下是否有皇后    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] = 1;         for(int i = 1; i <= 2*8; i++)             rup[i] = lup[i] = 1;                 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] == 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;                 }             }         }     }        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);    }} 

Answer 3

public class Queen { // 同栏是否有皇后，1表示有
private int[] column; // 右上至左下是否有皇后 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] = 1;
for (int i = 1; i <= 2 * 8; i++)
rup[i] = lup[i] = 1;
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] == 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;
}
}
}
} 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);
}
}