Get all valid ways of putting N Queens on an N * N chessboard so that no two Queens threaten each other.
Assumptions
N > 0
Return
A list of ways of putting the N Queens
Each way is represented by a list of the Queen's y index for x indices of 0 to (N - 1)
Example
N = 4, there are two ways of putting 4 queens:
[1, 3, 0, 2] --> the Queen on the first row is at y index 1, the Queen on the second row is at y index 3, the Queen on the third row is at y index 0 and the Queen on the fourth row is at y index 2.
[2, 0, 3, 1] --> the Queen on the first row is at y index 2, the Queen on the second row is at y index 0, the Queen on the third row is at y index 3 and the Queen on the fourth row is at y index 1.
class Solution(object):
def nqueens(self, n):
res = []
self.dfs(n,0,[],res)
return res
def dfs(self,n,i,state.res):
if i == n:
res.append(state[:])
return
for pos in xrange(n):
if self.isValid(state,pos):
state.append(pos)
self.dfs(n,i+1,state,res)
state.pop()
return
def isValid(self,state,pos):
for i in xrange(len(state)):
if abs(state[i] - pos) in (0,len(state) - i):
return False
return True
