八皇后问题

冷不防 2022-08-03 00:49 234阅读 0赞

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。试解出92种结果。

![Center][]

// eight_queen.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    
    #include<deque>
    #include<iostream>
    
    
    using namespace std;
    
    
    #define N 8
    
    
    typedef unsigned char BYTE;
    
    
    BYTE chess_board[N][N] = { 0 };
    deque<deque<BYTE>>record, solution;
    
    deque<BYTE>cc;
    deque<BYTE>bb;
    
    
    bool update(int height)
    {
    	cc.clear();
    	chess_board[height][bb[height]] = 1;
    	for (int i = 0; i < N; i++)
    	{
    		chess_board[height][i] = 1;
    		chess_board[i][bb[height]] = 1;
    		if (height - bb[height] + i >= 0 && height - bb[height] + i <= N - 1)
    			chess_board[height - bb[height] + i][i] = 1;
    		if (height + bb[height] - i >= 0 && height + bb[height] - i <= N - 1)//右上左下
    			chess_board[height + bb[height] - i][i] = 1;
    	}
    
    	for (int i = 0; i < N; i++)
    		if (chess_board[height + 1][i] == 0)
    			cc.push_back(i);
    	if (!cc.empty())
    	{
    		return true;
    	}
    	return false;
    }
    
    
    
    
    void eight_queen()
    {
    
    	for (int i = 0; i < N; i++)
    	{
    		bb.push_back(i);
    	}
    	record.push_back(bb);
    	bb.clear();
    	int k = 0;
    
    	while (k < N)
    	{
    		if (!record.empty())
    		{
    			if (record[k].empty())
    			{
    				while (record[k].empty())
    				{
    					record.pop_back();
    					if (record.empty())
    						return;
    					bb.pop_back();
    					k--;
    				}
    				for (int i = 0; i < N; i++)
    					for (int j = 0; j < N; j++)
    						chess_board[i][j] = 0;
    				for (int i = 0; i < k; i++)
    					update(i);
    			}
    			bb.push_back(record[k][0]);
    			record[k].pop_front();
    		}
    
    		if (!update(k))
    		{
    			while (!update(k))
    			{
    				
    				if (record[k].empty())
    				{
    					while (record[k].empty())
    					{
    						record.pop_back();
    						if (record.empty())
    							return;
    						k--;
    						for (int i = 0; i < N; i++)
    							for (int j = 0; j < N; j++)
    								chess_board[i][j] = 0;
    						for (int i = 0; i < k; i++)
    							update(i);
    						bb.pop_back();
    					}
    					bb.pop_back();
    					break;
    				}
    
    				else
    				{
    
    					bb[k] = record[k][0];
    					record[k].pop_front();
    					for (int i = 0; i < N; i++)
    						for (int j = 0; j < N; j++)
    							chess_board[i][j] = 0;
    					for (int i = 0; i < k; i++)
    						update(i);
    
    					if (update(k))
    					{
    						if (k == N - 2)
    						{
    							deque<BYTE> dd;
    							dd = bb;
    							dd.push_back(0);
    							for (int i = 0; i < cc.size(); i++)
    							{
    								dd[N - 1] = cc[i];
    								solution.push_back(dd);
    							}
    							
    							bb.pop_back();
    							for (int i = 0; i < N; i++)
    								for (int j = 0; j < N; j++)
    									chess_board[i][j] = 0;
    							for (int i = 0; i < k; i++)
    								update(i);
    						}
    						else
    						{
    							record.push_back(cc);
    							k++;
    						}
    						break;
    					}
    				}
    
    			}
    		}
    		else
    		{
    			if (k == N - 2)
    			{
    				deque<BYTE> dd;
    				dd = bb;
    				dd.push_back(0);
    				for (int i = 0; i < cc.size(); i++)
    				{
    					dd[N - 1] = cc[i];
    					solution.push_back(dd);
    				}
    			
    				bb.pop_back();
    				for (int i = 0; i < N; i++)
    					for (int j = 0; j < N; j++)
    						chess_board[i][j] = 0;
    				for (int i = 0; i < k; i++)
    					update(i);
    			}
    			else
    			{
    				record.push_back(cc);
    				k++;
    			}
    		}
    	}
    
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	eight_queen();
    
    	system("pause");
    	return 0;
    }

[Center]: /images/20220731/b2e4b6082c774b4183683a51572b7e17.png