leetcode 51. N-Queens

Dear 丶 2022-07-26 06:07 135阅读 0赞

The n\-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

![8-queens.png][]

Given an integer n, return all distinct solutions to the n\-queens puzzle.

Each solution contains a distinct board configuration of the n\-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

For example,  
There exist two distinct solutions to the 4-queens puzzle:

[
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]

这个哥以前就解过了，大概一年前吧，偷懒了，直接粘过来了。

typedef unsigned char BYTE;
    class Solution {
    	int N;
    	vector<vector<BYTE>> chess_board;
    	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++;
    				}
    			}
    		}
    	}
    public:
    	vector<vector<string>> solveNQueens(int n) {
    		vector<vector<string>>re;
    		if (n == 1)
    		{
    			vector<string>v;
    			v.push_back("Q");
    			re.push_back(v);
    			return re;
    		}
    		N = n;
    		chess_board.resize(N);
    		for (int i = 0; i < N; i++)
    			chess_board[i].resize(N);
    		eight_queen();
    		string s = string(N, '.');
    		vector<string> ss(N, s);
    		for (int i = 0; i < solution.size(); i++)
    		{
    			vector<string>aa = ss;
    			for (int j = 0; j < N; j++)
    				aa[j][solution[i][j]] = 'Q';
    			re.push_back(aa);
    		}
    		return re;
    	}
    };

后面52. N-Queens II返回size大小就行了，一样AC

[8-queens.png]: http://www.leetcode.com/wp-content/uploads/2012/03/8-queens.png