Saturday, June 26, 2010

The N Queens Problem in Ruby

The N Queens Problem was posed recently over at Programming Praxis. This is a pretty classic problem and typically uses a recursive solution. Here's what I came up with as a ruby solution.


# We present today a classic exercise that has been on my to-do list since the
# start of Programming Praxis.
#
# The n-queens problem is to find all possible ways to place n queens on an n ×
# n chess board in such a way that no two queens share a row, column, or
# diagonal. The diagram at right shows one way that can be done on a standard 8
# × 8 chess board.
#
# Your task is to write a program to find all such placements. When you are
# finished, you are welcome to read or run a suggested solution, or to post
# your own solution or discuss the exercise in the comments below.

class Board

# Create a new board, initialize with with all "b" and
# save the size of it.
def initialize(n)
@n = n
@board = Array.new(n)
@board.map! { Array.new(n, "b") }
end

# Print the current board.
def print_board
puts "Board:"
@board.each_index do |row|
@board.each_index do |col|
print "#{@board[row][col]}"
end
puts
end
end

# Check if the row is safe by looping through each of the
# columns in the row.
def safe_row(suggested_row)
0.upto(@n-1) do |col|
return false if @board[suggested_row][col] == "Q"
end

return true
end

# Check if the column is safe by looping through each of the
# rows in the row.
def safe_col(suggested_col)
0.upto(@n-1) do |row|
return false if @board[row][suggested_col] == "Q"
end

return true
end

# Loop through in one diagonal direction to determine if the
# suggested row and column are safe.
def safe_diag(suggested_row, suggested_col, row_mod, col_mod)
row,col = suggested_row+row_mod, suggested_col+col_mod
while true do

# Break out of the loop if the row or column is off the board.
break if (row >= @n) || (col >= @n) || (row < 0) || (col < 0)

# If this row or column has a queen, then it's not safe.
return false if @board[row][col] == "Q"

# Move in the appropriate direction.
row += row_mod
col += col_mod
end

# This direction is safe.
return true
end

def safe(suggested_row, suggested_col)

# Check the rows and columns for safe.
return false if !safe_row(suggested_row)
return false if !safe_col(suggested_col)

# Check the diagonals for safe.
return false if !safe_diag(suggested_row, suggested_col, 1, 1)
return false if !safe_diag(suggested_row, suggested_col, 1, -1)
return false if !safe_diag(suggested_row, suggested_col, -1, 1)
return false if !safe_diag(suggested_row, suggested_col, -1, -1)

# Should be OK.
return true
end

# Solve the n-queens problem by making a call to the recursive solve_1
# method with 0 (the first row of the board) to start.
def solve
solve_1(0)
end

# The recursive method (by row) that loops through the columns and checks
# if the row given and the column are "safe". If they are we add a "Q" to
# the position and if the row is 0, we print it out (everthing is
# complete). If it's safe adn we aren't at 0 we move to the next row
# recursively. Finally, we reset the position to "b" (blank) when we
# return from the recursive call or from printing the board. If it's not
# "safe" then we just move to the next column and try that one.
def solve_1(row)
0.upto(@n-1) do |col|
if safe(row, col)
@board[row][col] = "Q"
if row == (@n-1)
print_board
else
solve_1(row+1)
end
@board[row][col] = "b"
end
end
end
end


# Solve the problem for 8 queens. There should be 92
# solutions.
board = Board.new(8).solve


I've put quite a few comments in there, but if you have questions, don't hesitate to ask.

9 comments:

  1. Thanks for this code...though its been 3 years. Your comments are great and coding style is clean. Just a comment...I think there is a quicker way to check for a safe diagonal.

    ReplyDelete
  2. Taiwo, Glad you enjoyed this. What are your thoughts on the diagonal? I'd love to see what you've come up with.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Hey thanks for your response. I wasted some time testing out some random theory about n queens so I'm just responding. I had to turn in a n queens assignment and after doing some reading and seeing your code, I thought I could "optimize" it this way. Since the inherent constraint is that only 1 queen per column, then you dont need to check if a column is safe. I may be wrong, but the results up to 8 queens shows that it is fine. Also, the safe_diag method confused me and I decided to rewrite it. Overall, the code is a bit faster. Lastly, I think I will implement a method that keeps track of attacked squares...it might further "optimize" the code if the overhead of keeping track isnt significant.

    def safe_row?(suggested_col)
    0.upto(@n-1) do |row|
    return false if @board[row][suggested_col] == "Q"
    end
    return true
    end

    def safe_diag?(suggested_row, suggested_col)
    0.upto(@n-1) do |col|
    0.upto(suggested_row-1) do |row| #redundant to check the actual row...so -1
    return false if @board[row][col] == "Q" and (row - suggested_row).abs == (col - suggested_col).abs
    end
    end
    return true
    end

    ReplyDelete
    Replies
    1. Now I get your safe_diag...it is a more efficient way to check I think.

      Delete
  5. Nice job. Especially on noting that there's no need to check for a safe column. I haven't looked at this since I wrote it, so I'd have to dig a bit deeper on some of these things. Let me know if you do a time comparison on the two approaches.

    Thanks for writing!

    ReplyDelete
    Replies
    1. I ran a short time comparison with 8 queens on 3 approaches. First approach, I ran your code. Second approach, I ran my code and it ran about 20-25% faster than the first. Third approach, I combine what I thought were the best ideas from both. Basically, I kept your safe_diag and I removed the column check. It ran about 40-50% faster than the first. Your safe_diag method works better than mine because it only checks if the diagonals of a particular square (where you intend to place a new queen) can attack previous queen(s). The cool thing here is that the constraint is checked by the new queen. However, mine searches for all queen positions and checks if they have diagonals that can attack my new queen. The constraint is checked by every queen or at least until I find an attacking queen. Essentially, I waste time searching for queens and checking their diagonals, when I can just have the new queen check if it can attack a previous queen. I found another implementation by someone else that runs 90-95% (no kidding) faster than the first, but he used at least 4 times as much space. Well I think this ends my little research.

      Delete
    2. Well done. It certainly shows the usefulness of code reviews. It makes sense that the column code is unnecessary, but also slow base on the fact that typically arrays are fastest going through by columns (across the row and slower when looping through a single column). Was the version you found that was much faster non-recursive? That'd be the one thing I'd look at if I were going to really try for speed on this.

      Delete
  6. The version I found used recursion and 4 times as much space. That extra space most likely gave it the speed bump. You know I just found another way to optimize. The two lines below check for diagonals below a queen that is about to be placed, but it isnt needed because I believe there would never be a queen below a queen that is about to be place. My test with 8 queens gave another 40% speed bump from version 3 above.

    return false if !safe_diag(suggested_row, suggested_col, 1, 1)
    return false if !safe_diag(suggested_row, suggested_col, 1, -1)

    ReplyDelete