‘壹’ 急求！！pascal n皇后问题 (递归） 带详细解析
〖问题描述〗
在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。
〖问题分析〗(聿怀中学吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8
（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；
如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
3、当n>;8时，便一一打印出结果。
〖优点〗逐一测试标准答案，不会有漏网之鱼。
〖参考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procereprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceretry(i:integer);
varj:integer;
begin
forj:=1to8do
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then
begin
a:=j;
b[j]:=1;
c[i+j]:=1;
d[i-j]:=1;
ifi<8thentry(i+1)
elseprint;
b[j]:=0;
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);
end.
==========================================
这是N皇后问题，看看吧：
在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; //放皇后数组
b:array[2..2*max] of boolean; // ‘/’对角线标志数组}
c:array[-(max-1)..max-1] of boolean;// ‘\’对角线标志数组}
col:array[1..max] of boolean; //列标志数组}
total:integer; //统计总数}
procere output; //这里是输出过程
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; //判断第dep行第i列可放否？
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) and
(col[i]=true) then ok:=true
end;
procere try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do //每一行均有max种放法，对吧？xixi~~~~
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; // ‘/’对角线已放标志
c[dep-i]:=false; // ‘\’对角线已放标志
col[i]:=false; // 列已放标志
if dep=max then output
else try(dep+1); // 递归下一层
a[dep]:=0; //取走皇后,回溯
b[i+dep]:=true; //恢复标志数组
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
方案一（深度优先搜索）：
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. 9士捎?到16来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；
fx:array[-7..7] of boolean; //反斜线（左上向右下）数组，该斜线特点为：斜线上每一格的行减列的差一定，差为从-7到7 9士捎?7到7来表示这15条正斜线，于是该数组记录了2到16中某条正斜线是否已经被另一个皇后占用；
temp:integer; //记录总方案数；
procere print; //该子程序负责输出方案；
var i:integer;
begin
write('zuobiao');
for i:=1 to 8 do
write(' (',i,',',ans[i],')'); //i代表行，ans[i]代表列；
writeln;
end;
procere 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); // 反斜线数组设初值为False;
search(1); //从第一行开始进行搜索；
writeln(temp); //再输出总方案数；
end.
方案二（位运算加速）：
var
upperlim,sum:integer;
procere test(row,ld,rd:integer);
var
pos,p:integer;
begin
if row<>upperlim then
begin
pos:=upperlim and not (row or ld or rd);
while pos<>0 do
begin
p:=pos and -pos;
pos:=pos-p;
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
end;
end
else
inc(sum);
end;
begin
upperlim:=(1 shl 8)-1;
test(0,0,0);
writeln(sum);
end.
设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。
‘贰’ 用递归方法求n皇后问题（c++版本的）
#include <cstdio>
#include <cstdlib>
int n=8;
void NQueen(int k,int a[]){
int i,j;
if(k==n){
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
return;
}
for(a[k]=1;a[k]<=n;a[k]++){
for(j=0;j<k;j++)
if(a[j]==a[k]||abs(a[j]-a[k])==k-j) break;
if(j>=k)
NQueen(k+1,a);
}
}
int main()
{
int a[10];
NQueen(0,a);
return 0;
}
‘叁’ C语言八皇后递归问题
queen[]是一个数组，其元素queen[i]表示第i个皇后位于第i行，第queen[i]（值）列。
‘肆’ N皇后问题10秒内能算出的最大个数，请问什么代码能实现呢，这个最大的个数是多少，代码又是什么
packagecom.newflypig.eightqueen;
importjava.util.Date;
/**
*在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
*即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
*下面使用递归方法解决
*@[email protected]
*
*/
publicclassEightQueen{
privatestaticfinalshortN=15; //使用常量来定义，方便之后解N皇后问题
privatestaticintcount=0; //结果计数器
privatestaticintK=0;
publicstaticvoidmain(String[]args){
for(K=9;K<=N;K++){
count=0;
Datebegin=newDate();
//初始化棋盘，全部置0
shortchess[][]=newshort[K][K];
for(inti=0;i<K;i++){
for(intj=0;j<K;j++){
chess[i][j]=0;
}
}
putQueenAtRow(chess,0);
Dateend=newDate();
System.out.println("解决"+K+"皇后问题，用时："+String.valueOf(end.getTime()-begin.getTime())+"毫秒，计算结果："+count);
}
}
(short[][]chess,introw){
/**
*递归终止判断：如果row==N，则说明已经成功摆放了8个皇后
*输出结果，终止递归
*/
if(row==K){
count++;
// System.out.println("第"+count+"种解：");
// for(inti=0;i<N;i++){
// for(intj=0;j<N;j++){
// System.out.print(chess[i][j]+"");
// }
// System.out.println();
// }
return;
}
short[][]chessTemp=chess.clone();
/**
*向这一行的每一个位置尝试排放皇后
*然后检测状态，如果安全则继续执行递归函数摆放下一行皇后
*/
for(inti=0;i<K;i++){
//摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘
for(intj=0;j<K;j++)
chessTemp[row][j]=0;
chessTemp[row][i]=1;
if(isSafety(chessTemp,row,i)){
putQueenAtRow(chessTemp,row+1);
}
}
}
privatestaticbooleanisSafety(short[][]chess,introw,intcol){
//判断中上、左上、右上是否安全
intstep=1;
while(row-step>=0){
if(chess[row-step][col]==1) //中上
returnfalse;
if(col-step>=0&&chess[row-step][col-step]==1) //左上
returnfalse;
if(col+step<K&&chess[row-step][col+step]==1) //右上
returnfalse;
step++;
}
returntrue;
}
}
‘伍’ 八皇后问题求解的C语言程序的实现
这是个前不久,我为别人写的一个代码;
八皇后问题共有92种解;
以下代码是解决:对于固定一个皇后位置,输出所有可能情况.
如果这不适合你的答案你可以,稍微改改的哦~~
代码如下:
#include "stdio.h"
bool board[8][8]={0};
int num=0; //满足条件的个数
int inix,iniy; //输入一个皇后的初始位置
void output() //输出
{
int i, j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(!board[i][j]) printf("■ ");
else printf("◆ ");
}
printf("\n");
}
num++;
printf("\n\n");
return ;
}
bool check(int x,int y) //判断是否能放
{
int i, j ;
for(i=0; i<8 ; i++)
{
if(board[i][y]==1) return false;
}
for(i=0;i<8;i++)
{
if(board[x][i]==1) return false;
}
i=x; j=y;
while(i>0 && j>0 ) { i--; j--; }
for(;i<8 && j<8 ; i++,j++)
if(board[i][j]==1) return false;
i=x; j=y;
while(i>0 && j<7 ) {i--;j++;}
for(;i<8 && j>=0 ; i++ ,j--)
if(board[i][j]==1) return false ;
return true ;
}
void search(int x,int num) // 搜索函数
{
int i;
if(num>=8) { output(); return ;}
if(x==inix-1) search(inix,num+1);
else
{
for(i=0;i<8;i++)
{
if(check(x,i))
{
board[x][i]=1;
search(x+1,num+1);
board[x][i]=0;
}
}
}
return ;
}
int main()
{
scanf("%d %d",&inix,&iniy);
board[inix-1][iniy-1] = 1 ;
search(0,0);
printf("%d\n",num);
return 0;
}
例如:
输入 : 1 1
输出 :
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
4
‘陆’ n皇后问题，递归算法。
c:
#include<stdio.h>
#include<stdlib.h>
intresult=0;
voidqueen(int*chess,intlen,intn){
if(n==len){
result++;
}else{
intflag=0;
for(inti=0;i<len;i++){
flag=1;
for(intj=0;j<n;j++){
if(abs(n-j)==abs(i-chess[j])||chess[j]==i){
flag=0;
break;
}
}
if(!flag)
continue;
chess[n]=i;
queen(chess,len,n+1);
chess[n]=0;
}
}
}
intmain(void){
intn;
int*chess;
scanf("%d",&n);
chess=(int*)malloc(sizeof(int)*n);
queen(chess,n,0);
printf("result=%d ",result);
return0;
}
‘柒’ N皇后回溯问题 解释下这程序 C语言
#include <stdio.h>
#define DelayTime 20000
#define TopX 10
#define TopY 5
int N;/*此处开始设置几个全局变量 N即代表皇后个数*/
int a[8], b[15], c[15];
int Num = 0;/*Num代表解决方法个数*/
int row;
/******************************************************************************/
void BackTrack (int row)
{
int col;
for (col=1; col<=N; col++)
{
if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0) /*1，为什么这里要等于0？ if语句里的3个表达式都代表什么呢？*/
{
a[col-1] = 1;
b[row+col-2] = 1;
c[row-col+N-1] = 1;
gotoxy(col*2 + TopX, row + TopY); /* 2，这里的gotoxy（）语句是做什么的？ 仅仅是跳到相应位置，打印Q*/
putch('Q');
if (row < N)
{
BackTrack (row + 1); /* 3，这句什么意思? 递归调用*/
}
else
{
Num++;
gotoxy(40, 9); /* 4，这里又是做什么的？什么用？*/
printf("Num: %d ", Num);
delay(DelayTime); /* 5，这里又有什么用？延迟*/
}
a[col-1] = 0;
b[row+col-2] = 0; /* 6，这个三个表达式怎么又成0了？*/
c[row-col+N-1] = 0;
gotoxy(col*2 + TopX, row + TopY); /* 7，这又是什么用?*/
putch('.');
}
}
}
/********************************************************************************/
void main()
{
int i, j;
clrscr();
gotoxy(1, 10);
printf("Input the number of queen: ");
while(N <= 0 || N > 100)
{
scanf("%d", &N);
if(N > 100) printf("Two huge number, input again:");
if(N <= 0) printf("Can's smaller than 1, again:");
}
clrscr();
for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++)
{
gotoxy(i*2 + TopX, j + TopY); /* 8，这里又是什么用? 将光标移动到指定位置说明：gotoxy（x，y）将光标移动到指定行y和列x。
*/
putch('.');
}
}
BackTrack(1); /* 9，为什么是1呢？不是应该传递的是皇后的数量吗?第一行，N为皇后的数量*/
gotoxy(12, 17); /* 10，这又是什么用？*/
printf ("There are %d kinds of solution.\n", Num);
getch();
}
‘捌’ C语言递归解决八皇后问题
#include<stdio.h>
intEightQueen(introw,intcol,int(*chess)[8]);
intnotdanger(introw,intcol,int(*chess)[8]);//函数声明要放在主函数外
intsum=0;
intmain()
{
intchess[8][8],i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
chess[i][j]=0;
}
EightQueen(0,8,chess);
printf("一共有%d种方案 ",sum);
return0;
}
intEightQueen(introw,intcol,int(*chess)[8])
{
intchess2[8][8],i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{chess2[i][j]=chess[i][j];}
}
if(row==8)
{
printf("第%d种解法",sum+1);//逗号为中文输入逗号
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%d",(*(*chess2+i)+j));//括号不匹配
printf(" ");
}
printf(" ");
sum++;
}
else
for(j=0;j<8;j++)
{
if(notdanger(row,j,chess))
{
for(i=0;i<8;i++)
{
*(*(chess2+row)+i)=0;//raw没有定义，你是想用row吧？
*(*(chess2+row)+j)=1;//raw没有定义，你是想用row吧？
}
EightQueen(row+1,col,chess2);
}
}
return0;
}
intnotdanger(introw,intj,int(*chess)[8])
{
inti,k,flag1=0,flag2=0,flag3=0;
/*判断列方向*/
for(i=0;i<8;i++)
{
if(*(*chess+i)+j)!=0)
{
flag1=1;
break;
}
}
/*判断左上方*/
for(i=row,k=j;i>=0&&k>=0;i--,k--)//逗号为中文逗号
{
if(*(*chess+i)+k)!=0)
{
flag2=1;
break;
}
}
/*判断右上方*/
for(i=row,k=j;i>=0&&k<8;i--,k++)//逗号为中文逗号
{
if(*(*chess2+i)+k)!=0)//括号比匹配
{
flag3=1;
break;
}
}
if(flag1||flag2||flag3)
{
return0;
}
else
{
return1;
}
}
评注：没有改完，你主要的地方在于中文逗号，花括号“{}”不匹配，“（）”括号不匹配，变量raw没有定义，都是些低级错误，自己把代码的格式调整好，然后再试试。
‘玖’ n皇后递归算法
就是深搜算法
代码如下：
var ans:array[1..13] of byte;
b,c,d:array[-12..26] of boolean;
n,i,max:longint;
procere print;
var i:longint;
begin
for i:=1 to n do
write(ans [i] ,' ');
writeln;
end;
procere gyw(i:integer);
var j:integer;
begin
if i>n then
begin
// print;
inc(max);
end
else for j:=1 to n do
if (b [j] =false)and(c[i+j]=false)and(d[i-j]=false) then
begin
ans [i] :=j;
b [j] :=true;
c[i+j]:=true;
d[i-j]:=true;
gyw(i+1);
b [j] :=false;
c[i+j]:=false;
d[i-j]:=false;
end;
end;
begin
read(n);
gyw(1);
writeln(max);
end.
Pascal的