问题描述:
在n*n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线。
盲目的迭代枚举：
/*
*作者：xymaqingxiang
*说明：八皇后——盲目迭代法
*分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案
*日期：2014-05-15
*/
#include <iostream>
#include <cstdlib>
using namespace std;
bool place(int a[],int n)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=i-;j++)
{
if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))//不同列和不同斜线约束
{
return false;//位置冲突
}
}
}
return true;//不冲突
} void queens()
{
int a[];
int count = ;
//每个皇后都从第一列位置开始判断
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
if(!place(a,)) //判断位置的合法性
continue;
else
{
for(int i=;i<=;i++)
{
cout<<a[i]; //打印满足约束的可行性放置方案
}
cout<<endl;
count++;
}
}
}
}
}
}
} }
}
cout<<count<<endl;
} void main()
{
queens();
system("pause");
}
盲目枚举——nQueen
/*
*作者：xymaqingxiang
*说明：八皇后——盲目迭代法
*分析：通过8重循环模拟搜索空间中的8^8个状态，从中找出满足约束条件的可行性方案，但是这样会走很多冤枉路，而回溯的思想就是——走不通则掉头
所以在下面的算法实现中，每进行一个皇后位置的讨论就立刻进行位置的检查，不满足则结束本路径，回头走下一路径，这样便能减少很多冤枉路。
本算法虽可读性良好，但仍局限于解决8皇后问题，对于解决任何N皇后问题还要修改程序结构，不能把皇后个数n作为参数传递给函数，不具有普遍性。
而且程序中出现了大量的for循环，而且for循环的结构很相似，自然让我们想到迭代回溯，即下面我们要讨论的递归回溯和非递归回溯
*日期：2014-05-15
*/
#include <iostream>
#include <cstdlib>
using namespace std;
bool place(int a[ ],int n)
{//多次被调用，只需一重循环
for(int i=;i<=n-;i++)
{
if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))
return false;
}
return true;
} void queens()
{
int a[];
int count = ;
for(a[]=;a[]<=;a[]++)
{
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,)) continue;
for(a[]=;a[]<=;a[]++)
{
if (!place(a,))
continue;
else
{
for(int i=;i<=;i++)
{
cout<<a[i];
}
cout<<endl;
count++;
}
}
}
}
}
}
} }
}
cout<<count<<endl;
} void main()
{
queens();
system("pause");
}
改进版盲目枚举——nQueen
以上两种算法虽可读性良好，但仍局限于解决8皇后问题，对于解决任何N皇后问题还要修改程序结构，不能把皇后个数n作为参数传递给函数，不具有普遍性。而且程序中出现了大量的for循环，而且for循环的结构很相似，自然让我们想到迭代回溯，即下面我们要讨论的递归回溯和非递归回溯。
算法分析：
用n元组x[1:n]表示n后问题的解，其中x[i]表示皇后 i 放在棋盘的第 i 行的第x[i]列。
不同行：事先规定好 i 号皇后只能放置在 i 行上，这样就解决了同行的问题。
不同列：解向量中的x[i]互不相同，即x[i]!=x[j]，如此便实现了不同列的限制。
不同斜线：最终任意两个皇后的位置(i,x[i])和(j,x[j])不在同一斜线，即斜率的绝对值不能为1，也就是|j-i|!=|x[j]-x[i]|。
用回溯法解决n后问题时，用完全n叉树表示解空间，可行性约束Place减去不满足行、列和斜线约束的子树。
下面具体解n后问题的回溯法中，递归函数Backtrack(1)实现对整个解空间的回溯搜索。Backtrack(i)搜索解空间中的第 i 层子树。类Queen的数据成员记录解空间结点信息，以减少传给Backtrack的参数。sum记录当前已找到的可行方案数。
在算法Backtrack中：
1、 当i>n时，算法搜索至叶节点，得到一个新的n皇后互不攻击放置方案，当前已找到的可行方案数sum加1。
2 、当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,3....n共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由Place检察其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。
算法描述1：————子集树（仅仅隐藏掉行约束）——规定好行位置，列位置从第一列开始讨论
#include <iostream>
#include <cstdlib>
using namespace std;
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n, //皇后个数
* x; //当前解空间
long sum; //当前已找到的可行方案数
};
bool Queen::Place(int k) //位置检查，满足约束则返回true，否则返回false
{
for(int j=;j<k;j++) //检查k个皇后不同列和不同斜线的约束语句
if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
return false;
return true;
}
void Queen::Backtrack(int t)
{
if(t>n)
sum++; //搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1
else
for(int i=;i<=n;i++)
{
x[t] = i; //确定第 i 个皇后的列位置
if(Place(t)) //检查放置位置是否满足约束条件
Backtrack(t+); //深度优先搜索可行子树
}
}
int nQueen(int n)
{
Queen X; //定义并初始化X的信息
X.n = n;
X.sum = ;
int *p = new int [n+];
for(int i=;i<=n;i++)
p[i] = ;
X.x = p;
X.Backtrack();
delete [] p;
cout<<X.sum<<endl;
return X.sum;
}
int main()
{
nQueen();
nQueen();
nQueen();
return ;
}
迭代回溯：
数组x 记录了解空间树中从根到当前扩展结点的路径，这些信息已包含了回溯法在回溯时所需要的信息。利用数组x 所含的信息，可将上述回溯法表示成非递归形式，进一步省去O(n)递归栈空间。
具体的算法描述为：
#include <iostream>
#include <cstdlib>
using namespace std;
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(void);//.........
int n,
* x;
long sum;
};
bool Queen::Place(int k) //位置检查函数，满足约束返回true，不满足返回false
{
for(int j=;j<k;j++)
if( ( abs(k-j) == abs(x[j]-x[k]) ) ||( x[j] == x[k] ) )
return false;
return true;
}
void Queen::Backtrack(void)//非递归实现
{
x[] = ; //x[1]赋初值为0
int k = ; //从第一个皇后开始讨论
while(k>)
{
x[k]+=; //x[1]赋初值为0，加1后，表示首先从第一列开始放
while( (x[k]<=n) && !(Place(k)) )//k还不是最后的叶子结点，且位置没有冲突，满足Place函数的约束————x[k]代表列的位置，没有超出列的限制
x[k] += ; //在没有超出列的限制且不满足Place函数位置约束时，列后移
if(x[k] <= n) //没有超出列的限制范围
if(k == n) //k是叶子结点，已经讨论到最后一个皇后
sum++; //可行方案数加1
else
{ //未到达叶子节点(最后一个皇后)，且已经为当前的皇后找到合适的位置，k++后处理下一个皇后的放置位置
k++; //考虑下一个皇后的放置位置
x[k] = ; //初始位置之前赋值为0
}
else
k--; //由于已经超出列的限制范围，且当前正考虑的皇后没有找到合适的位置，则前一个皇后的位置后移，重新来过
}
}
int nQueen(int n)
{
Queen X;
X.n = n;
X.sum = ;
int *p = new int [n+];
for(int i=;i<=n;i++)
p[i] = ;
X.x = p;
X.Backtrack();//......
delete [] p;
cout<<X.sum<<endl;
return X.sum;
}
int main()
{
nQueen();
nQueen();
nQueen();
return ;
}
算法描述2：————排列树（隐藏掉行和列约束）——>规定好行位置的同时，列位置从j（不同于上一个皇后的列）开始讨论
#include <iostream>
#include <cstdlib>
using namespace std;
class Queen{
friend int nQueen(int);
private:
bool Place(int k);
void swap(int t,int i,int *x);
void Backtrack(int t);
int n, //皇后个数
* x;//当前解空间
long sum;//当前已找到的可行方案数
};
bool Queen::Place(int k)//位置检查，满足约束则返回true，否则返回false
{
for(int j=;j<k;j++)//检查k个皇后不同列和不同斜线的约束语句
if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
return false;
return true;
}
void Queen::swap(int t,int i,int *x)
{
int k;
k=x[t];
x[t]=x[i];
x[i]=k;
} void Queen::Backtrack(int t)
{
if(t>n)
{
for(int i=;i<=n;i++) //方案数加1前，先打印符合要求的排列组合
cout<<x[i];
cout<<endl;
sum++;//搜索至叶结点，即讨论完最后一个皇后的位置，得到一个新的不受攻击放置方案，可行方案数加 1
}
else
for(int i=t;i<=n;i++)//控制分支数目，每次都要减一，初始值从t开始而非1
{
swap(t,i,x);//交换位置，得到一种新的排列————轮岗ing
if(Place(t))//检查放置位置是否满足约束条件
Backtrack(t+);//深度优先搜索可行子树
swap(t,i,x);//调回原位置（初始排列组合）———— 众神归位
}
}
int nQueen(int n)
{
Queen X;//定义并初始化X的信息
X.n = n;
X.sum = ;
int *p = new int [n+];
for(int i=;i<=n;i++)
p[i] = i; //给x[i]赋初值，必须是其排列的一种
X.x = p;
X.Backtrack();
cout<<X.sum<<endl;
delete [] p;
return X.sum;
}
int main()
{
nQueen();
nQueen();
nQueen();
system("pause");
return ;
}