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 ith queen. Now if (k-1) queens are already placed in first (k-1) rows and we need to place kth queen in kth row then we need to check its column and diagonals with all previously placed (k-1) queens.

If we find no place for kth queen in kth 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 kth queen. If we still have problem in placing kth 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 kth queen, we will go 2 step back and find alternate safe column for (k-2)th queen.

This process will be repeated till 1st 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 '
        s << '_ '
    puts s
  # exit #remove this exit if u want to see all solutions

# 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
  return true

# 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)
        puts ""
        nqueen(r+1, n)

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