程序员面试题精选100题(58)-八皇后问题

字号:|
2019-09-22    FW.5VV.CN范文网
    // 程序员面试题精选100题(58)-八皇后问题.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    static int sum=0;
    void swap(int &a,int &b)
    {
        int temp;
        temp=a;
        a=b;
        b=temp;
    }
    bool isqueen(int *arr,int n)
    {
        bool flag=true;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (i!=j)
                {
                    if (i-j==arr[i]-arr[j]||i-j==arr[j]-arr[i])
                    {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    void permution(int *arr,int i,int n)
    {
        if (i==n-1)
        {
            if (isqueen(arr,n))
            {
                sum++;
                for (int j=0;j<n;j++)
                {
                    cout<<arr[j]<<" ";
                }
                cout<<endl;
            }
        }
        else
        {
            permution(arr,i+1,n);
            for (int k=i+1;k<n;k++)
            {
                swap(arr[i],arr[k]);
                permution(arr,i+1,n);
                swap(arr[i],arr[k]);
            }
        }
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        int arr[]={0,1,2,3,4,5,6,7};
        permution(arr,0,8);
        cout<<"sum is "<<sum<<endl;
        system("pause");
        return 0;
    }

记得两三年前在林大的820自习室花了一天的时间做这道题,现在依然是看答案后才想出来。这题关键一是确定了用一元数组的数据结构后。二是采用排列的方式。三是如何判定符合条件