八皇后问题

1. 八皇后问题介绍

要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。

2.解决思想：

• 我们可以设8个皇后分别排在1,2,3,4,5,6,7,8行上。
• a[1],a[2].....a[8]的值分别表示每一行上的皇后位于第几列。。
• 要求每一个皇后不在同一行，这一要求已经在步骤1中默认达到。要求每一行的皇后不在同一列，同一对角线，可以使用两个for来实现，判断语句是if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))则说明不符合要求。

3.解决方法：

3.1暴力枚举法：

使用八重循环，遍历每一行所有的列，从中找出满足条件的解：

#include <iostream>
using namespace std;
bool check_1(int a[],int n)
{
for(int i=2;i<=n;i++)       //要使用双重循环，因为每一行都要与前面所有行进行比较
{
    for(int j=1;j<=i-1;j++)
    {
        if ((a[i]==a[j])||(abs(a[i]-a[j])==i-j))
        {
            return false;
        }
    }
}
return true;
}

void queens_1()
{
    int a[9];
    int count = 0;
    for(a[1]=1;a[1]<=8;a[1]++)
    {
        for(a[2]=1;a[2]<=8;a[2]++)
        {
            for(a[3]=1;a[3]<=8;a[3]++)
            {
                for(a[4]=1;a[4]<=8;a[4]++)
                {
                    for(a[5]=1;a[5]<=8;a[5]++)
                    {
                        for(a[6]=1;a[6]<=8;a[6]++)
                        {
                            for(a[7]=1;a[7]<=8;a[7]++)
                            {
                                for(a[8]=1;a[8]<=8;a[8]++)
                                {
                                    if(!check_1(a,8))   
                                        continue;
                                    else
                                    {
                                        for(int i=1;i<=8;i++)  
                                        {
                                            cout<<a[i];
                                        }
                                        cout<<endl;
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }

        }
    }
    cout<<count<<endl;
}

void main()
{
    queens_1();
}

3.2 递归方法

int a[9], n, count;

bool check_2 (int a[ ],int n)
{   
    /*这里只用一层循环，是因为该方法每放置一个皇后就对条件进行判断,而不是跟
    方法1一样枚举完所有的行上的皇后再进行判断*/
    for(int i=1;i<=n-1;i++)
    {
        if((abs(a[i]-a[n])==n-i)||(a[i]==a[n]))
            return false;
    }      
    return true;
}

void recursion(int k)
{
    if (k>n)//如果递归到放置第9行上的皇后，则退出递归
    {
        for(int i=1;i<=8;i++)  
        {
            cout<<a[i];
        }
        cout<<endl;
        count++;
        return ;
    }
    else
    {
        for (int i = 1;i <=n; i++)
        {
            a[k] = i;
            if (check_2(a,k) == 1)
            {backtrack(k+1);}
        }
    }
    
}

void main()
{
    n=8,count=0;
    recursion(1);
    cout<<count<<endl;
}