Solving the N-Queens Problem With Ruby

N-Queens is an interesting coding challenge where you have to place N queens on a N * N board.

It looks like this:

A queen can move in all directions:

• Vertical
• Horizontal
• Diagonal

The solution (there can be many) must place all the queens on the board & every queen must be out of reach of every other queen.

In this article you’re going to learn how I came up with the solution.

The Plan

When solving these kind of challenges a good place to start is to write down a plan in plain English.

This helps you get clear on what the problem is & the steps to solve it.

If you’re having trouble writing your plan make sure you understand the problem 100%.

My plan for the N-Queens solution:

• Start @ position 0,0
• if valid position: put queen, advance column (+ 1), set row to 0
  • check top, bottom, left, right, diagonal
• else: advance 1 square
  • go up (row + 1) unless current position == n
  • backtrack when queen can’t be placed in current column
    • remove last queen
    • set row & column to last queens’ position with row + 1

This is a cleaner version of what I initially wrote down.

I drill down on the steps that require more details before I can implement them.

Now:

Your plan won’t be perfect (mine wasn’t) but it will give you an idea of what to work towards.

If you can’t write a solid plan there is nothing wrong with looking up the solution…

…understand how the solution works then write your own.

Finding Valid Moves

To check if a position is valid we have to look in several directions.

Instead of messing around with a 2D board, I decided to have an array of queens in the board with their positions.

Then we check this array of queens against the position we want to validate.

For example, for the row check:

def queen_in_row(row)
  @queens_in_board.find { |r, c| r == row }
end

This will return a queen if the row is taken or nil if not.

You don’t have to check if the column is free because we move to the next column after placing a queen.

For the diagonals it takes some extra work since there are 4 of them.

Here’s the code for the right upper diagonal:

def right_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end

  diagonals
end

The other diagonals are the same, the only differece is in the conditions of the loop & the direction (row + 1 / row - 1).

This took a little bit of trial & error to get right, but that's ok.

It's important to test these methods in isolation to make sure they work. When you have a set of working methods you can put them together to form your complete solution.

Here's the method that pulls together all the diagonals & checks against every queen in the board:

def queen_in_diagonal(row, column, n)
  diagonals =
    right_upper_diagonal_for(row, column, n) +
    left_upper_diagonal_for(row, column, n) +
    left_lower_diagonal_for(row, column, n) +
    right_lower_diagonal_for(row, column, n)


  diagonals.any? { |r, c| r == row && c == column } ||
  diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end

How to Implement BackTracking

Solving these non-trivial challenges require you to know a key insight, technique or algorithm.

In the case of N-Queens the technique is backtracking.

Backtracking is undoing some previous action (like placing a queen on the board) & trying again with a different configuration.

I thought this would be the hardest part, but it turned out to be pretty easy.

To figure this out I ran a little simulation.

I drew myself a board & some boxes represting the queens:

Then I just moved the boxes around the board (directly with my mouse) to simulate the algorithm.

Here's the code:

while row >= n
  row    = @queens_in_board[-1][0] + 1
  column = @queens_in_board[-1][1]

  puts "Backtracking, deleted: #{@queens_in_board.pop}"
end

You can also do this for other problems when you get stuck, draw it on some drawing program or even on paper & play around with it.

Here's the essence of how this works:

• We keep going up, if we reach the top of the board it means we couldn't fit a queen on this column
• We backtrack by setting the current position to the last queen & removing it from the board
• If we can't place a queen from this position we backtrack again

The + 1 on the row position is how we advance the last queen to reposition it & open up new board configurations.

When running this code for n = 4 (there are no solutions for n = 2 & n = 3):

"placing at 0 0"
"placing at 2 1"
Backtracking, deleted: [2, 1]
"placing at 3 1"
"placing at 1 2"
Backtracking, deleted: [1, 2]
Backtracking, deleted: [3, 1]
Backtracking, deleted: [0, 0]
"placing at 1 0"
"placing at 3 1"
"placing at 0 2"
"placing at 2 3"

This gif is a visual example of the algorithm:

Full Code

def solve_n_queens(n)
  @queens_in_board = []

  row = 0
  column = 0

  until @queens_in_board.size == n
    if queen_in_row(row) || queen_in_diagonal(row, column, n)
      row += 1

      while row >= n
        row    = @queens_in_board[-1][0] + 1
        column = @queens_in_board[-1][1]

        puts "Backtracking, deleted: #{@queens_in_board.pop}"
      end
    else
      place_queen(row, column)

      p "placing at #{row} #{column}"

      row = 0
      column += 1
    end
  end

  @queens_in_board
end

def queen_in_row(row)
  @queens_in_board.find { |r, c| r == row }
end

def queen_in_diagonal(row, column, n)
  diagonals =
    right_upper_diagonal_for(row, column, n) +
    left_upper_diagonal_for(row, column, n) +
    left_lower_diagonal_for(row, column, n) +
    right_lower_diagonal_for(row, column, n)


  diagonals.any? { |r, c| r == row && c == column } ||
  diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end

def top_row?(row, n)
  row == n
end

def place_queen(row, column)
  @queens_in_board << [row, column]
end

def right_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end

  diagonals
end

def left_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == 0
    diagonals << [row += 1, column -= 1]
  end

  diagonals
end

def right_lower_diagonal_for(row, column, n)
  diagonals = []

  until row == 0 || column == n
    diagonals << [row -= 1, column += 1]
  end

  diagonals
end

def left_lower_diagonal_for(row, column, n)
  diagonals = []

  until row == 0 || column == 0
    diagonals << [row -= 1, column -= 1]
  end

  diagonals
end

def print_board(n)
  board = Array.new(n) { Array.new(n) { "." } }

  @queens_in_board.each { |queen| board[queen[0]][queen[1]] = "Q" }

  board.map { |n| n.join("|") }.reverse
end

p solve_n_queens(4)
p solve_n_queens(5)

puts print_board(5)

Recursive Version

This is an alternative version that finds ALL the possible solutions.

def solve_n_queens(n, column = 0, queens_in_board = [])
  @queens_in_board = queens_in_board

  n.times do |row|
    unless queen_in_row(row) || queen_in_diagonal(row, column, n)
      place_queen(row, column)

      solve_n_queens(n, column + 1, @queens_in_board)

      remove_last_queen
    end
  end

  puts print_board(n) if @queens_in_board.size == n
end

The only thing that changes is the solve_n_queens method.

This version uses recursion (a method that calls itself) to explore all partial solutions.

When a complete solution is found we print it using the print_board method.

Summary

You have learned about the N-Queens coding challenge & how to solve it in Ruby. You have also learned how to improve your problem-solving skills.

If you liked this article please share it with anyone that can benefit from it.

Thanks for reading!