Leetcode51.n queen

link ：

https://leetcode-cn.com/problems/n-queens/

describe ：

Example ：

Code ：

class Solution {
    
public:
	vector<vector<string>> solveNQueens(int n) {
    
		// Store all solutions by coordinate position 
		vector<vector<pair<int, int>>> solutions;
		// The location of all queens in a solution 
		vector<pair<int, int>> solution;
		DFS(solutions, solution, 0, n);
		// Turn the coordinate position into string
		return transResult(solutions, n);
	}
	void DFS(vector<vector<pair<int, int>>>& solutions, vector<pair<int, int>>& solution, int curRow, int n)
	{
    
		if (curRow == n) solutions.push_back(solution);
		// Try whether a queen can be placed at each position of the current line 
		for (int col = 0; col < n; ++col) {
    
			if (isValid(solution, curRow, col)) {
    
				// If possible , Save the current location , Continue to determine the position of the queen in the next row 
				// Call the constructor directly , Internal construction pair,  Or call make_pair
				solution.emplace_back(curRow, col);
				DFS(solutions, solution, curRow + 1, n);
				// to flash back , Delete current location , Try another location on the current line 
				solution.pop_back();
			}
		}
	}
	// solution:  One solution , From the first line to the previous line of the current line, each line has placed the Queen's point 
	bool isValid(vector<pair<int, int>>& solution, int row, int col) {
    
		//  Judge whether the queen position of the current line is in conflict with the queen position of the previous lines 
		// i.second == col:  The first i Queens are in the same column as the current point 
		// i.first + i.second == row + col:  The first i A queen is on the left with the current point , Abscissa + The ordinate values are the same 
		// i.first - i.second == row - col： The first i A queen is pressed with the current point ,  Abscissa - The ordinate values are the same 
		for (pair<int, int>& i : solution)
			if (i.second == col || i.first + i.second == row + col
				|| i.first - i.second == row - col)
				return false;
		return true;
	}
	vector<vector<string>> transResult(vector<vector<pair<int, int>>>& solutions, int n) {
    
		vector<string> tmp();
		// Turn every solution into string form , final result 
		vector<vector<string>> ret;
		for (vector<pair<int, int>>& solution : solutions) {
    
			//n*n char:  Each row has n Elements , Change the Queen's position to Q
			vector<string> solutionString(n, string(n, '.'));
			for (pair<int, int>& i : solution) {
    
				solutionString[i.first][i.second] = 'Q';
			}
			ret.push_back(solutionString);
		}
		return ret;
	}
};