Ⅰ 如何用C语言解决N皇后问题并作出流程图
#include"iostream"
using namespace std;
const max_board = 13;
class Queen
{
public :
Queen(int size);
bool is_solved() const; //判断是否已经填满
void print() const; //打印结果
bool unguarded(int col) const; //判断是否被锁定
void insert(int col); /首旁/在该位放置皇后
void remove(int col); //移除皇后
// void solve_from(Queen &configuration);
int board_size; //边界
private :
int count; //已放置皇后的数目
bool queen_square[max_board][max_board]; //棋盘
};
Queen::Queen(int size)
{
if(size<1)
board_size=1;
else
if(size>13)
board_size=13;
else
board_size=size;
count=0;
for(int i=0;i<board_size;i++)
for(int j=0;j<board_size;j++)
{
queen_square[i][j]=false;
}
}
bool Queen::is_solved() const
{
return count==board_size;
}
void Queen::print() const
{
for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
cout<<queen_square[i][j]<<' ';
}
cout<<endl;
}
cout<<仔芹迅endl;
}
bool Queen::unguarded(int col) const
{
int i;
bool ok=true;
for(i=0;ok&&i<count;i++)
{
ok=!queen_square[i][col];
}
for(i=1;i<=col&&i<念此=count&&ok;i++)
{
ok=!queen_square[count-i][col-i];
}
for(i=1;i<board_size-col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col+i];
}
return ok;
}
void Queen::insert(int col)
{
queen_square[count++][col]=true;
}
void Queen::remove(int col)
{
queen_square[--count][col]=false;
}
void solve_from(Queen &configuration)
{
if(configuration.is_solved())
configuration.print();
else
for(int col=0;col<configuration.board_size;col++)
if(configuration.unguarded(col))
{
configuration.insert(col);
solve_from(configuration);
configuration.remove(col);
}
}
int main()
{
int n;
cout<<"please input the size:\t";
cin>>n;
Queen queen(n);
solve_from(queen);
return 0;
}
Ⅱ N皇后问题的回溯法求解属于子集树还是排列树 详细讲一讲
“八皇后”问题递归法求解 (Pascal语言) 八皇后问题是一个古老而着名的问题，是回溯算法的典型例题。该问猜羡哪题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。穗码现代教学中，把八皇后问题当成一个经典递归算法例题。 算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列，如果某列上已经有皇后，则为1，否则为0；数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]，如果某条主对角线上已经有皇后，则为1，否则为0；数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]，如果某条从对角线上已经有皇后，则为1，否则为派前0；另优化：第一个皇后在1~4格，最后*2，即为总解数 } program queens; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procere print; begin t:=t+1; write(t,': '); for k:=1 to 8 do write(a[k],' '); writeln; end; procere try(i:integer); var j:integer; begin for j:=1 to 8 do {每个皇后都有8种可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判断位置是否冲突} begin a:=j; {摆放皇后} b[j]:=1; {宣布占领第J行} c[i+j]:=1; {占领两个对角线} d[i-j]:=1; if i<8 then try(i+1) {8个皇后没有摆完，递归摆放下一皇后} else print; {完成任务，打印结果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fillchar(a,sizeof(a),0); {初始化数组} fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); try(1);{从第1个皇后开始放置} end. “八皇后”问题递归法求解 (C语言) ＃i nclude "stdio.h" static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int iQueenNum=0; //记录总的棋盘状态数 void qu(int i); //参数i代表行 int main() { int iLine,iColumn; //棋盘初始化，空格为*，放置皇后的地方为@ for(iLine=0;iLine<8;iLine++) { a[iLine]=0; //列标记初始化，表示无列冲突 for(iColumn=0;iColumn<8;iColumn++) Queen[iLine][iColumn]='*'; } //主、从对角线标记初始化，表示没有冲突 for(iLine=0;iLine<15;iLine++) b[iLine]=c[iLine]=0; qu(0); return 0; } void qu(int i) { int iColumn; for(iColumn=0;iColumn<8;iColumn++) { if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果无冲突 { Queen[iColumn]='@'; //放皇后 a[iColumn]=1; //标记，下一次该列上不能放皇后 b[i-iColumn+7]=1; //标记，下一次该主对角线上不能放皇后 c[i+iColumn]=1; //标记，下一次该从对角线上不能放皇后 if(i<7) qu(i+1); //如果行还没有遍历完，进入下一行 else //否则输出 { //输出棋盘状态 int iLine,iColumn; printf("第%d种状态为：\n",++iQueenNum); for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn2)this.width=screen.width/2" vspace=2 border=0>; } printf("\n\n"screen.width/2)this.width=screen.width/2" vspace=2 border=0>; } //如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置 Queen[iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 八皇后的c语言解法： #include #include #include int n,k,a[20],num=0; int attack(int k){ int flag=0; int i=1; while ((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i))) i++; if (i==k) flag=1; return flag; } void place(int k) { //printf(" %d",k); int i; if (k==n+1){ num=num+1; printf("num=%d:",num); for (i=1;i<n+1;i++) printf(" %d",a); printf("\n");} else { for (i=1;i<n+1;i++){ a[k]=i; if (attack(k)==1) place(k+1); else a[k]=0; } } } main(){ scanf("%d",&n); k=1; place(k); if (k!=n+1) printf("no solution!\n"); getch(); }
Ⅲ 急求！！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皇后图，称完卷。
Ⅳ 利用《数据结构》课程知识完成C语言程序设计“N皇后问题”（堆栈，一维数组，普通算法都可以，用C语言写
#include<stdio.h>//N皇后问题
#include<
stdlib.h
>
#include<stdio.h>
#include<
iostream.h
>
#include<
time.h
>
#include<dos.h>
#include<malloc.h>
typedefstruct{
int*elem;
intlength;
intlistsize;
}Sqlist;
intInitList(Sqlist&L){//初始化
L.elem=(int*)malloc(100*sizeof(int));
if(!L.elem)
return0;
L.length=0;
L.listsize=100;
return1;
}
intInsert(Sqlist&L,inte){//插入
intm=0,i=0;
int*p=&L.elem[0],*j=&L.elem[0];
if(L.length==0)
{*p=e;L.length++;return1;}
for(i;i<L.length;i++)
if(e>=*(p+i))
m=i+1;
for(i=L.length;i>m;i--)
*(j+i)=*(j+i-1);
L.elem[m]=e;
L.length++;
return1;
}
voidPrint(Sqlist&L,intn){//
遍历
打印输出
intk=1,i=0;int*p=&L.elem[0];
for(i=0;i<n*n;i++,k++){
printf("%d",*(p+i));
if(k==n){k=0;printf(" ");}}
printf(" ");
}
intReturnK(Sqlist&L,intk){//返回第K个元素的值
int*p=&L.elem[0];
return*(p+k-1);咐仿
}
voidFuK(Sqlist&L,intk,inte){//将第k个元素赋值为e
int*p=&L.elem[0];
*(p+k-1)=e;
}
intTiaoJian(SqlistL,intn,int&e){//是否满足皇后问题判断
intb[100];
intm=0,h=2*n;
for(intk=0;k<2*n;k++)b[k]=0;
for(inti=1;i<=n*n;i++)
if(ReturnK(L,i)==1)
{b[m]=(i-1)/n+1;m++;b[m]=i-(b[m-1]-1)*n;m++;}
for(intc=0;c<2*n;c++)
if(b[c]==0){h=c;break;}
for(c=0;c<h-2;c=c+2)
for(intd=c+2;d<h;d=d+2)
if(b[c]==b[d]||b[c+1]==b[d+1]||b[d+1]-b[c+1]==b[d]-b[c]||b[d+1]-b[c+1]==b[c]-b[d])
return0;
if(h==2*n){
printf(" %d皇后问题第%d个排列衡告纤！ ",n,e);e++;
}
return1;
}
voidTrial(Sqlist&L,inti,intn,int&e){//皇后问题
intj;
if(i>n){Print(L,n);}
elsefor(j=1;j<=n;j++){
FuK(L,n*i-n+j,1);
if(TiaoJian(L,n,e)==1)
Trial(L,i+1,n,e);
FuK(L,n*i-n+j,0);
}
}
voidmain(){
intk,i=0;
printf(" 请输入要n皇后问题个数： ");
scanf("%d",&k);
time_trawtime;
structtm
*timeinfo;
time(友饥&rawtime);
timeinfo=localtime(&rawtime);
SqlistL1;
InitList(L1);
for(i=0;i<k*k;i++)
Insert(L1,0);
inte=1;
Trial(L1,1,k,e);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
time(&rawtime);
timeinfo=localtime(&rawtime);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
printf("哈哈哈哈(^o^)/~ ");
system("pause");
}
Ⅳ n皇后问题的算法
# include <stdio.h>
# include <stdlib.h>
# define MAXN 20
int n,m,good;
int col[MAXN+1],a[MAXN+1];
int b[2*MAXN+1],c[2*MAXN+1];
int main()
{int j;
char awn;
printf("槐脊唤输入n:");scanf("%d",&n);
for(j=0;j<=n;j++)a[j]=1;
for(j=0;j<=2*n;j++)b[j]=c[j]=1;
m=1;col[1]=1;good=1;col[0]=0;
do{
if (good)
if (m==n)
{
printf("列\t\t行\n");
for (j=1;j<=n;j++) printf("%3d\t%d\n",j,col[j]);
scanf("%c",&awn);
if (awn=='铅凯Q'||awn=='q') exit(0);
while (col[m]==n)
{
m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else {
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else {
while (col[m]==n){
m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
}while (m!=0);
}
我看这个30+也要算一野拍阵子
Ⅵ 八皇后问题求解的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
Ⅶ 用回溯法解定和子集问题、0/1背包问题和n皇后问题的算法比较
我只写了一个n皇后的解法，其它的没写，不知道什么意思。程序如下：
#include <iostream>
using namespace std;
#define MAX 5 //数组维数
static int total=0; //算法薯毕总数
int array[MAX][MAX]; //定义数组
void SetArray() //数组置零
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
array[i][j]=0;
}
bool IsTrue(int a,int b) //合法性银手激判断
{
int i,j,len;
for (i=0;i<MAX;i++)
if(array[a][i]==1||array[i][b]==1)
return false;
len=(a<b?a:b);
for(i=a-len,j=b-len;i<MAX&&j<MAX;i++,j++)
if(array[i][j]==1)
return false;
for(i=a,j=b;i<MAX&&j>=0;i++,j--)
if(array[i][j]==1)
return false;
for(i=a,j=b;i>=0&&j<MAX;i--,j++)
if(array[i][j]==1)
return false;
return true;
}
void show() //显示结果
{
int i,j;
cout<<"第"<<++total<<"种结果为："<<endl;
for (i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
cout<<array[i][j]<<" ";
cout<<endl;
}
}
bool Queen(int i) //皇后算法
{
int j;
for(j=0;j<MAX;j++)
{
if(IsTrue(i,j))
{
array[i][j]=1;
if(i==MAX-1)
{
show();
array[i][j]=0;
continue;
}
else if(!Queen(i+1))
{
array[i][j]=0;
continue;
}
}
}
return false;
}
void main()
{
int i;
for(i=0;i<MAX;i++)
{
SetArray();
array[0][i]=1;
Queen(1);
}
}
不明白的可锋袜以来问我。。
Ⅷ N皇后问题
一、问题描述：
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。
输入：
给定棋盘的大小n (n ≤ 13)
输出：
输出有多少种放置方法。
二、解题思路：
要解决N皇后问题，其实就是要解决好怎么放置这n个皇后，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线，在这里我们可以以行优先，就是说皇后的行号按顺序递增，只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。如果不能，则跳到下一列...直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。此即是回溯法的精髓所在。当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解...如此后，即可找出一个n皇后问题的所有可行解。
三、复杂度分析：
关于N皇后问题的复杂度问题可以说是众说纷纭了，自己也改变过好几次，刚开始以为棋盘是n行n列，所以理所当然应该是n^2,后来发现在每列选择可否放置的比较上又做了一次循环，所以应该是n^3，但想了很久，发谨者现判断可否放置的时候不是每次都循环到n,它是根据皇后i的取值而变化的，所以复杂度应该是1/3 n^3左右，即是小于n^3的。
四、测试代码：
在这里我写了两个实现方法，一个是递归回溯，一个是迭代回溯，思路都一样，只是形式不同罢了。
递归回溯：
C代码
#include<stdio.h>
#define N 15
int n; //皇后个数
int sum = 0; //可行解个数
int x[N]; //皇后放置的列数
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen(int t)
{
if(t>n && n>0) //当放置的皇后超过n时，可行解个数加1，老雀此时n必须大于0
sum++;
else
for(int i=1;i<=n;i++)
{
x[t] = i; //标明第t个皇后放在第i列
if(place(t)) //如果可以放在某一位置，则继续放下一皇后
queen(t+1);
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen(1);
if(n == 0) //如果n=0，则可行解个数为0，这种情况一定不要忽略
t = 0;
printf("%d",t);
return 0;
}
迭代回溯：
C代码侍晌早
#include<stdio.h>
#define N 15
int n;
int sum = 0;
int x[N];
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen()
{
x[1] = 0;
int t=1;
while(t>0)
{
x[t]+=1;
while(x[t]<=n && !place(t))
x[t]++;
if(x[t]<=n)
if(t == n)
sum++;
else
x[++t] = 0;
else
t--;
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen();
printf("%d",t);
return 0;
}
迭代回溯的注释因为和递归回溯差不多，所以就不再附注了。在这里我们可以看到，递归回溯非常简单，结构很清晰，但它有一个潜在的问题存在，即当随着变量n的增大，递归法的复杂度也将成几何级增长，也有可能会出现重复的情况，所以我们在解决问题时，如果能用迭代法解决，最好还是不要用递归法，除非你已经对这个递归了如指掌了。
通过这个N皇后问题，我想大概已经把回溯法讲得很清楚了吧，回溯法得到的解展开就是一个树，很多方法都是可以通过回溯法来解决的，效率很高，但如果基数过大的话，回溯法就显得不是那么适用了，这也是回溯法的弱势吧。比如说这个N皇后问题，好像当n>60的时候，回溯法就不能完全地解决问题了，这时可以考虑用概率算法来解决，它可以解决很大的基数，只不过结果不是很精确而已。所以我们在面对一个问题时，具体是使用什么算法还是要结合实际情况来考虑的，目的都是更方便、更准确地解决问题。
Ⅸ 皇后问题为什么能同时求出多个解
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。
一、 求解N皇后问题是算法中回溯法应用的一个经典案例
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中颤前宏找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。
下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：
1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
3) 在当前位置上满足条件的情形：
在当前位置放一个皇后，若当前行是最后一行，记录一个解；
若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
若当前行是最后一行，当前列是最后茄册一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
以上返回到第2步
4) 在当前位置上不满足条件的情形：
若当前列不是最后一列，当前列设为下一列，返回到第2步;
若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。
在具体解决该问题时，可以将其拆分为几个小问题。首先就是在棋盘上如何判断两个皇后是否能够相互攻击，在最初接触这个问题时，首先想到的方法就是把棋盘存储为一个二维数组，然后在需要在第i行第j列放置皇后时，根据问题的描述，首先判断是在第i行是否有皇后，由于每行只有一个皇后，这个判断也可以省略，然后判断第j列是否有皇后，这个也很简单，最后需要判断在同一斜线上是否有皇后，按照该方法需要判断两次，正对角线方向和负对角线方向，总体来说也不难。但是写完之后，总感觉很笨，因为在N皇后问题中这个函数的使用次数太多了，而这样做效率较差，个人感觉很不爽。上网查看了别人的实现之后大吃一惊，大牛们都是使用一个一维数组来存储棋盘，在某个位置上是否有皇后可以相互攻击的判断也很简单。具体细节如下：
把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有悔或规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
Ⅹ 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;
}