# CSP Solver

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 n2×n2 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 n2.

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