###### 4 comments

Excelent article about the classic problem, good job! I’ve that review in details to remember this. Excelent again!

Thanks for your comment Daniel! ðŸ™‚

Excellent!!!

Thanks for reading ðŸ™‚

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.

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.

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

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:

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)

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.

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!

Daniel Moros says
4 years ago

Excelent article about the classic problem, good job! I’ve that review in details to remember this. Excelent again!

Jesus Castello says
4 years ago

Thanks for your comment Daniel! ðŸ™‚

Kiri says
4 years ago

Excellent!!!

Jesus Castello says
4 years ago

Thanks for reading ðŸ™‚