Article Image
Est Reading time: 9 minutes

ConstraintSolver.jl - Str8ts

This is part 21 of an ongoing series about: How to build a constraint solver? You might want to check out earlier posts if you're new. See first post.

In short: I'm creating a constraint solver from scratch in Julia. You can follow the project on my GitHub repo. Whenever I add something not too small I'll post about it in my blog. Sometimes I also make a post of small stuff when there is enough of it. If you're interested in some special thing which you don't understand please open an issue and I'll explain my thoughts.

Mostly these posts are about implementing something new in the constraint solver itself or changing the structure like refactoring. Sometimes it's just nice to see what we can do with what we have so far. Yesterday I've posted a blog post about the table constraint. I felt that this might be interesting for those of you who are really interested in this project but I think that there are way more people who might be interested in what to do with it than a dry version of how it works. Therefore here you can read the: How to solve Str8ts using our constraint solver without changing the solver :D

What is Str8ts?

Str8ts is similar to sudoku as it uses the all different constraint as well as it is played on a 9x9 grid.


This is a fairly simple Str8ts so it provides us with a good start.

The rules:

  • Each white field has to have a digit in the end
  • No digit can appear more than once in each row/col.
  • White fields which are connected (no black cell in between) in a row/col must form a straight.

Black cells without a digit are just defining the straight block. With a digit they are also used for the all different constraint of the second rule.

If we have a look at the first col we can immediately fill it.

Str8ts first col

The one in the upper left can only be 7 or 9 based on the straights constraint and 7 exists already in the column therefore it must be 9. It's very similar for the six and the 2 is the only option to create a straight.

Defining the variables

There are always two things we need to define to solve such a puzzle:

What are the variables and what are the constraints?

In sudoku it was very easy as we had 81 variables and 27 constraints no matter what. Here it is a bit more complicated. We can take some different routes here and mine is probably not the best but hopefully quite simple to understand.

I decided to have 81 variables as well this time ranging from 0-9 this time. Each white field needs to be between 1-9 and each black field which isn't assigned a number in the starting configuration is set to 0.

Before we have that in code we need to define the grid first. I use two arrays for this. The first is the same as in sudoku holding the digits and 0 if not filled yet. The second array just saves whether a cell is white or black. I call it white so it's 1 if the cell is white and 0 if it's black.

The above puzzle is then represented by:

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

white = zeros(Int, (9,9))
white[1,:] = [1, 1, 0, 1, 1, 1, 0, 1, 1]
white[2,:] = [1, 1, 1, 1, 1, 0, 0, 1, 1]
white[3,:] = [0, 1, 1, 0, 0, 1, 1, 1, 0]
white[4,:] = [1, 1, 0, 1, 1, 1, 1, 1, 0]
white[5,:] = [1, 1, 0, 1, 1, 1, 0, 1, 1]
white[6,:] = [0, 1, 1, 1, 1, 1, 0, 1, 1]
white[7,:] = [0, 1, 1, 1, 0, 0, 1, 1, 0]
white[8,:] = [1, 1, 0, 0, 1, 1, 1, 1, 1]
white[9,:] = [1, 1, 0, 1, 1, 1, 0, 1, 1]

And yes one can define it without writing white[X,:] all the time and white could be Boolean but this all doesn't matter here ;)

Okay defining the variables in JuMP:

using JuMP
using ConstraintSolver
const CS = ConstraintSolver

m = Model(CS.Optimizer)
@variable(m, 0 <= x[1:9,1:9] <= 9, Int)

# set variables
for r = 1:9, c = 1:9
    if grid[r, c] != 0
        @constraint(m, x[r,c] == grid[r, c])
    elseif white[r,c] == 1
        @constraint(m, x[r,c] >= 1)
    else # black ones without a number
        @constraint(m, x[r,c] == 0)

Let's check out the constraints.

Defining the constraints

For this it's important to fully understand the rules of course and I first did a mistake here. I thought I can just use all different constraints with 9 variables for each row and column but this of course doesn't work because we have the black cells which are set to 0. It is important to notice that the black cells can have multiple digits for the all different constraint so it's not just a digit which doesn't need to be solved it's not really a specified digit at all.

Hope I didn't confuse you...

What I mean is the all different constraints should only consider the white cells and black cells with a digit not the black ones without a digit.

