n皇后问题分支限界算法

A. c语言 N皇后问题

q[j] == i表示与上个棋子同列（同行是不可能，不用考虑），还有情况得舍弃的就是斜线，左斜和右斜，)(abs(q[j]-i)==(abs(j-k))))这个就表示与前面的棋子是否在同一斜线，左斜右斜都包括了，你自己写写就能总结出这个式子了，数学计算而已。不懂HI我

B. N皇后问题,提交queen.pas

n皇后问题（非递归）
top := 1; // 从第一个皇后开始尝试
while (top > 0) do // 当还有活动节点时循环
if (top > n) then // 是否n个皇后都放置在棋盘了
begin
inc(count); // 找到一组解，总数加一
dec(top); // 回到上一皇后继续
end
else // n个皇后还没有都放置好
begin
inc(x[top]); // 当前皇后到下一列
if (x[top] > n) then // 是否超出棋盘
dec(top) // 超出棋盘，回到上一个皇后继续
else // 没有超出棋盘
if check(top) then // 检查当前位置是否可以放皇后
begin
inc(top); // 可以放置，继续尝试下一个皇后
x[top] := 0; // 下一个皇后从第一列开始尝试
end;
end;
n皇后问题（边界判定）
function check(pos: integer): boolean;
var
i: integer;
begin
check := true;
for i := 1 to pos - 1 do
if (x[pos] = x[i]) or (abs(x[pos] - x[i]) = abs(pos - i)) then
begin
check := false;
break;
end;
end;
n皇后问题（递归）
procere search(k: integer);
var
i: integer;
begin
if k > n then // 是否前n个皇后都已经放下
inc(count)
else // 还有皇后没放
for i := 1 to n do // 从第1列开始逐列尝试
begin
x[k] := i; // 把第k个皇后放在第i列
if check(k) then // 第k个皇后是否可以放在第i列
search(k + 1); // 可以放，继续处理第k+1个皇后
end;
end;

C. 谁有n皇后问题的答案

八皇后问题程序及注解
http://www.mydrs.org 2003-12-3 大榕树

大家一定见过这种办法吧 ,但是做为初学者理解起来特别困难 ,我就把我当时对它的理解简单说一下,不对的地方大家给个 建议!
program eightqueens;
var
x:array[1..8] of integer;
a,b,c:array[-7..16] of boolean;
i:integer;
procere print;
var k:integer;
begin
for k:=1 to 8 do write(x[k]:4);
writeln;
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to 8 do
if a[j] and b[i+j] and c[i-j]
then begin
x:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<8 then try(i+1)
else print;
a[j]:=true;
b[i+j]:=true;
c[i-j]:=true
end
end;
begin
for i:=-7 to 16 do
begin
a:=true;
b:=true;
c:=true
end;
try(1);
end. 现在循环从 i=1 ,j:=1 to 8 do 开始 此时 计算机检测到 i=1 j=1 简化为(1,1)为空,占用该位置并令该位置对应的斜线和水平方向的位置为 false ,然后程序就开始去执行try(2),注意此时计算机在i=1 这层仅仅走拉一个循环(j=1)就跳到拉i=2 这层里此时计算机从j:=1 to 8 do 又开始循环,排除 j=1,j=2 得到 (2,3)注意计算机在层里也只是走拉3(j=3)个循环然后又跳到拉i=3 这层依次类推得到(3,5),(4,2)(5,4)而在i=6 这层里计算机从j:= 1 to 8 do 都没有找到合适的位置,此时注意在i=6 这层里计算机计算机将返回到i=5 这层里,(因为用拉递归)并且释放(5,4)该位置,为什么要释放呢?因为原因很简单如果不释放的话 该位置对应的斜线和水平方向会对以后的几层造成影响,让计算机误认为为false.此时的在i=5这层里 j=4才是结束,然后计算机又会从j=5到 8 开始去找合适的位置 ,如果找不到又会返回到上一层依次类推直到计算机找到一组解 输出,假设在(8,3)这个位置是计算机找到的一组解,此时计算机又会从j=4到8 开始循环,如果找不到 计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环,依次类推不断的返回,跳出, 求解,(即令前几个位置不变,从第8个位置变换,没有空位置的.接会返回上一层)最后返回到i=1这层里,注意此时在这层里也只是走拉j=1个循环然后计算机就又开始从j= 2 去试着找....大家有没有算过求出所有的解要走过多少个循环?我想估计也不下1000个吧.其实整个过程就是一个重复的过程(即递归)倒着想在i=7 这层里的j=1 位置即(7,1) 计算机会去试从(8,1)到(8,8)这8 个位置,而在(7,2)也同样会去试这8 个位置 等等在(6,1)会试(7,1)到(7,8) 等. 这是正着考虑(1,1)这里计算机会试着从(2,1)到(2,8)这8个位置而在这8 个位置里并没有试完就有空位置 (2,3)此时计算机会在这个位置对下一层里开始试(3,1)..(3,8)依次类推,试不通的返回,接着走完上一层直到试完所有的位置!

