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.."]]

解题思路：

使用回溯法解决N皇后问题，是常见的解决方法。分N步放置皇后，由于皇后之间不能同行、同列、同斜线，所以每次放置皇后的时候，都要考虑是否与已有的皇后“冲突”，如果冲突，则改变位置，直至所有皇后放置完毕。

测试皇后冲突的函数：isValid()；

本文思路比较取巧，使用a[n]记录N皇后位置。根据皇后放置规则可知，每一行有且只有一个皇后，所以从第一行到第N行，依次放置第n个皇后。a[n]记录第n个皇后所在列数。即第i个皇后放置在第i行第a[i]列。

参考：http://blog.csdn.net/feixiaoxing/article/details/6877965

具体实现如下（AC 36ms）：

class Solution {public:    vector<vector<string> > re;    //测试在第row行，第row列放置皇后是否有效     int isValid(int *a, int n, int row, int col)    {    	int tmpcol=0;    	for(int tmprow=0;tmprow<row;tmprow++)    	{    		tmpcol = a[tmprow];    		if(tmpcol == col)// 同列    			return 0;    		if((tmpcol-col) == (tmprow - row))// 在同一右斜线    			return 0;    		if((tmpcol-col) == (row - tmprow))// 在同一左斜线    			return 0;    	}    	return 1;	    }        void PrintN(int *a, int n)    {    	vector<string> tmps;    	for(int i=0;i<n;i++)    	{    		string s(n,‘.‘);    		s[a[i]]=‘Q‘;    		tmps.push_back(s);		    	}    	re.push_back(tmps);    }    void n_queens(int *a,int n, int index)    {    	for(int i=0;i<n;i++)    	{    		if(isValid(a,n,index,i))    		{    			a[index]=i;    			if(index == n-1)    			{    				PrintN(a,n);    				a[index]=0;    				return;    			}    			n_queens(a,n,index+1);    			a[index]=0;    		}    	}    }        vector<vector<string> > solveNQueens(int n) {    	        int *a = new int[n];        memset(a,0,sizeof(int)*n);        n_queens(a,n,0);        return re;    }};

N皇后个数对应解的个数：（验证程序）