The solution below is not very elegant, but it follows a generic pattern common in lots of backtracking problems.

Most backtracking problems can be solved with **Depth First Search**. Once we are given such a problem, we should be thinking about solving it step by step. As in this N-Queen problem, a common way is to put a queen one column at a time. By doing so, we know we have finished once we are handling the nth column.

For every column, we want to put a queen without violating the rules. Once our move is invalid, we undo the move and try another move in the same column. Every time we have a complete set of moves that maintain the rules, we add the board config to the solution set.

Some important parameters are **index**, **cur**, and **ret**. **index** indicates where we are in solving the problems. Since we only have n columns, reaching index n means we have checked the previous n moves and is ready to add to solution set. **cur** refers to the current solution we are building. In this case, the unfinished n-queen board. **ret** is the solution set to keep a record of all valid board configurations.

One caveat is that when we are adding to the solution set, we do not add **cur** directly, because it is a reference to a board configuration that is used throughout the solving processes. It is subject to change while what we needed was the value at a specific point.

'''

```
def solveNQueens(self, n):
ret = []
self.dfs(n, 0, ['.'*n for i in range(n)], ret)
return ret
def dfs(self, n, index, cur, ret):
if index >= n:
ret.append(cur[::])
return
for i in range(n):
cur[i] = cur[i][:index]+'Q'+cur[i][index+1:]
if self.isValid(cur, i, index):
self.dfs(n, index+1, cur, ret)
cur[i] = cur[i][:index]+'.'+cur[i][index+1:]
def isValid(self, board, i, j):
for a in range(j):
if board[i][a] == 'Q':
return False
for b in range(1, min(i,j)+1):
if board[i-b][j-b] == 'Q':
return False
for c in range(1, min(j,len(board)-i-1)+1):
if board[i+c][j-c] == 'Q':
return False
return True
```

'''