# CSP Solver

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

Download
Current version: **v0.0.1**

This project started out of a desire to write a program to solve Mathdoku puzzles, but I wanted it to have the flexibility to solve any CSP. It was a good artificial intelligence exercise, and it was a lot of fun to make.

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 class

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 class

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.

A | B | C | D | |
---|---|---|---|---|

1 | `:A1` |
`:B1` |
`:C1` |
`:D1` |

2 | `:A2` |
`:B2` |
`:C2` |
`:D2` |

3 | `:A3` |
`:B3` |
`:C3` |
`:D3` |

4 | `:A4` |
`:B4` |
`:C4` |
`:D4` |

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.

**Note:**Solution must be the same size as the

`Mathdoku`

instance.
```
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*^{2}×*n*^{2} 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.

A | B | C | D | E | F | G | H | I | |||
---|---|---|---|---|---|---|---|---|---|---|---|

1 | `:A1` |
`:B1` |
`:C1` |
`:D1` |
`:E1` |
`:F1` |
`:G1` |
`:H1` |
`:I1` |
||

2 | `:A2` |
`:B2` |
`:C2` |
`:D2` |
`:E2` |
`:F2` |
`:G2` |
`:H2` |
`:I2` |
||

3 | `:A3` |
`:B3` |
`:C3` |
`:D3` |
`:E3` |
`:F3` |
`:G3` |
`:H3` |
`:I3` |
||

4 | `:A4` |
`:B4` |
`:C4` |
`:D4` |
`:E4` |
`:F4` |
`:G4` |
`:H4` |
`:I4` |
||

5 | `:A5` |
`:B5` |
`:C5` |
`:D5` |
`:E5` |
`:F5` |
`:G5` |
`:H5` |
`:I5` |
||

6 | `:A6` |
`:B6` |
`:C6` |
`:D6` |
`:E6` |
`:F6` |
`:G6` |
`:H6` |
`:I6` |
||

7 | `:A7` |
`:B7` |
`:C7` |
`:D7` |
`:E7` |
`:F7` |
`:G7` |
`:H7` |
`:I7` |
||

8 | `:A8` |
`:B8` |
`:C8` |
`:D8` |
`:E8` |
`:F8` |
`:G8` |
`:H8` |
`:I8` |
||

9 | `:A9` |
`:B9` |
`:C9` |
`:D9` |
`:E9` |
`:F9` |
`:G9` |
`:H9` |
`:I9` |

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*^{2}.

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.

**Note:**Solution must be the same size as the

`Sudoku`

instance.
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 © 2017 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.