PROGRAMMING INTERVIEWS

Question: N queen problem is a very famous problem in computer science. This problem ask user to place N chess queens on a NxN chessboard so that no two queens attack each other.

Answer: As the queen can move in any of the eight directions and any number of steps in a single move, there are few solutions, which fit the bill. For N=8, there are 92 distinct solutions. And if solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has only 12 solutions.

Lets assume that we already have some queens placed on the chess board so that no queen can attack each other. Now if we need to place another queen on the board, how will we go about it? Please note that a queen is safe if:

1. There is no queen in same row.
2. There is no queen in same column.
3. There is no queen in diagonal paths going from that queen.

Lets say that there are 2 queens at position (i, j) and (x, y). By above theory, that are NOT safe if:

• i = x               same row
• j = y               same row
• |i-x| = |j-y|   same diagonal paths

We can simply avoid the first constraint by placing each queen in different rows. So lets put 1st queen in 1st row, 2nd queen in 2nd row and so on. Now we need to check for same column and same diagonal. Lets have an array 'pos[]' of size N showing where pos[i] is column for i^th queen. Now if (k-1) queens are already placed in first (k-1) rows and we need to place k^th queen in k^th row then we need to check its column and diagonals with all previously placed (k-1) queens.

If we find no place for k^th queen in k^th row because of placement of earlier queens, we will go back to (k-1)^th queen and place it in a different column. Then we try again to place k^th queen. If we still have problem in placing k^th queen, we will go back to (k-1)^th queen and try another safe position for it. This process will be repeated till we try all the possible position for (k-1)^th queen. If there is no safe position to place (k-1) and k^th queen, we will go 2 step back and find alternate safe column for (k-2)^th queen.

This process will be repeated till 1^st queen until we don't find a solution. Since we are going back and finding alternate safe place, this kind of algorithmic approach is called backtracking. Below is an animated figure for the same. (source: Wikipedia)


Below is the ruby implementation for the same:

require 'pp'

@pos = []

def print(size)
  for i in 0..size
    s = ""
    for j in 0..size
      if @pos[i] == j
        s << 'Q '
      else
        s << '_ '
      end
    end
    puts s
  end
  # exit #remove this exit if u want to see all solutions
end

# check if putting a queen in (row, col) is safe
def is_safe(row, col)
  for i in 0..(row-1)
    if (col == @pos[i]) or ((row-i).abs == (col-@pos[i]).abs)
      return false
    end
  end
  return true
end

# place queen in row r
def nqueen(r, n)
  for i in 0..n
    if is_safe(r, i)
      @pos[r] = i
      if (r == n)
        print(n)
        puts ""
      else
        nqueen(r+1, n)
      end
    end
  end
end

if __FILE__ == $0
  if ARGV.length < 1
    puts "Usage: ruby #{$0} size"
    exit
  end
  size = ARGV[0].to_i-1
  if size < 3
    puts "No solution possible"
  else
    nqueen(0, size)
  end
end

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.