Solving the N-Queens Problem in Python

The N-Queens problem is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. This means that no two queens should share the same row, column, or diagonal. Below is a solution on an 8x8 chessboard.

Image credits: Wikimedia commons

The most common solution to this problem uses backtracking. Basically, we try to place a queen on the board, if no placement is appropriate, we shift the previous queen to the right. If the placement was successful, we try to place the next queen.

You can also view the visualization on algorithm-visualizer.org

Solution

Creating the board

The first obvious task is to create the board given N. Let's do that in a main function.

def main(n=4):
  board = [["-" for _ in range(n)] for _ in range(n)]
  boardToPrint =  "\n".join(["".join(x) for x in board])
  print (boardToPrint)

main()

Running the main function prints this matrix

----
----
----
----

Is safe to place a queen

Before we start placing any queen, we need to know that a cell is safe. Each cell we encounter has an x and y coordinate.

def isSafe(x, y, board):
  for column in range(len(board)):
    for row in range(len(board)):
      # check if x,y share row with any queen
      if board[column][row] == 'q' and x==column and y != row: 
        return False
      # check if x,y share column with any queen
      elif board[column][row] == 'q' and y==row and x!=column:
        return False
      # check if i,j share diagonal with any queen
      elif (x+y == column+row or x-y == column-row) and board[column][row] == 'q':
        return False
  return True

Recurive function

We will use the nQueens function to place a single

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