# Solution to the n-queens puzzle in Ruby

I started studying programming in January of this year and found a free online course that teaches Ruby. Below is my solution to the Eight Queens problem.

I wanted my solution to be able to return any valid n-queens puzzle solution in a non-specific order.

I'm looking for feedback such as:

1. On the continuum of good or bad, where do you think my code lies?
2. What are one or two things I should be working on or focusing on becoming more familiar with?
require 'set'

class EightQueens

attr_accessor :grid

def initialize(n)
@grid = Array.new(n) { Array.new(n, '_') }
@invalid_pos = Set.new
@queen_pos = Set.new
end

def solve

until @queen_pos.size == self.size + 1

random_pos = self.pick_random_pos
row = random_pos
col = random_pos
if @grid[row][col] != 'Q' && open_move?(random_pos, self.size )
self.place_queen(random_pos)
@queen_pos << random_pos
elsif @grid[row][col] == 'Q' || !open_move?(random_pos, self.size)
@invalid_pos << random_pos
end

if @invalid_pos.length == self.full_grid_count - @grid.length
self.reset_grid
@invalid_pos.clear
@queen_pos.clear
end
end
puts 'Eight Queens puzzle solved, observe board.'
self.print
return true
end

def size
@grid.length - 1
end

def full_grid_count
count = 0
@grid.each { |row| count += row.count }
count
end

def reset_grid
@grid.map! do |row|
row.map! do |el|
el = '_'
end
end
end

def pick_random_pos
idx1 = rand(0...@grid.length)
idx2 = rand(0...@grid.length)

[ idx1, idx2 ]
end

def print
@grid.each do |row|
puts row.join(' ')
end
end

def open_move?(position, grid_size)
row = position
col = position

return false if queen_in_col?(col) || queen_in_row?(row) || queen_in_diagonal?(position, grid_size)
true
end

def []=(pos, val)
row, col = pos
@grid[row][col] = val
@diag_check_start_points = { 0=>[0,0]}
end

def place_queen(pos)
row, col = pos
@grid[row][col] = 'Q'
end

def is_queen?(pos)
row, col = pos
@grid[row][col] == 'Q'
end

def queen_in_row?(row)
@grid[row].any? { |pos| pos == 'Q' }
end

def queen_in_col?(col)
transposed = @grid.transpose
transposed[col].any? { |pos| pos == 'Q' }
end

def queen_in_diagonal?(position, n)
all_diagonals = (right_lower_diagonal(position, n) +
right_upper_diagonal(position, n) +
left_lower_diagonal(position, n) +
left_upper_diagonal(position, n))

all_diagonals.any? { |pos| is_queen?(pos) }
end

def right_lower_diagonal(position, n)
row = position
col = position
diagonals = []

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

diagonals
end

def right_upper_diagonal(position, n)
row = position
col = position
diagonals = []

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

diagonals
end

def left_upper_diagonal(position, n)
row = position
col = position
diagonals = []

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

diagonals
end

def left_lower_diagonal(position, n)
row = position
col = position
diagonals = []

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

diagonals
end

end


On the continuum of good or bad, where do you think my code lies?

The Eight Queens puzzle is already some advanced programming and if we consider that you just started programming ~6 months ago it is great that you came up with a working solution.

I think it is a clever approach to store the valid and invalid position in a set which is an efficient way for look up.

However, there is of course room for some improvements.

What are one or two things I should be working on or focusing on becoming more familiar with?

I think you should focus on object oriented design as you basically just have one class which does everything and is quite hard to understand and change.

So good candidates to extract into classes are methods with the same parameters and / or body. If we look at your code, all the _diagonal methods are good candidates.

# Diagonal

class Diagonal
def initialize(position, size, delta)
@row, @column = position
@row_delta, @column_delta = delta
@size = size
end

def all
[].tap do |result|
result << update_position until border_reached?
end
end

def self.for(position, size)
Diagonal.new(position, size, [-1, -1]).all +
Diagonal.new(position, size, [1, 1]).all +
Diagonal.new(position, size, [-1, 1]).all +
Diagonal.new(position, size, [1, -1]).all
end

private

attr_reader :row, :column, :row_delta, :column_delta, :size

def update_position
[
update_row,
update_column
]
end

def update_row
@row += row_delta
end

def update_column
@column += column_delta
end

def border_reached?
row.zero? ||
column.zero? ||
row == size ||
column == size
end
end


So we now DRYed this up a little bit and reuse the Diagonal class and just pass in the different deltas depending if it's upper right/left or lower right/left. Note that the abort function border_reached? is basically the same for all diagonals too.

We can use this class now with Diagonal.for([1,1], 8).any? to get all diagonals for position 1,1 in a 8 sized grid.

# GridPrinter

We could also extract the grid printing like this

class ConsolePrinter
def initialize(grid)
@grid = grid
end

def print
grid.each do |row|
puts row.join(' ')
end
end

private

end


You might wonder why we want to extract only 3 lines of code but it makes the code a lot more extensible. For instance, if we want to reuse your code on a website, we can implement a HtmlPrinter which just prints the grid as HTML code.

## Move

We can now also extract a Move or ValidMove class. Something like this

class Move
def initialize(position, grid)
@row, @column = position
@grid = grid
end

def valid?
!invalid?
end

def invalid?
queen_in_col? || queen_in_row? || queen_in_diagonal?
end

private

attr_reader :row, :column, :grid

