Eternity

eternity.jl

using ConstraintSolver
using JuMP
const CS = ConstraintSolver
include("plot_search_space.jl")

function read_puzzle(fname)
    lines = readlines("data/$fname")
    npieces = length(lines)
    puzzle = zeros(Int, (npieces, 5))
    for i=1:npieces
        puzzle[i,1] = i
        parts = split(lines[i], " ")
        puzzle[i,2:end] = parse.(Int, parts)
    end
    return puzzle
end

function get_rotations(puzzle)
    npieces = size(puzzle)[1]
    rotations = zeros(Int, (npieces*4,5))
    rotation_indices = [[2,3,4,5], [3,4,5,2], [4,5,2,3], [5,2,3,4]]
    for i=1:npieces
        j = 1
        for rotation in rotation_indices
            rotations[(i-1)*4+j, 1] = i
            rotations[(i-1)*4+j, 2:end] = puzzle[i,rotation]
            j += 1
        end
    end

    return rotations
end

function main(fname="eternity_7")
    puzzle = read_puzzle(fname)
    rotations = get_rotations(puzzle)
    npieces = size(puzzle)[1]
    width = convert(Int, sqrt(npieces))
    height = convert(Int, sqrt(npieces))
    ncolors = maximum(puzzle[:,2:end])
    println("Ncolors: $ncolors")

    m = Model(CS.Optimizer)
    @variable(m, 1 <= p[1:height, 1:width] <= npieces, Int)
    @variable(m, 0 <= pu[1:height, 1:width] <= ncolors, Int)
    @variable(m, 0 <= pr[1:height, 1:width] <= ncolors, Int)
    @variable(m, 0 <= pd[1:height, 1:width] <= ncolors, Int)
    @variable(m, 0 <= pl[1:height, 1:width] <= ncolors, Int)

    @constraint(m, p[:] in CS.AllDifferentSet())
    for i=1:height, j=1:width
        @constraint(m, [p[i,j], pu[i,j], pr[i,j], pd[i,j], pl[i,j]] in CS.TableSet(rotations))
    end

    # borders
    # up and down
    for j=1:width
        @constraint(m, pu[1,j] == 0)
        @constraint(m, pd[height,j] == 0)

        if j != width
            @constraint(m, pr[1,j] == pl[1,j+1])
            @constraint(m, pr[height,j] == pl[height,j+1])
        end
    end

     # right and left
     for i=1:height
        @constraint(m, pl[i,1] == 0)
        @constraint(m, pr[i,width] == 0)

        if i != height
            @constraint(m, pd[i,1] == pu[i+1,1])
            @constraint(m, pd[i,width] == pu[i+1,width])
        end
    end

    for i=1:height-1, j=1:width-1
        @constraint(m, pd[i,j] == pu[i+1, j])
        @constraint(m, pr[i,j] == pl[i, j+1])
    end

    start_piece = findfirst(i->count(c->c == 0, puzzle[i,:]) == 2,1:npieces)
    @constraint(m, p[1,1] == start_piece)
    println("start_piece: $start_piece")

    optimize!(m)

    status = JuMP.termination_status(m)
    println(status)

    sp = convert.(Int, JuMP.value.(p))
    spu = convert.(Int, JuMP.value.(pu))
    spr = convert.(Int, JuMP.value.(pr))
    spd = convert.(Int, JuMP.value.(pd))
    spl = convert.(Int, JuMP.value.(pl))

    plot_eternity(puzzle, sp, spu, spr, spd, spl, "eternity")
end

eternity_7

8 6 6 5
7 7 4 4
1 2 0 0
4 4 5 7
6 6 7 8
1 0 2 5
1 0 3 7
6 1 0 3
0 3 5 2
2 1 0 0
6 5 7 8
5 5 4 8
2 2 0 0
6 3 0 3
0 1 7 1
3 7 2 0
6 5 8 4
7 7 5 6
7 3 0 1
8 6 7 5
3 0 1 5
4 4 7 8
3 6 1 0
5 5 8 4
3 0 2 4
0 1 6 1
0 0 2 3
1 7 3 0
4 4 5 8
0 3 5 3
0 1 5 1
6 7 5 7
2 8 2 0
6 6 6 4
7 8 4 8
2 0 1 8
8 8 8 4
5 5 5 7
6 5 6 8
2 0 3 6
5 8 6 7
8 4 6 7
8 7 5 8
2 6 3 0
4 8 4 7
4 8 6 4
2 7 2 0
7 4 4 4
6 4 8 5

plot_search_space.jl

using Plots
using ColorSchemes
rectangle(w, h, x, y) = Shape(x .+ [0, w, w, 0], y .+ [0, 0, h, h])

function plot_eternity(puzzle, sol_id, sol_u, sol_r, sol_d, sol_l, fname)
    plot(;
        size = (900, 900),
        legend = false,
        xaxis = false,
        yaxis = false,
        aspect_ratio = :equal,
    )
    npieces = size(puzzle)[1]
    width = convert(Int, sqrt(npieces))
    height = convert(Int, sqrt(npieces))

    colors = ColorSchemes.Accent_8
    for r=1:height, c=1:width
        plot!(
            rectangle(1, 1, c - 1, height - r),
            color = "white"
        )
        x = c - 0.5
        y = height + 1 - r - 0.5
        if sol_id[r,c] != 0
            annotate!(x, y, text(string(sol_id[r,c]), 20, :black))
        end
        # up 
        plot!(
            Shape([x-0.5, x+0.5, x], [y+0.5, y+0.5, y+0.2]),
            color = sol_u[r,c] == 0 ? :black : colors[sol_u[r,c]]
        )

        # down
        plot!(
            Shape([x-0.5, x+0.5, x], [y-0.5, y-0.5, y-0.2]),
            color = sol_d[r,c] == 0 ? :black : colors[sol_d[r,c]]
        )

        # right
        plot!(
            Shape([x+0.5, x+0.5, x+0.2], [y+0.5, y-0.5, y]),
            color = sol_r[r,c] == 0 ? :black : colors[sol_r[r,c]]
        )

        # left
        plot!(
            Shape([x-0.5, x-0.5, x-0.2], [y+0.5, y-0.5, y]),
            color = sol_l[r,c] == 0 ? :black : colors[sol_l[r,c]]
        )
    end

    png("images/$(fname)")
end