Building a constraint programming solver in Julia

More than 2 years ago I wrote a Sudoku solver in Python. I really enjoyed it and therefore I've spend some time to do the same in Julia just faster ;) Then I wanted to build a whole constraint-programming solver in Julia. Well I actually still want to do it. It will be hard but fun. I want to share my way on my blog and instead of writing when I've done something I want to share my journey while I'm doing it.

Additionally the blog should be as simple as possible and everyone should be able to follow step by step.

In my dream we are building this together so if there is someone out there who is crazy and wants to build a constraint-programming solver from scratch... Send me a mail (o.kroeger@opensourc.es) and/or comment on this post.

In this first post I'll create the package and create test cases as well as building the most basic solver using backtracking. In the next stages we will build the alldifferent, straights, sum constraint and so on together. The next post will be similar to the previous Sudoku post but with animation and of course written in Julia.

Let's get started:

First we create a package:

julia
(v1.2) pkg> generate ConstraintSolver
Generating project ConstraintSolver:
    ConstraintSolver/Project.toml
    ConstraintSolver/src/ConstraintSolver.jl

(v1.2) pkg> activate ConstraintSolver/
Activating environment at `~/Julia/ConstraintSolver/Project.toml`

(v1.2) pkg> develop .
 Resolving package versions...
  Updating `~/.julia/environments/v1.2/Project.toml`
  [e0e52ebd] + ConstraintSolver v0.1.0 [`../../../Julia/ConstraintSolver`]
  Updating `~/.julia/environments/v1.2/Manifest.toml`
  [e0e52ebd] + ConstraintSolver v0.1.0 [`../../../Julia/ConstraintSolver`]

Info: You get to the package mode with ].

I want to have a git repository for the project and we can do this inside the julia shell as well.

shell> cd ConstraintSolver/
/home/ole/Julia/ConstraintSolver

shell> git init
Initialized empty Git repository in /home/ole/Julia/ConstraintSolver/.git/

Info: You get to the shell mode with ;.

The next thing for me is always to create a simple test file which I call current.jl which is inside .gitignore so that I can test the same thing on different branches.

shell> mkdir test
shell> touch test/current.jl
shell> vim .gitignore

Now before we do something like loading modules I would advise to use Revise which helps in general to avoid reloading the REPL when we change code.

julia> using Revise

The current.jl file is not a real test it's more like a playground.

Inside I wrote:

using ConstraintSolver

CS = ConstraintSolver
include("sudoku_fcts.jl")

function main()
    com = CS.init()

    grid = zeros(Int8,(9,9))
    grid[1,:] = [0 0 0 5 4 6 0 0 9]
    grid[2,:] = [0 2 0 0 0 0 0 0 7]
    grid[3,:] = [0 0 3 9 0 0 0 0 4]
    grid[4,:] = [9 0 5 0 0 0 0 7 0]
    grid[5,:] = [7 0 0 0 0 0 0 2 0]
    grid[6,:] = [0 0 0 0 9 3 0 0 0]
    grid[7,:] = [0 5 6 0 0 8 0 0 0]
    grid[8,:] = [0 1 0 0 3 9 0 0 0]
    grid[9,:] = [0 0 0 0 0 0 8 0...

Read full post at opensourc.es