def size
grid.length - 1
end

def queen_in_row?
grid[row].any? { |pos| pos == 'Q' }
end

def queen_in_col?
transposed = grid.transpose
transposed[column].any? { |pos| pos == 'Q' }
end

def queen_in_diagonal?
Diagonal.for([row, column], size).any? { |pos| queen?(pos) }
end

def queen?(pos)
row, col = pos
grid[row][col] == 'Q'
end
end


# Grid

And finally a Grid class.

class Grid
def initialize(n, printer = GridPrinter)
@printer = printer
@store = Array.new(n) { Array.new(n, '_') }
end

def place_queen(row, column)
return false if store[row][column] == 'Q' || Move.new([row, column], store).invalid?

store[row][column] = 'Q'
true
end

def length
store.length
end

def full_grid_count
store.flatten.count
end

def print
printer.new(store).print
end

private

end


Notice that we moved the place_queen method in the Grid class and also moved the 'validation' there. This is called tell, don't ask and instead checking if the move is valid and then placing the queen we now just say, place the queen and let us know if it worked. This simplifies our code in the EightQueens class.

class EightQueens
def initialize(n)
@grid = Grid.new(n)
@invalid_pos = Set.new
@queen_pos = Set.new
end

def solve
until queen_pos.size == grid.length
place_queen
reset
end

puts 'Eight Queens puzzle solved, observe board.'
grid.print

true
end

private

attr_reader :invalid_pos, :queen_pos, :grid

def place_queen
random_pos = pick_random_pos

if grid.place_queen(*pick_random_pos)
queen_pos << random_pos
else
invalid_pos << random_pos
end
end

def pick_random_pos
idx1 = rand(0...grid.length)
idx2 = rand(0...grid.length)

[idx1, idx2]
end

def reset
return unless invalid_pos.length == grid.full_grid_count - grid.length

@grid = Grid.new(grid.length)
@invalid_pos = Set.new
@queen_pos = Set.new
end
end


# Corner cases

It's not working for grids smaller 3 and just ends up in a infinite loop. You might want to have a look at these cases when no solution exists.

This is mostly focused on object oriented design (and by no means a perfect solution either). There might be ways to make this more efficient too but often readable and maintainable code if preferred over efficiency.

Some books about object oriented design in Ruby I can highly recommend are

## Edit:

In your solution you also use some sort of brute forcing (pick a random queen position until you have a valid solution, if no valid solution is possible reset grid). This is a simple solution! However, try to solve a 32 grid and it will take 'forever'. With your updated solution you can now easily implement new algorithms to solve the problem as you can reuse Grid and Move and we just need to implement a new EightQueens class (and maybe rename the old one to e.g. RandomEighQueensSolver. A better algorithm you might want to try to implement is called backtracking (https://en.wikipedia.org/wiki/Backtracking).

## Edit2:

As discussed in the comments, my assumption to merge the abortion condition in diagonal together does not work.

class Diagonal
def initialize(position:, delta:, to:)
@row, @column = position
@row_delta, @column_delta = delta
@to_row, @to_column = to
end

def all
[].tap do |result|
result << update_position until border_reached?
end
end

def self.for(position, size)
Diagonal.new(position: position, delta: [-1, -1], to: [0, 0]).all +
Diagonal.new(position: position, delta: [1, 1], to: [size, size]).all +
Diagonal.new(position: position, delta: [-1, 1], to: [0, size]).all +
Diagonal.new(position: position, delta: [1, -1], to: [size, 0]).all
end

private

attr_reader :row, :column, :row_delta, :column_delta, :to_row, :to_column

def update_position
[
update_row,
update_column
]
end

def update_row
@row += row_delta
end

def update_column
@column += column_delta
end

def border_reached?
row == to_row ||
column == to_column
end
end


See also a working example here https://github.com/ChrisBr/queen-puzzle.

• This is excellent, thank you. I do have one question, in the 'reset' function, would there be any concern about creating new grids and sets in terms of memory? Is my impression that clearing the originally initialized grid and vald/invalid sets saves space in memory, or is this maybe too little of a concern? Or is it just another way to solve the problem? Thanks again, really enjoying Ruby I'll be studying this answer over the next day or two. Jun 30, 2020 at 23:35
• Creating new objects should not be a memory concern as you don't hold the reference anymore and eventually Ruby's garbage collection will remove the objects. If you would create millions of objects it might make sense to reuse them, most of the team it's more clear to just create new objects though. Jul 1, 2020 at 7:29
• Please note my edit regarding trying out different algorithms too. Jul 1, 2020 at 7:51
• Okay, that's an interesting feature of Ruby, thanks for the clarification. I will definitely circle back around to understand and implement the 'backtracking' method. Interestingly according to wiki the highest n-queen board size that has been fully enumerated is 27x27. I was actually surprised by my method, it was still giving me answers within 30 seconds or so up until 17x17 or 18x18, I was wondering if I had a stronger computer might the method not be able to make it all the way up to 27x27 in a reasonable amount of time, but I'm interested to see how backtracking does... Jul 1, 2020 at 23:26
• So I had another look and turns out my assumption to merge the breaking condition for the diagonals was wrong. I implemented some specs and a fixed solution here github.com/ChrisBr/queen-puzzle. The code is in the lib directory, specs are in specs. Feel free to add some more specs (e.g. for rows, columns and if the position is already occupied) and send me a PR if you fancy. Jul 10, 2020 at 7:24