8 Queens in Ruby

I came across a puzzle article that mentioned the 8 Queens problem. It’s been a long time since I encountered it, but I can’t recall if I ever took the time to code it up, so I took a few minutes to code up a couple versions in Ruby. I was impressed with how easy it was in Ruby. If Ruby had the macros and efficiency of Lisp, I’d be pleased.

In a nutshell, the idea is to determine all possible ways to arrange 8 queens on a chessboard so that none are attacking another.

I’m sure my solution is naive since it was pretty much the first approach I thought of, but it cranks out all solutions in a quarter of a second, so it’ll do :)

require 'pp'

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank)
      queens(stack, n+1) if valid?(stack)
      stack.pop
    end
  end
end

queens [], 0

I then became curious about abstracting away the concept of:
1) push something onto a stack
2) do something with the stack
3) pop something off the stack

So, I opened up the Array class and modified push to accept a block.

require 'pp'

class Array
  alias_method :orig_push, :push
  def push obj
    orig_push(obj)
    if block_given?
      yield self
      pop
    end
  end
end

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank) {|s| queens(s, n+1) if valid?(s) }
    end
  end
end

queens [], 0

It makes the code 15% slower, and I don’t like modifying the existing push method in this way, but it does show the convenience of Ruby blocks and how you can extend existing classes. I think a better approach would be to introduce a new function – either standalone as below, or in the Array class.

def push_with_block stack, obj
  stack.push(obj)
  yield stack
  stack.pop
end