# 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.

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.

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

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHey 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.

ReplyDeletedef 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

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

DeleteNice 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.

ReplyDeleteThanks for writing!

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.

DeleteWell 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.

DeleteThe 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.

ReplyDeletereturn false if !safe_diag(suggested_row, suggested_col, 1, 1)

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