queen8

queen8 八皇后问题

八皇后问题的数学模型：如何能够在 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种解决方案：