Christian.

Backtracking

March 05, 2021

Leetcode problems about Backtracking.

51. N-Queens

I: N = 4
O: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

  • We check our base case if no grid exists
def solveNQueens(self, n: int) -> List[List[str]]:
  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 [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
Big OWhy
TimeO(n x m)Double for loop over our (n x m) matrix
SpaceO(n x m)We must traverse an entire (n x m) matrix

Written by Christian Turner
Follow me on Twitter