LC 0051 [H] N Queens - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=wGbuCyNpxIg

---

• it helps to think of this problem in terms of row = y and col = x
• backtracking DFS with 3 arrays: solutions[], diagonals[], anti-diagonals[]
• we are done with a solution when we have placed all the cols to the size of the board
• else we loop through the cols (x) and keep track of the ones we can place
• so we know what the row we are on (y) as the len of the solution so far
• we check vertical placements by simply checking they are not in a col (x) we have already placed
• we check diagonal placements by using y = mx + b, solving for diagonals: y = 1x + b => y - x = b and anti-diagonals: y = -1x + b => y + x = b, making sure the next y +- x = b does not fall on the same diagonal line
• then return the cols for each solution with some prefix-suffix parsing

---

https://www.youtube.com/watch?v=Ph95IHmRp5M&ab_channel=NeetCode

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set() # (r + c)
        negDiag = set() # (r + c)
        
        res = []
        board = [['.'] * n for i in range(n)]
        
        def dfs(r):
            if r == n:
                res.append( [''.join(row) for row in board] )
            else:
                for c in range(n):
                    if c in col or (r + c) in posDiag or (r - c) in negDiag:
                        continue
                        
                    # do
                    col.add(c)
                    posDiag.add(r + c)
                    negDiag.add(r - c)
                    board[r][c] = 'Q'
                    
                    dfs(r + 1)
                    
                    # undo (backtracking)
                    col.remove(c)
                    posDiag.remove(r + c)
                    negDiag.remove(r - c)
                    board[r][c] = '.'
                    
        dfs(0)
        
        return res

class Solution:
    def solveNQueens(self, n):
        n_rows = n_cols = n

        def dfs(placed_cols, yx_dif, yx_sum):
            if len(placed_cols) == n_cols:
                sols.append(placed_cols)
            else:
                for x in range(n_cols): # loop cols
                    y = len(placed_cols) # imply row
                    can_place_vert = x not in placed_cols
                    can_place_diag = y-x not in yx_dif and y+x not in yx_sum
                    if can_place_vert and can_place_diag: 
                        dfs(placed_cols + [x], yx_dif + [y-x], yx_sum + [y+x])  
        sols = []
        dfs([], [], [])
        
        def parseRow(x):
            prefix = '.' * x
            suffix = '.' * (n_cols - 1 - x)
            return f'{prefix}Q{suffix}'
        
        return [ [parseRow(x) for x in placed_cols] for placed_cols in sols]