ruby-csp

Ruby-csp is a library for modeling and solving constraint satisfaction problems (CSPs). It is implemented in pure Ruby and aims to provide a clean, "ruby like" API. This is just the first release (I am calling it version 0.0.1), so there is lots to do, but it is already usable.

The library is written and maintained by Jonathan Sillito. Please report bugs, make suggestions or otherwise get involved by email to [sillito at gmail.com].

Download and Installation Instructions

Download one of the following:

ruby-csp-0.0.1.tgz
ruby-csp-0.0.1.zip

Unpack the downloaded file which contains the directory ruby-csp. Follow the instructions in ruby-csp/README.txt.

Using the Library

Full library documentation is available in the distribution in the directory ruby-csp/doc/. It is also available online here. The distribution also contains tests in ruby-csp/tests and several examples in ruby-csp/examples (N-Queens, Golomb Ruler and Magic Squares). Here is how the N-Queens example looks:

Models and solves the N-Queens problem as a CSP.

require 'ai/csp'
include AI::CSP

def problem(n)

    # variables are columns and values are rows, so assigning 
    # the first variable the value 2 corresponds to placing a 
    # queen on the board at col 0 and row 2.

    variables = (0...n).collect {|i| 
        <b>Variable.new(i, (0...n))</b>
    }
    problem = Problem.new(variables)

    # None of the queens can share a row. AllDifferent is a 
    # built in constraint type.
    <b>problem.add_constraint(AllDifferent.new(*variables))</b>

    # No pair of queens can be on the same diagonal. 
    variables.each_with_index {|v1,i|
        variables[(i+1)..-1].each_with_index{ |v2,j|
            <b>problem.add_constraint(v1, v2) { |row1,row2|
                (j+1) != (row1-row2).abs
            }</b>
        }
    }

    problem
end

solver = Backtracking.new(true, FAIL_FIRST)
solver.each_solution(problem(8)) { |solution|
    puts solution 
}

puts solver # prints some statistics