Ostomachion coloring

By Laurent Lessard

This problem appeard in The Riddler on January 26, 2018. A full write-up of my solution appears in this blog post.

In [22]:
using JuMP, PyPlot, Gurobi, Combinatorics
In [23]:
# shape coordinates (matrices where first row is xcoords, second row is ycoords)
shapes = [ [0 3 2 0; 0 0 4 0], [3 3 2 3; 0 6 4 0], [3 6 6 4 3 3; 0 0 6 8 6 0], [6 8 6 6; 0 4 6 0],
    [6 12 8 6; 0 0 4 0], [0 4 2 0; 0 8 10 0], [0 2 0 0; 0 10 12 0], [0 4 6 0; 12 8 12 12],
    [4 6 6 4; 8 6 12 8], [6 8 9 6 6; 6 4 6 12 6], [8 12 9 8; 4 0 6 4], [9 12 12 9; 6 0 6 6],
    [9 12 12 9; 6 6 8 6], [9 12 12 6 9; 6 8 12 12 6] ]

# number of shapes in total
N = length(shapes)

# compute areas for each of the shapes
areas = zeros(N,1)
for (i,s) in enumerate(shapes)
    x = s[1,:]
    y = s[2,:]
    k = length(x)
    areas[i] = 0.5*(dot(x[1:k-1],y[2:k]) - dot(y[1:k-1],x[2:k]))
end

# specification of which shapes touch which other shapes (edges in the graph)
edges = [(1,2),(1,6),(2,3),(2,6),(3,4),(3,6),(3,9),(4,5),(4,10),
    (5,11),(6,7),(6,8),(7,8),(8,9),(9,10),(10,11),(10,14),(11,12),(12,13),(13,14)]

# number of edges
E = length(edges);
In [63]:
C = 4  # number of colors

m = Model(solver=GurobiSolver(OutputFlag=0,PoolSearchMode=2,PoolSolutions=100000))
@variable(m, groups[1:C,1:N], Bin)
@constraint(m, csum[i=1:N], sum(groups[:,i])==1 )  # each shape belongs to exactly one group
@constraint(m, rsum[j=1:C], sum(groups[j,i]*areas[i] for i = 1:N) == sum(areas)/C ) # each group has same frac of tot area
for k = 1:E
    @constraint(m, groups[:,edges[k][1]] + groups[:,edges[k][2]] .<= 1)  # colors must be different across edges
end
@constraint(m, groups[1,1] == 1)  # the first triangle is green
status = @time solve(m)
Academic license - for non-commercial use only
  0.032049 seconds (171 allocations: 53.047 KiB)
Out[63]:
:Optimal
In [64]:
# extract all solutions
g = getrawsolver(m)
solcount = Gurobi.get_sol_count(g)
sols = Dict()
for solnumber = 1:solcount
    Gurobi.set_int_param!(g, "SolutionNumber", solnumber-1)
    sol = Gurobi.get_dblattrarray(g, "Xn", 1, Gurobi.num_vars(g))
    rsol = round.( Int, reshape(sol,(N,C))' )
    sols[rsol] = 0
end

# remove duplicate solutions
qq = permutations(collect(1:C))
hh = copy(sols)
for k in keys(hh)
    if haskey(sols,k)
        for q in qq
            delete!(sols,k[q,:])
        end
        sols[k] = 0
    end
end
println("There are ", length(keys(sols)), " distinct solutions")
There are 9 distinct solutions
In [65]:
# colors for the different regions
col = ["green","blue","red","orange","yellow","cyan"]

# plot the solutions
figure(figsize=(10,10))
for (p,g) in enumerate(keys(sols))
    subplot(3,3,p)    

    # plot each of the shapes
    for j = 1:C
        gx = find(g[j,:])
        for i in gx
            fill( shapes[i][1,:], shapes[i][2,:], col[j])
            plot( shapes[i][1,:], shapes[i][2,:], "k-")
        end
    end
    axis("image")
    axis("off")
    # plot the gridlines
    for i = 1:11
        plot( [i,i], [0,12], ":", linewidth=1, color="black" )
        plot( [0,12], [i,i], ":", linewidth=1, color="black" )
    end
end
#savefig("osto4.png")
In [ ]: