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.

Simple Webrick Server and shjs Syntax Highlighting

Since I've upgraded my machine, maruku hasn't been able to do syntax highlighting for me. I'm now giving shjs a shot. Here's a simple webserver using webrick.

# Get webrick
require 'webrick'
include WEBrick

# Create the server.
server = HTTPServer.new(:Port => 9090, :DocumentRoot => Dir::pwd)

# Shutdown if we get an interrupt.
trap("INT") { server.shutdown }

# Start the server
server.start

Not to much going on here. We get webrick included and create the server. The port here is 9090 (obviously you can pick any one that you want). The HTML files will be served from the current directory and this can be modified also. Then we shut down the server when we see a ^C and finally, we start the server.

I actually lifted this from somewhere and forgot to grab the link to give credit. If it's yours or you know who's it is, let me know so I can acknowledge them.

Let me know if you have questions.