The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
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..”] ]
思路：回溯法。一行一行的放置并判断是否有效，递归调用解决函数，直到最后一行都检查有效时返回结果。期间若无效则回溯。判断是否有效时因为是一行一行的放置，所以行重复不用判断，只用判断之前行的列重复和两个对角线重复。
class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>>res; vector<string>nQueens(n,string(n,'.')); SolveNQueens(res,nQueens,0,n); return res; } void SolveNQueens(vector<vector<string>>&res,vector<string>&nQueens,int row,int n){ if(row==n){ res.push_back(nQueens); return; } for(int col=0;col<n;col++){ if(isValid(nQueens,row,col,n)){ nQueens[row][col]='Q'; SolveNQueens(res,nQueens,row+1,n); nQueens[row][col]='.'; } } } bool isValid(vector<string>&nQueens,int row,int col,int n){ for(int i=0;i<row;i++){ if(nQueens[i][col]=='Q') return false; } for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){ if(nQueens[i][j]=='Q') return false; } for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){ if(nQueens[i][j]=='Q') return false; } return true; } };