This package aims to be a constraint solver written in Julia and will be documented completely on my blog OpenSourc.es
- Easily extendable
- Teaching/Learning about constraint programming
You can install this julia package using
] add ConstraintSolver
or if you want to change code you might want to use
] dev ConstraintSolver
.
You can easily use this package using the same modelling package as you might be used to for solving (non)linear problems in Julia: JuMP.jl.
using JuMP
grid = [6 0 2 0 5 0 0 0 0;
0 0 0 0 0 3 0 4 0;
0 0 0 0 0 0 0 0 0;
4 3 0 0 0 8 0 0 0;
0 1 0 0 0 0 2 0 0;
0 0 0 0 0 0 7 0 0;
5 0 0 2 7 0 0 0 0;
0 0 0 0 0 0 0 8 1;
0 0 0 6 0 0 0 0 0]
using ConstraintSolver
const CS = ConstraintSolver
# creating a constraint solver model and setting ConstraintSolver as the optimizer.
m = Model(CS.Optimizer)
# define the 81 variables
@variable(m, 1 <= x[1:9,1:9] <= 9, Int)
# set variables if fixed
for r=1:9, c=1:9
if grid[r,c] != 0
@constraint(m, x[r,c] == grid[r,c])
end
end
for rc = 1:9
@constraint(m, x[rc,:] in CS.AllDifferentSet())
@constraint(m, x[:,rc] in CS.AllDifferentSet())
end
for br=0:2
for bc=0:2
@constraint(m, vec(x[br*3+1:(br+1)*3,bc*3+1:(bc+1)*3]) in CS.AllDifferentSet())
end
end
optimize!(m)
# retrieve grid
grid = convert.(Int, JuMP.value.(x))
You can see a list of currently supported constraints in the docs. This constraint solver works only with bounded discrete variables.
- Setup of the solver and basic backtracking for Sudoku
- Pruning in Sudoku
- More pruning and benchmarks
- Sophisticated implementation of the alldifferent constraint and benchmarks
- New data structure for better user interface and performance
- Backtrack without recursion and start of sum constraint
- Speed up the sum constraint
- UI changes and refactoring
- Recap video
- First step in graph coloring
- Comarison with MIP using graph coloring
- Documentation with Documenter.jl and newest Benchmarking results
- How to profile Julia code
- Second take on bipartite matchings
- Making it a JuMP solver
- Dealing with real objectives
- Support for linear objectives
- Table logging
- Bound computation
- v0.1.0
I'm a MSc student in computer science so I don't have much knowledge on how constraint programming works but I'm keen to find out ;)
If you find a bug or improvement please open an issue or make a pull request. You just enjoy reading and want to see more posts and get them earlier? Support me on Patreon or click on the support button at the top of this website. ;)