Solving 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.

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)
    end
end

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())
end
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())
end

Next up we need to find all straights.

Let's define it for the 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
            end
            if white[r,c] == 1
                found_straight = true
                push!(vec, (r,c))
            elseif found_straight
                push!(straights, copy(vec))
                empty!(vec)
                found_straight = false
            end
        end
        if found_straight
            push!(straights, copy(vec))
        end
    end
end

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)
end

where get_straights is defined as follows:

function get_straights(numbers, len)
    sort!(numbers)
    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    
        end
    end
    return table
end

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]))
end

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

Result:

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.

Thanks for reading and 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 using Patreon and PayPal.

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).

Any questions, comments or improvements? Please comment here and/or write me an e-mail o.kroeger@opensourc.es and for code feel free to open a PR/issue on GitHub ConstraintSolver.jl

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

Want to be updated? Consider subscribing on Patreon for free