We can define the 18 constraints with:

for r = 1:9
    variables = [x[r,c] for c = 1:9 if white[r,c] == 1 || grid[r,c] != 0]
    @constraint(m, variables in CS.AllDifferentSet())
for c = 1:9
    variables = [x[r,c] for r = 1:9 if white[r,c] == 1 || grid[r,c] != 0]
    @constraint(m, variables in CS.AllDifferentSet())

Next up we need to find all straights.

Let's define it for the first row:

First row

We start with a white cell which is part of a straight therefore we create a new straight vector.

  • Then we move to the next cell which is also white so we add it to the current straight vector.
  • The black cell terminates the straight and we add the current straight to the list of all straights.
  • A new straight vector is created in cell 4.
  • ...
  • In the end we can think of a black cell at the border such that we don't forget to add the last straight to the list of straights.

In my code this might look a bit ugly so maybe you have a better idea ;)

straights = []
for row_or_col in [:row, :col]
    for i = 1:9
        found_straight = false
        vec = Vector{Tuple{Int, Int}}()
        for j = 1:9
            r, c = i, j
            if row_or_col == :col
                r,c = j, i
            if white[r,c] == 1
                found_straight = true
                push!(vec, (r,c))
            elseif found_straight
                push!(straights, copy(vec))
                found_straight = false
        if found_straight
            push!(straights, copy(vec))

The straights vector now holds

Any[[(1, 1), (1, 2)], [(1, 4), (1, 5), (1, 6)], [(1, 8), (1, 9)], ... ]

Okay what do we do with this now?

We need to generate all possible straights with length 1-9. (Actually only 2-8 as if the length is 1 or 9 it's always a straight)

This can be done with the function permutations from Combinatorics.jl.

straight_tables = Vector{Array{Int,2}}(undef, 9)
for i=1:9
    straight_tables[i] = get_straights(collect(1:9), i)

where get_straights is defined as follows:

function get_straights(numbers, len)
    nrows = (length(numbers)-len+1)*factorial(len)
    table = Array{Int64}(undef,(nrows,len))
    i = 1
    for j=1:length(numbers)-len+1
        l = numbers[j:j+len-1]
        for row in permutations(l, len)
            table[i,:] = row      
            i += 1    
    return table

Here I compute the number of combinations first and then fill it with the permutations such that all are straights.

An output of straight tables:

julia> straight_tables[2]
16×2 Array{Int64,2}:
 1  2
 2  1
 2  3
 3  2
 3  4
 4  3
 7  6
 7  8
 8  7
 8  9
 9  8

This is the correct format for the table constraint.

The last thing we need is:

for straight in straights
    len = length(straight)
    variables = [x[s[1],s[2]] for s in straight]
    @constraint(m, variables in CS.TableSet(straight_tables[len]))

status = JuMP.termination_status(m)
println("Status: $status")
println("Solved in [s]: ", MOI.get(m, MOI.SolveTime()))


Solved Str8ts

This was solved without backtracking in about 0.03 seconds on my machine. (Solve time is without creating the tables)

Next up I want to do some simple Eternity solving.

You need to update the ConstraintSolver for this to v0.1.2.

Several updates are mentioned in the new post Bugs & Benchmarks

Thanks for reading! Stay home and be safe!

Special thanks to my five patrons!

List of patrons paying more than 4\$ per month:

  • Site Wang
  • Gurvesh Sanghera
  • Szymon Bęczkowski

Currently I get 18\$ per month from my patrons on Patreon.

For a donation of a single dollar per month you get early access to the posts. Try it out at the start of a month and if you don't enjoy it just cancel your subscription before pay day (end of month).

What do I wanna do with this money? If you find it useful and want to show your appreciation I would be very happy. I do this in my free time but would like to make a living out of it. I know that this will be hard.

There are currently some things that I don't like about this blog and let me know if you have something to add: I don't like the CMS anymore and want to build everything in Julia. I found Franklin to be perfect for it.

The best thing is that I'll have full control over the design there.

I currently publish all my new posts there first so if you want to use it now... Patreon!

I'll keep you updated on Twitter OpenSourcES as well as my more personal one: Twitter Wikunia_de

Become a Patron!
Follow the blog on Twitter
Blog Comments powered by Disqus.
Blog Logo

Ole Kröger




Back to Overview