D. N皇后问题 C++

#include<iostream>

#include<cstdio>

using namespace std;

int q[1000],s=0,n;

bool a[1000]={0},b[1000]={0},c[1000]={0};

void search(int i){

int j;

for(j=1;j<=n;j++){

if((!a[j])&&(!b[i+j])&&(!c[i-j+n-1])){

q[i]=j;

a[j]=1;

b[i+j]=1;

c[i-j+n-1]=1;

if(i==n)s++;

if(i!=n)search(i+1);

a[j]=0;

b[i+j]=0;

c[i-j+n-1]=0;}}}

int main(){

cin>>n;

search(1);

cout<<s;}

E. n皇后问题 c++

回溯法程序：
#include<iostream.h>
#include<string.h>
#include<time.h>
#define size 100
int board[size];
int ver[size];
int ru[size*2];//右上
int rd[size*2];//右下
int n,find; int rec[size];
//回溯搜索
void dfs(int t)
{
int i;
if(find) return;
if(t==n)
{
find=1;
for(i=0;i<n;i++)
{
rec[i]=board[i];
}
return;
}
for(i=0;i<n;i++)
{
if(ver[i]==1) continue;
if(ru[i-t+n]==1) continue;
if(rd[i+t]==1) continue;
ver[i]=1;
ru[i-t+n]=1;
rd[i+t]=1;
board[t]=i;
dfs(t+1);
rd[i+t]=0;
ru[i-t+n]=0;
ver[i]=0;
}
return;
}
int main()
{
int i,j,t1,t2;
cout<<"输入棋盘大小：";
cin>>n;
t1=clock();
find=0; memset(ver,0,sizeof(ver));
memset(ru,0,sizeof(ru)); memset(rd,0,sizeof(rd));
dfs(0);
t2=clock();
if(find)
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(rec[i]==j) cout<<'X';
else cout<<'+';
}
cout<<endl;
}
else
cout<<"Can't find!n";
cout<<"耗费时间："<<t2-t1<<"msn";
return 0;
}

既然是回溯法，楼主可以看看回溯法
---------2 回溯法：如果在第i行无论如何放置皇后，都和前面i-1行的皇后互相攻击的话，说明i-1行的皇后位置不合理，于是就回退一行，重新计算。这类似于走迷宫，如果在某个路口实在不下去了，只好退后一步重新选择。在退后一步重新选择的时候，显然可以排除已经尝过的路线。

下面重点分析回溯法解决N皇后问题。

很容易想到，在同一行上只能放置一个皇后，因此nxn的棋盘上放n个皇后的方案必然是每一行上放一个皇后。这样的话，我们可以使用一个一维数组q[n]来保存最后的方案，其中q[i]的含义是第i行上皇后的位置。比如q[3]=5，则表示第三行上的皇后在第5格。

