4
\$\begingroup\$

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_reader :invalid_pos, :queen_pos
    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[0]
            col = random_pos[1]
            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[0]
        col = position[1]

        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[0]
        col = position[1]
        diagonals = []

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

        diagonals
    end

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

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

        diagonals
    end

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

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

        diagonals
    end

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

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

        diagonals
    end

end
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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

  attr_reader :grid
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

  attr_reader :store, :printer
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.

\$\endgroup\$
10
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 30, 2020 at 23:35
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 1, 2020 at 7:29
  • \$\begingroup\$ Please note my edit regarding trying out different algorithms too. \$\endgroup\$ Jul 1, 2020 at 7:51
  • \$\begingroup\$ 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... \$\endgroup\$ Jul 1, 2020 at 23:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jul 10, 2020 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.