八皇后问题
八皇后问题的数学模型：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。
回溯法：解决8queen问题的最简单的思路就是回溯。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：
1、定义一个解空间，它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
适用范围：适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。
采用回溯法解决queen8问题：
我们用试探的方法先对问题做一个初步的解释：
不断的向前试探，但是到第五列的时候，已经找不到一个满足条件的位置了。此时就要回溯，将第五列的皇后拿掉，从当前位置继续向后寻找，即第7个位置，此时第五列仍然没有合适的位置，这时就回退到第4列，再前进一步，后退一步。。。知道找到第八列为止，即找到了一个解决方案。
接下来是代码：
//queen8
#include<iostream>
using namespace std;
#define N 8
int y[N+];
int count;
void print();
bool check(int x);
int main()
{
count = ;
for(int i = ;i<;i++)
y[i]=;
int x = ;
while(x>)
{
y[x]++;
while((y[x]<=N) && (!check(x)))
y[x]++;
if(y[x]<=N)
{
if(x==N)
{
count++;
print();
}
else
x++;
}
else
{
y[x]=;
x--;
}
}
system ("pause");
return ;
}
bool check(int x)
{
for(int j=;j<x;j++)
if(abs(j-x)==abs(y[j]-y[x])||y[j]==y[x])
return false;
return true;
}
void print()
{
cout<<count<<endl;
for(int i = ; i<=N;i++)
{
for(int j = ;j<=N;j++)
if(j==y[j])
cout<<'x';
else
cout<<'o';
cout<<endl;
}
}
这样就找到了所有的92种解决方案：