### Leave a Comment:

###### 4 comments

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

ReplyN-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!

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

Reply