Building a constraint programming solver in Julia

Ole Kröger — Wed, 04 Sep 2019 22:00:00 +0000

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

Neuromorphic computing: An Overview

Ole Kröger — Mon, 17 Jun 2019 22:00:00 +0000

This is a different blog post than my normal ones. There will most likely be no code (okay there is no code...) and therefore no repository on this one.I'm currently preparing a seminar talk for this topic and find it quite interesting but also relatively complicated. This post is trying to give you an idea about what neuromorphic computing is. Why does it exist? Will it change the world of computing?There will be a some literature references in this post and if you enjoy such non coding posts and hope I'll enjoy writing it :D then I'll consider writing more of these kind. (Writing it was quite nice ;) )

Okay let's begin. What is neuromorphic computing? The idea is basically to make a brain model to understand the human brain better. We wanted to have AI and then we thought okay we know one intelligent creature on this world (whatever intelligent really means) and that is us humans but this idea didn't work out that great mostly because someone found a different way to create something similar which is called deep neural networks. They are easy to train using backpropagation but they have nothing to do with how our brains work. It's similar to airplanes in comparison with birds. They work well but they aren't really biologically inspired. We aren't only interested in creating an AI we are also interested in a better understanding of our own body and especially brain. Which means it is still quite interesting to get back to neuromorphic computing and give it another shot.

Brain vs Deep neural network

I wrote a bit about neural networks on my blog. The general idea is that we have some layers with some neurons and they are all connected to the next layer (fully connected network). The first layer connects to the first hidden layer and the last hidden layer connects to the output layer. The connections have some weights and to obtain the output we go from input layer to output layer and do some matrix matrix multiplications. In general our neural network model is extremely simple and organized and everything flows in one direction. Source: Wikipedia: Artificial neural network

In comparison the brain: We have a bunch of neurons "floating" around. Those are connected to each other in a more random like fashion and there is no direction (it is still a directed graph, but they aren't organized in layers). Additionally artificial neural networks are working with floating point numbers i.e if the input is 0.3 and the weight is 0.2 we get 0.06 as a result input to the next neuron add it up with all the other inputs and then send it over to the next layer. The brain has a different technique. Neurons have more or less two states: They either fire or they chill. That is binary and our computer model uses those complicated floating point numbers. Why???Good question! The point is that our brain works using time,...

Read the full article here

No worries it's free ;)

DEV Community: Ole Kröger

Building a constraint programming solver in Julia

Neuromorphic computing: An Overview

Brain vs Deep neural network