上面无论哪种方法，都要解决一个问题：如何量化的判断两个皇后是否相互攻击？有了数组q的定义，我们很容易发现如下的规律：

对于两个皇后q[i]和q[j]，互相不攻击的条件是：
1 i != j，即不在同一行。
2 q[i] != q[j]，即不再同一列。
3 |q[i] - q[j]| != |i - j|，即不在一个对角线上。

根据前面的分析，我们假设前面的i-1行的皇后已经布好，即互不攻击，则在第i行上的皇后位置为q[i]，那么我们可以把q[i]依次和前面的i-1行比较，如果q[i]和前面的i-1行互不攻击的话，则说明第i行的皇后q[i]就是一个合理的位置，则继续寻找i+1行的皇后合理位置。如果第i行的皇后和前面的i-1行的某个皇后有攻击，则第i行的皇后需要右移一格，重新和前面的i-1行进行比较。

在进行具体处理时，要注意边界条件，即回退到棋盘第一行以及皇后已经右移到棋盘的最后一行的最后一格的情况，都意味着当前皇后位置使得N皇后问题无解。

下面是算法：

PROCEDURE QUEEN(n)
FOR i = 1 TO n DO q[i] = 1
i = 1
loop:
IF(q[i] <= n) THEN
{
k = 1
WHILE((k < i) and ((q[k] - q[i])) * (|q[k] - q[i]| - |k - i| ) != 0)
DO k = k + 1

IF(k < i) THEN q[i] = q[i] + 1
ELSE
{
i = i + 1
IF(i > n) THEN
{
OUTPUT q[i] (i = 1,2,...,n)
q[n] = q[n] + 1
i = n
}
}
}
ELSE
{
q[i] = 1
i = i - 1
IF(i < 1) THEN RETURN
q[i] = q[i] + 1
}

TOGO loop
RETURN

F. 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;
}

G. 急求！！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皇后图，称完卷。

H. c语言常用算法有哪些

0） 穷举法
穷举法简单粗暴，没有什么问题是搞不定的，只要你肯花时间。同时对于小数据量，穷举法就是最优秀的算法。就像太祖长拳，简单，人人都能会，能解决问题，但是与真正的高手过招，就颓了。
1） 贪婪算法
贪婪算法可以获取到问题的局部最优解，不一定能获取到全局最优解，同时获取最优解的好坏要看贪婪策略的选择。特点就是简单，能获取到局部最优解。就像打狗棍法，同一套棍法，洪七公和鲁有脚的水平就差太多了，因此同样是贪婪算法，不同的贪婪策略会导致得到差异非常大的结果。
2） 动态规划算法
当最优化问题具有重复子问题和最优子结构的时候，就是动态规划出场的时候了。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。就像斗转星移武功，对手强它也会比较强，对手若，他也会比较弱。
3）分治算法
分治算法的逻辑更简单了，就是一个词，分而治之。分治算法就是把一个大的问题分为若干个子问题，然后在子问题继续向下分，一直到base cases，通过base cases的解决，一步步向上，最终解决最初的大问题。分治算法是递归的典型应用。
4） 回溯算法
回溯算法是深度优先策略的典型应用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个
分岔路，在选一条路走，一直这样递归下去，直到遍历万所有的路径。八皇后问题是回溯算法的一个经典问题，还有一个经典的应用场景就是迷宫问题。
5） 分支限界算法
回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。

I. pascal跳马问题的思路

用回溯和递归结合
有个例子参考

n皇后问题的递归算法如下：

program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.

程序2：

说明:当n=8 时有30条对角线分别用了l和r数组控制，

用c数组控制列.当(i,j)点放好皇后后相应的对角线和列都为false.递归程序如下:

program nhh;
const n=8;
var s,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;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
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 output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
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;
s:=0;try(1);
writeln;
end.