CSP Solver

A Ruby library for solving constraint satisfaction problems (CSPs).

This program does not have any sort of user interface (yet). It is strictly a Ruby library that can be used to model and solve any type of constraint satisfaction problem. I have tried to make the API simple and intuitive. If you have any suggestions, please open an issue on the GitHub repository.

API

CSP

In file: lib/csp.rb

new()

Create a new CSP instance.

csp = CSP.new

var(id, domain)

Create a new variable in the CSP identified by id and with the initial domain domain. Domain must have a to_a method.

Variables are specified here as symbols, but may be anything equatable.

csp.var :x, 1..10
csp.var(:x, 1..10)

vars(ids, domain)

Create variables in the CSP identified by id that all share the same domain domain. The given domain array will be shallow-copied to all created variables.

csp.vars :x..:z, 1..10
csp.vars([:x, :y, :z], 1..10)

assign(hash)

Assigns values to the variables identified by the hash keys (creating them if necessary) by setting their domain to be a singleton list containing only the hash value.

csp.assign x: 5, y: 3, z: 6
csp.assign({ :x => 5, :y => 3, :z => 6 })

constrain(*vars, &predicate)

Add a constraint involving the given variables as specified by the predicate. The predicate arguments will have a one-to-one mapping with the vars arguments to the constrain method, and the predicate must evaluate to a boolean.

Constraints may be of any arity. If only one variable is specified, then the constraint will be evaluated as a unary filter on the domain of the variable at solve-time. If two variables are specified, a corresponding two-way binary relationship will be added with the given predicate. If more than two variables are specified, an auxiliary variable will be generated with a domain filtered according to the given predicate, and binary constraints will be created to link this auxiliary variable to the variables it represents.

If more than one constraint is specified for a given set of variables, the solver will ensure that all of them are satisfied. That is, multiple constraints will be AND-ed together.

csp.constrain(:x) { |x| x.even? }
csp.constrain(:x,:y) { |x,y| x < y }
csp.constrain(:x,:y,:z) { |x,y,z| x + y + z == 15 }

all_pairs(vars, &predicate)

A shortcut method to apply the given predicate as a binary constraint to all pairs of variables.

csp.all_pairs([:x,:y,:z]) { |a,b| a == b }

all_same(vars)

A shortcut method to ensure that all variables have the same value. Equivalent to calling all_pairs(vars) { |a,b| a == b }.

csp.all_same([:x, :y, :z])

all_different(vars)

A shortcut method to ensure that all variables have different values. Equivalent to calling all_pairs(vars) { |a,b| a != b }.

csp.all_different([:x, :y, :z])

solve()

Find a solution to the current CSP instance. The resulting solution will be a hash of the form variable => value. If no solutions exist, this method will return false. If a unique solution exists, this method will return that solution. If multiple solutions exist, this function will return the first solution found (may not be the same every time due to randomization).

csp.solve
#=> { :x => 4, :y => 5, :z => 6 }

Mathdoku

In file: lib/mathdoku.rb

Inherits from CSP

new(n)

Create a new n×n Mathdoku puzzle. This initializes a board with Symbol vars named like battleship coordinates: Columns are represented by a capital letter, and rows are represented by a number.

Initial constraints are that the values of each row must all be different, and the values of each column must all be different. Initial domains are the integer values 1 through n.

Values may be assigned to cells using #assign.

md = Mathdoku.new(4)
md.assign B3: 1, D4: 3

sum(value, *vars)

Specify a group of cells whose sum is value.

md.sum 6, :A1, :A2, :B2

difference(value, v1, v2)

Specify two cells whose difference is value.

md.difference 1, :B1, :C1

product(value, *vars)

Specify a group of cells whose product is value.

md.product 16, :D1, :D2, :C2,

quotient(value, v1, v2)

Specify two cells whose quotient is value.

md.quotient 2, :A3, :A4

print!(solution)

Prints a solution returned by #solve in an easy-to-read grid layout.

sol = md.solve
md.print! sol

# 1 3 2 4
# 3 2 4 1
# 4 1 3 2
# 2 4 1 3

Sudoku

class

In file: lib/sudoku.rb.

Inherits from CSP.

new(n)

Create a new n²×n² Sudoku puzzle. This initializes a board with Symbol vars named like battleship coordinates: Columns are represented by a capital letter, and rows are represented by a number.

Initial constraints are that the values of each row must all be different, the values of each column must all be different, and the values of each n×n sub-grid must all be different. Initial domains are the integer values 1 through n².

Values may be assigned to cells using #assign.

sd = Sudoku.new(3)
sd.assign({
  :C1 => 3, :D1 => 2, :I1 => 6,
  :A2 => 1, :C2 => 2, :E2 => 6, :G2 => 3,
  :A3 => 4, :B3 => 7, :G3 => 2, :H3 => 8,
  :D4 => 4, :G4 => 8, :H4 => 9,
  :B5 => 4, :C5 => 7, :D5 => 8, :E5 => 5, :F5 => 9, :G5 => 6, :H5 => 2,
  :B6 => 9, :C6 => 8, :F6 => 6,
  :B7 => 6, :C7 => 9, :H7 => 1, :I7 => 8,
  :C8 => 1, :E8 => 9, :G8 => 5, :I8 => 3,
  :A9 => 8, :F9 => 1, :G9 => 9
})

print!(solution)

Prints a solution returned by #solve in an easy-to-read grid layout.

See Mathdoku#print!.

sol = sd.solve
sd.print! sol

# 9 5 3 2 8 4 1 7 6
# 1 8 2 9 6 7 3 5 4
# 4 7 6 1 3 5 2 8 9
# 6 1 5 4 2 3 8 9 7
# 3 4 7 8 5 9 6 2 1
# 2 9 8 7 1 6 4 3 5
# 5 6 9 3 4 2 7 1 8
# 7 2 1 6 9 8 5 4 3
# 8 3 4 5 7 1 9 6 2

License

CSP Solver is licensed under the MIT license below. If this presents a problem for you in any way, please let me know and I will consider relicensing the software for you.

The MIT License (MIT)

Copyright © 2014 Matthew Barry

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.