LeetCode 51. N-Queens

八皇后问题的延伸版，回溯实现。

class Solution {
public:
bool checkQueen(int** mat, int N, int r, int c) {
	for (int row = 0; row < N; row++) {
		if (row == r)
			continue;
		if (mat[row][c] == 1)
			return false;
	}
	//
	int row = r-1, col = c-1;
	while (row >= 0 && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row--; col--;
	}
	row = r + 1, col = c + 1;
	while (row < N && col < N) {
		if (mat[row][col] == 1)
			return false;
		row++; col++;
	}
	//
	//
	row = r - 1, col = c + 1;
	while (row >= 0 && col < N) {
		if (mat[row][col] == 1)
			return false;
		row--; col++;
	}
	row = r + 1, col = c - 1;
	while (row < N && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row++; col--;
	}
	//
	return true;
}
void nQueensSub(int** mat, int N, int row, int col, vector<vector<string>>& results) {
	if (row == N) {
		//print
		vector<string> result;
		for (int i = 0; i < N; i++) {
			string row;
			for (int j = 0; j < N; j++) {
				if (mat[i][j] == 0)
					row += '.';
				else
					row += 'Q';
			}
			result.push_back(row);
		}
		results.push_back(result);
	}
	else {
		if (checkQueen(mat, N, row, col)) {
			//put queen here
			mat[row][col] = 1;
			//try next row
			nQueensSub(mat, N, row + 1, 0, results);
			mat[row][col] = 0;
		}
		//try next col
		if (col+1 < N) {
			nQueensSub(mat, N, row, col + 1, results);
		}
	}
}
    vector<vector<string>> solveNQueens(int n) {
	    int** mat = new int*[n];
	    for (int i = 0; i < n; i++) {
	    	mat[i] = new int[n];
	    	for (int j = 0; j < n; j++) {
	    		mat[i][j] = 0;
    		}
    	}
    	vector<vector<string>> results;
    	nQueensSub(mat, n, 0, 0, results);
    	for (int i = 0; i < n; i++) {
    		delete[]mat[i];
    	}
    	delete[] mat;
    	return results;
    }
};