**The problem**

- Input integer
**n** - Place
**n**queens on**n x n**board **Q**means queen at cell**.**Means empty space- Queen can move in any direction
- Horizontally
- Up
- Down
- Diagonal neg + pos

## The Trick, let's say for 4x4

**Understanding**- Notice that
**each and****every queen has to be in a different row!** - Notice that
**each and every queen has to be in a different column!** - Notice that
**each and every queen has to be in a different positive diagonal!** - Notice that
**each and every queen has to be in a different negative diagonal!** **State -**__Set__- is queen in column, posDiag (row-col), negDiag (row+col)- Which rows have queen - do not have to store in state we just loop the rows
- Which
**columns have queen - store in state**! - Which posDiag have queen - store in state!
- Which negDiag have queen - store in state!
**Trick****posDiag -> row - column = constant**- Every time we increase row we increase column
**negDiag -> row + column = constant**- Every time we increase row we decrease column
- Loop
- 1st queen 1st row
- Can put first queen in first column
- Can put first queen in second column
- Can put first queen in third column
- Can put first queen in 4th column

class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
cols = set() # Cannot put Q in this col.
diag1 = set() # Cannot put Q in this diagonal.
diag2 = set() # Cannot put Q in this diagonal.
# We do not need to store cannot put Q in row because we just loop to next row.
res = []
board = [['.'] * n for i in range(n)]
# For each row try putting a queen start with row 0
def backtrack(r):
# Do we have a solution?
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
# Try put Q in each col
for c in range(n):
if c in cols or (r + c) in diag1 or (r-c) in diag2:
# Cannot put Q in this col continue to next col.
continue
# Put Q in this col mark following rows cannot use this col, diag1, diag2
cols.add(c)
diag1.add(r+c)
diag2.add(r-c)
board[r][c] = 'Q'
# We have placed our Q continue to next row.
backtrack(r + 1)
# We get here in two flows
# 1. Finished backtrack(r+1) successfully we have a solution, now try the next column as a new solution.
# 2. Finished backtrack(r+1) unsuccessfully we don't have a solution try next column.
cols.remove(c)
diag1.remove(r+c)
diag2.remove(r-c)
board[r][c] = '.'
backtrack(0)
return res;

## Comments

## Post a Comment