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 the number of distinct solutions to the n-queens puzzle.

Example:


Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Difficulty: interview

Starter code:

class Solution:
    def totalNQueens(self, n: int) -> int:
        

Solutions:
class Solution:
     def totalNQueens(self, n):
         def dfs(lst, xy_dif, xy_sum):
             p=len(lst)
             if p==n: res.append(lst)
             for q in range(n):
                 if (q not in lst) and (p-q not in xy_dif) and (p+q not in xy_sum):
                     dfs(lst+[q], xy_dif+[p-q], xy_sum +[p+q])
             
         res=[]
         dfs([],[],[])
         return len(res)

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         result=[]
         self.DFS(n,0,"",[],[],[],result)
         print(result)
         return len(result) 
             
     def DFS(self, n, row, sss, check_col,check_diag1,check_diag2, result):
         """ sss is solution string, all other checks are checks for occupied places """
         if (len(sss) == n):
             result.append('.')
             return
         
         for col in range(0,n):
             if (col in check_col): continue
             if (row+col in check_diag1): continue
             if (row-col in check_diag2): continue
             self.DFS(n, row+1, sss+str(col), check_col+[col], 
                  check_diag1+[row+col], check_diag2+[row-col],result)

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         placement = []
         
         def can_place_queen(row, col):
             for i, j in enumerate(placement):
                 if col == j or abs(col - j) == row - i:
                     # Same column as, or diagonally from other queen
                     return False
             return True
 
         def place_in_row(row):
             if row == n:
                 return 1
             
             count = 0
             for col in range(n):
                 if can_place_queen(row, col):
                     placement.append(col)
                     count += place_in_row(row + 1)
                     placement.pop()
             return count
         return place_in_row(0)


class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         rl=[0]
         col=[False for x in range(n)]
         dia1=[False for x in range(2*n-1)]
         dia2=[False for x in range(2*n-1)]
         self.putQueen(n,col,dia1,dia2,rl,0)
         return rl[0]
     
     def putQueen(self,n,col,dia1,dia2,rl,index):
         if index==n:
             rl[0]+=1
             return True
         for i in range(n):
             if not col[i] and not dia1[index+i] and not dia2[index-i+n-1]:
                 col[i]=True
                 dia1[index+i]=True
                 dia2[index-i+n-1]=True
                 self.putQueen(n,col,dia1,dia2,rl,index+1)
                 col[i]=False
                 dia1[index+i]=False
                 dia2[index-i+n-1]=False

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 0:
             return 0
         diag_lr = [True] * (2*n-1)
         diag_rl = [True] * (2*n-1)
         vert = [True] * n
         res = []
 
         def _check_board(x, y):
             return vert[y] and diag_lr[y-x+n-1] and diag_rl[x+y]
 
         def _helper(x):
             if x == n:
                 res.append(1)
                 return
             for y in range(n):
                 if _check_board(x, y):
                     vert[y] = False
                     diag_lr[y-x+n-1] = False
                     diag_rl[x+y] = False
                     _helper(x+1)
                     vert[y] = True
                     diag_lr[y-x+n-1] = True
                     diag_rl[x+y] = True
 
         _helper(0)
         return len(res)

class Solution:
     def __init__(self):
         self.board = []
         self.col_status = []
         self.row_status = []
         self.dia_status_1 = []
         self.dia_status_2 = []
         self.result = 0
 
     def placeQueen(self, row, n):
         if row == n:
             tmp = [''.join(el) for el in self.board]
             self.result += 1
             return
         for i in range(n):
             if self.col_status[i] and self.dia_status_1[i+row] and self.dia_status_2[row-i]:
                 self.board[row][i] = 'Q'
                 self.col_status[i] = False
                 self.dia_status_1[i+row] = False
                 self.dia_status_2[row-i] = False
                 self.placeQueen(row+1, n)
                 self.board[row][i] = '.'
                 self.col_status[i] = True
                 self.dia_status_1[i+row] = True
                 self.dia_status_2[row-i] = True
 
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: List[List[str]]
         """
         self.board = [['.' for i in range(n)] for j in range(n)]
         self.col_status = [True for i in range(n)]
         self.row_status = [True for i in range(n)]
         self.dia_status_1 = [True for i in range(2*n-1)]
         self.dia_status_2 = [True for i in range(2*n-1)]
         self.placeQueen(0, n)
         return self.result

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         ans = []
         def dfs(queens, xy_dif, xy_sum):
             p = len(queens)
             if p == n:
                 result.append(queens)
                 return None
 
             for q in range(n):
                 if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
                     dfs(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
 
         result = []
         dfs([], [], [])
         
         return len(result)

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         def dfs(cols, diag_45, diag_135, depth=0):
             nonlocal result
             row = len(cols)
             if row == n:
                 result += 1
                 return 
             for col in range(n):
                 if col not in cols and (row - col) not in diag_45 and (row + col) not in diag_135:
                     dfs(cols + [col], diag_45 + [row - col], diag_135 + [row + col], depth + 1)
 
         result = 0
         dfs([], [], [])
         return result

class Solution:
     
     def find_arrangements(self, arrangement, diag1_used, diag2_used, col_used, x, n):
         if x == n:
             return 1
         res = 0
         for y in range(n):
             diag1 = x + y
             diag2 = x - y + n
             if not diag1_used[diag1] and not diag2_used[diag2] and not col_used[y]:
                 arrangement.append(y)
                 diag1_used[diag1] = True
                 diag2_used[diag2] = True
                 col_used[y] = True
                 cur_res = self.find_arrangements(arrangement, diag1_used, diag2_used, col_used, x + 1, n)
                 arrangement.pop()
                 diag1_used[diag1] = False
                 diag2_used[diag2] = False
                 col_used[y] = False
                 res += cur_res
                 
         return res
         
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         arrangement = []
         diag1_used = [False] * (2 * n)
         diag2_used = [False] * (2 * n)
         col_used = [False] * n
         return self.find_arrangements(arrangement, diag1_used, diag2_used, col_used, 0, n)

class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         
         count = 0
         def solve(rows, cols, diag0, diag1, n):
             nonlocal count
             
             freerows = {i for i in range(n)} - rows
             if not freerows:
                 count += 1
                 return
             
             i = freerows.pop()
             candidates = []
             for j in range(n):
                 if j in cols:
                     continue
                 if i + j in diag0:
                     continue
                 if i - j in diag1:
                     continue
                 
                 rows.add(i)
                 cols.add(j)
                 diag0.add(i+j)
                 diag1.add(i-j)
                 
                 solve(rows, cols, diag0, diag1, n)
                 
                 rows.remove(i)
                 cols.remove(j)
                 diag0.remove(i+j)
                 diag1.remove(i-j)
         
         solve(set(), set(), set(), set(), n)
         return count


class Solution:
     def totalNQueens(self, n):
         """
         :type n: int
         :rtype: int
         """
         row = [x for x in range(n)]
         table = []
         for i in range(n):
             table.append(row.copy())
         result = self.solve(table,0)
         return len(result)
     def solve(self,table,n):
         if table[n]==[]:return []
         elif n==len(table)-1:
             table[n] = table[n][0]
             return [table]
         else:
             result=[]
             for x in table[n]:
                 table1 = [(x if type(x)==int else x.copy()) for x in table]
                 table1[n] = x
                 for row in range(n+1,len(table)):
                     if x in table1[row]:
                         table1[row].remove(x)
                     if x+row-n in table1[row]:
                         table1[row].remove(x+row-n)
                     if x-(row-n) in table1[row]:
                         table1[row].remove(x-(row-n))
                 result.extend(self.solve(table1,n+1))
             return result