Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: Place N Queens on an NxN Chessboard

Solution Review: Place N Queens on an NxN Chessboard

In this lesson, we will go over the solution to the challenge from the previous lesson.

We'll cover the following...

Solution #

Press + to interact
def isSafe(i, j, board):
  for c in range(len(board)):
    for r in range(len(board)):
      # check if i,j share row with any queen
      if board[c][r] == 'q' and i==c and j!=r: 
        return False
      # check if i,j share column with any queen
      elif board[c][r] == 'q' and j==r and i!=c:
        return False
      # check if i,j share diagonal with any queen
      elif (i+j == c+r or i-j == c-r) and board[c][r] == 'q':
        return False
  return True 
def nQueens(r, n, board):
  # base case, when queens have been placed in all rows return
  if r == n:
    return True, board
  # else in r-th row, check for every box whether it is suitable to place queen
  for i in range(n):
    if isSafe(r, i, board):
      # if i-th columns is safe to place queen, place the queen there and check recursively for other rows
      board[r][i] = 'q'
      okay, newboard = nQueens(r+1, n, board)
      # if all next queens were placed correctly, recursive call should return true, and we should return true here too
      if okay:
        return True, newboard
      # else this is not a suitable box to place queen, and we should check for next box
      board[r][i] = '-'
  return False, board
def placeNQueens(n, board):
  
  return nQueens(0, n, board)[1]
def main():
  n = 4
  board = [["-" for _ in range(n)] for _ in range(n)]
  qBoard = placeNQueens(n, board)
  qBoard =  "\n".join(["".join(x) for x in qBoard])
  print (qBoard)
main()

Explanation

Let’s break down what we did there. The basic idea is to place the queen at all possible positions to find out what fits our needs. We start off placing a queen in the first row’s first box and then make a recursive call to place a queen in the second row. Here we place a queen in a safe position and check recursively again for the next rows. If any of the recursive calls return false, we check the next box on the previous row, and so on.

Look at the visualization of a dry run on an example where n = 4.

Observe how simple and intuitive this solution is. All we are doing is placing queens in a row and checking whether, after placing that queen, we can place queens in proceeding rows. Now if you look at the code, start with line 20, where we iterate over the rth^{th} ...