n皇后问题

曾经终败给现在 2022-08-20 06:24 211阅读 0赞

目前会的一种解决n皇后的方法，在笔记本上大概能解除10以内的问题，更大规模的还要再去学习其他的人的好方法

#include<iostream>
    using namespace std;
    class Queen
    {
    private:
    	int N;                            //皇后的个数
    	int sum;                          //解法数
    	int *result;                      //保存信息
    public:
    	Queen();
    	~Queen(){ delete result; }
    	void find(int num);               //回朔法
    	void print();                     //打印N皇后
    	bool check(int num);              //检查放入后是否有冲突
    	int getSum()const;                //返回sum
    };
    Queen::Queen()
    {
    	sum = 0;
    	cout << "现有N*N的棋盘，放入N个皇后，要求所有皇后不在同一行、列和同一斜线上！" << endl;
    	cout << endl << "请输入皇后的个数： ";
    	cin >> N;
    	result = new int[N];
    }
    int Queen::getSum()const 
    {
    	return sum;
    }
    void Queen::find(int num)
    {
    	if (num == N)          //放入第N个皇后后，说明已经成功，可以打印
    	{
    		print();
    		return;
    	}
    	for (int i = 0; i < N; i++)     //回朔法
    	{
    		result[num] = i;
    		if (check(num))
    		{
    			find(num + 1);
    		}
    	}
    }
    bool Queen::check(int num)   //检查放入后是否有冲突
    {
    	for (int i = 0; i < num; i++)
    	{
    		if (result[num] == result[i] || abs(num - i) == abs(result[num] - result[i]))
    			return false;
    	}
    	return true;
    }
    void Queen::print()         //打印N皇后
    {
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < N; j++)
    		{
    			if (result[i] != j)
    				cout << 0 << " ";
    			else
    				cout << "X ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    	sum++;
    }
    int main()
    {
    	Queen myqueen;
    	cout << "皇后摆法：" << endl << endl;
    	myqueen.find(0);
    	cout << "共有" << myqueen.getSum() << "种解法！" << endl;
    	system("pause");
    	return 0;
    }