Code to solve a specific jigsaw puzzle in Julia

puzzler.jl

#=
Created on Thu 9 Jan 2020
Last update:

@author: Bram De Jaegher
bram.de.jaegher@gmail.com

@author: Michiel Stock
michielfmstock@gmail.com

Puzzle puzzle!
=#

AI8 = Array{Int8,1}

abstract type AbstractPuzzle end

mutable struct Puzzle <: AbstractPuzzle
    id::String
    idSym::Symbol
    t::AI8
    r::AI8
    b::AI8
    l::AI8
    Puzzle(id, t, r, b, l) = new(id, Symbol(id), t, r, b, l)
end

mutable struct EmptyPuzzle <: AbstractPuzzle
    id::String
    idSym::Symbol
    t::AI8
    r::AI8
    b::AI8
    l::AI8
    EmptyPuzzle() = new(" ", Symbol("empty"), [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0])
end

Base.size(piece::AbstractPuzzle) = (length(piece.r), length(piece.t))
Base.size(piece::AbstractPuzzle, dim::Integer) = size(piece)[dim]

tp(i) = i == 0 ? '-' : i == 1 ? '^' : 'v'
tr(i) = i == 0 ? '|' : i == 1 ? '>' : '<'
tb(i) = i == 0 ? '-' : i == 1 ? 'v' : '^'
tl(i) = i == 0 ? '|' : i == 1 ? '<' : '>'


function Base.string(piece::AbstractPuzzle)
    n, m = size(piece)
    str = ""
    str *= " -" * join(tp.(piece.t), '-') * "- \n"
    for (i, il, ir) in zip(1:n, piece.l, piece.r)
        #println(io, '|' * (' '^(2m+1)) * '|')
        if i != (div(n, 2) + 1)
            str *= tl(il) * (' ' ^(2m+1)) * tr(ir) * "\n"
        else
            str *= tl(il) * ' '^m * "$(piece.id)" * ' '^m * tr(ir) * "\n"
        end
    end
    str *= " -" * join(tb.(piece.b), '-') * "- \n"
end

Base.show(io::IO, piece::AbstractPuzzle)= println(io,string(piece))

piece = Puzzle("A", [0, 0, 0], [-1, -1, 1], [1, 1, -1], [0, 0, 0])

function hflip!(piece::AbstractPuzzle)
    piece.l, piece.r = piece.r, piece.l
    reverse!(piece.t)
    reverse!(piece.b)

    return piece
end

function rotr90!(piece::AbstractPuzzle)
    piece.t, piece.r, piece.b, piece.l = piece.l, piece.t, piece.r, piece.b
    reverse!(piece.t)
    reverse!(piece.b)
    return piece
end

mutable struct Board <: AbstractArray{AbstractPuzzle,2}
    b::Array{Union{Puzzle,EmptyPuzzle},2}
    function Board(n::Int,m::Int)
        b = fill(EmptyPuzzle(),(n,m))
        new(b)
    end
    Board(b::Array{Puzzle,2}) =  new(b)
end

Base.size(board::Board) = size(board.b)
Base.size(board::Board, dim::Integer) = size(board.b)[dim]
Base.getindex(board::Board, args...) = getindex(board.b, args...)
Base.setindex!(board::Board, args...) = setindex!(board.b, args...)

function Base.show(io::IO, board::Board)
    n, m = size(board)
    for i in 1:n
        rowPieces = board[i,1:end]
        alignedPieces = fill("",(5,1))
        for piece in rowPieces
            a = split(string(piece),"\n")[1:end-1]
            alignedPieces = hcat(alignedPieces,a)
        end
        alignedPieces = hcat(alignedPieces,fill("\n",(5,1)))
        alignedPieces = [join(alignedPieces[i,:]) for i in 1:5]
        for row in alignedPieces
            print(io,row)
        end
    end
end

""" Returns the edges of the neighbours """
function neighbourEdges(x::Int, y::Int, board::Board)
    n, m = size(board)
    # right border of left piece
    if (y < 2)   # new piece located on left border?
        left = [0, 0, 0]
    else
        if board[x,y-1] isa EmptyPuzzle
            left = Int8[]
        else
            left = board[x,y-1].r
        end
    end

    # bottom border of top piece
    if x < 2  # new piece located on top border?
        top = [0, 0, 0]
    else
        if board[x-1,y] isa EmptyPuzzle
            top = Int8[]
        else
            top = board[x-1,y].b
        end
    end

    #  top border of bottom piece
    if x >=  n  # new piece located on bottom border?
        bot = [0, 0, 0]
    else
        if board[x+1,y] isa EmptyPuzzle
            bot = Int8[]
        else
            bot = board[x+1,y].t
        end
    end

    # left border of right piece
    if y >=  m  # new piece located on right border?
        right = [0, 0, 0]
    else
        if board[x,y+1] isa EmptyPuzzle
            right = Int8[]
        else
            right = board[x,y+1].l
        end
    end
    return Puzzle("Ω", top, right, bot, left)
end

"""Gives a list of pieces that fit in a certain location"""
function fittingPieces(x::Int, y::Int, board::Board, edge, edgeDict)
    edgePiece = Set()
    compEdgePieces = Set()
    try
        edgePiece = Set(edgeDict[edge])
    catch KeyError
    end
    try
        compEdgePieces = Set(edgeDict[reverse(-1 .*edge)])
    catch KeyError
    end
    oneEdgeMatches = union(edgePiece, compEdgePieces)

    nEdges = neighbourEdges(x, y, board)  # Other edges
    fullMatches = []
    edges = []
    for pieceID in oneEdgeMatches
        (checker, piece, originalEdges) = checkFit(pieceID,nEdges)
        if checker
            push!(fullMatches,piece)
            push!(edges,originalEdges)
        end
    end
    return fullMatches, edges
end

"""Removes a pieces from the edgeDict"""
function remove(piece::Puzzle, edgeDict, edges)
    for edge in edges
        try
            edgeDict[edge] = setdiff(edgeDict[edge],Set([piece.id]))
        catch KeyError
        end
        try
            edgeDict[reverse(-1 .*edge)] = setdiff(edgeDict[reverse(-1 .*edge)],Set([piece.id]))
        catch KeyError
        end
    end
    return edgeDict
end

"""adds a fitting piece to the board"""
function addPiece!(board::Board, edgeDict, location, matchLocation)
    I = location
    if matchLocation == "t"
        (fits, origEdges) = fittingPieces(I[1],I[2], board, reverse(-1 .*board[I[1]-1,I[2]].b), edgeDict)
    else
        (fits, origEdges) = fittingPieces(I[1],I[2], board, reverse(-1 .*board[I[1],I[2]-1].r), edgeDict)
    end
    if length(fits) > 0                 # Piece found?
        randInd = rand(1:length(fits))
        newPiece = fits[randInd] # select a random piece
        #  println("Match $(newPiece)")
        newEdges = origEdges[randInd]
        board[I[1],I[2]] = newPiece
        edgeDict = remove(newPiece, edgeDict, newEdges)     # remove that piece from the edgeDict
        return true
    else
        return false
    end
end

"""Tries to fit a piece to the neighbouring edges"""
function checkFit(pieceID, neighbours)
    piece = puzzlePiecesDict[pieceID]
    checker = [false false false false]
    neighbourEdges = [[neighbours.t] [neighbours.r] [neighbours.b] [neighbours.l]]
    transforms = [x -> x; repeat([x -> rotr90!(x)],4); x -> hflip!(x);
                    repeat([x -> rotr90!(x)],4); x -> hflip!(x)]
    originalEdges = [[piece.t] [piece.r] [piece.b] [piece.l]]
    while (length(transforms)>0) & (sum(checker) < 4)
        transform! = popfirst!(transforms)
        transform!(piece)
        edges = [[piece.t] [piece.r] [piece.b] [piece.l]]
        for (index, neighbourEdge, edge) in zip(1:length(edges), neighbourEdges, edges)
            if length(neighbourEdge) == 3   # empty means no neighbour
                checker[index] = edge .+ neighbourEdge == [0, 0, 0]
            else
                checker[index] = true
            end
        end
    end
    return (sum(checker) == 4, piece, originalEdges)
end

function collectEdges(puzzlePieces)
    edges = []
    for piece in values(puzzlePieces)
        append!(edges,[piece.t])
        append!(edges,[piece.b])
        append!(edges,[piece.l])
        append!(edges,[piece.r])
    end
    unique!(edges)
    edgeDict = Dict(edge => Set() for edge in edges)

    for piece in values(puzzlePieces)
        push!(edgeDict[piece.t],piece.id)
        push!(edgeDict[piece.b],piece.id)
        push!(edgeDict[piece.l],piece.id)
        push!(edgeDict[piece.r],piece.id)
    end
    return edgeDict
end


# Edge numbering
# -1-2-3-
# 1       1
# 2   A   2
# 3       3
# -1-2-3-
let
    minEmpty = 1
    minBoard = []
    for i in 1:500000
        A = Puzzle("A",[-1, 1, 1], [0, 1, -1], [1, 1, 0], [-1, -1, 1])
        B = Puzzle("B",[1, 0, 0], [1, 1, 0], [-1, 0, 1], [-1, 1, 1])
        C = Puzzle("C",[-1, 1, 0], [1, 1, 0], [-1, 0, 0], [-1, 1, 1])
        D = Puzzle("D",[0, 0, 1], [-1, 1, 1], [0, -1, 1], [-1, 1,-1])
        E = Puzzle("E",[0, 1, 0], [1, 1, -1], [1, -1, 1], [0, 0, 0])
        F = Puzzle("F",[1, -1, 1], [0, 1, 0], [1, -1, 0], [-1, -1, 1])
        G = Puzzle("G",[-1, 0, 0], [0, -1, 1], [0, -1, 0], [1, -1, 1])
        H = Puzzle("H",[-1, -1, 1], [0, 1, 0], [1, -1, 0], [-1, -1, 0])
        I = Puzzle("I",[-1, -1, 0], [-1, 0, 0], [0, 1, 0], [-1, 1, 0])
        J = Puzzle("J",[0, 1, 0], [-1, -1, 1], [0, 0, 0], [0, 1, -1])
        K = Puzzle("K",[1, 1, 0], [1, -1, 1], [-1, 1, 1], [0, 0, 0])
        L = Puzzle("L",[0, -1, 0], [1, -1, 0], [1, -1, 1], [-1, -1, 1])
        M = Puzzle("M",[1, -1, 1], [0, 0, 0], [0, 0, 0], [1, -1, 0])
        N = Puzzle("N",[0, 0, -1], [0, -1, 0], [0, 1, -1], [1, -1, 1])
        O = Puzzle("O",[1, 1, -1], [-1, -1, 1], [0, 0, 0], [0, 0, 0])
        P = Puzzle("P",[0, 0, 1], [0, -1, 1], [0, -1, 1], [1, -1, -1])
        Q = Puzzle("Q",[0, 1, -1], [-1, 1, 1], [-1, 1, -1], [-1, 1, -1])
        R = Puzzle("R",[0, 0, 0], [-1, 1, -1], [1, 0, -1], [0, 0, 0])
        S = Puzzle("S",[0, 1, -1], [0, 0, 0], [0, 0, -1], [0, 1, -1])
        T = Puzzle("T",[0, 1, -1], [0, -1, 1], [-1, 1, -1], [1, -1, -1])
        U = Puzzle("U",[0, -1, 0], [-1, 1, 1], [0, 0, -1], [-1, 0, 1])
        V = Puzzle("V",[0, 0, 0], [0, 1, 0], [-1, 1, 1], [1, -1, -1])
        W = Puzzle("W",[0, -1, -1], [1, 0, -1], [0, 0, 0], [1, 1, -1])
        X = Puzzle("X",[-1, 1, 0], [0, -1, -1], [0, 0, 0], [0, 1, 0])
        Y = Puzzle("Y",[0, -1, 0], [0, 0, 0], [0, 0, -1], [0, 0, 1])
        Z = Puzzle("Z",[-1, 1, 1], [-1, 0, 0], [-1, 1, -1], [0, -1, 0])
        p0 = Puzzle("0",[-1, 1, 1], [0, 0, 0], [-1, 0, 1], [-1, -1, 1])
        p1 = Puzzle("1",[0, 1, 0], [-1, 0, 1], [1, -1, -1], [1, 0, 0])
        p2 = Puzzle("2",[0, 0, 1], [0, 0, 0], [0, -1, 1], [-1, 0, 1])
        p3 = Puzzle("3",[0, 0, 0], [-1, 1, -1], [0, -1, 0], [-1, 1, 1])
        p4 = Puzzle("4",[0, -1, 0], [0, -1, 1], [0, 0, 0], [0, 0, 0])
        p5 = Puzzle("5",[-1, 1, -1], [0, 0, 0], [0, 1, -1], [-1, -1, 1])
        p6 = Puzzle("6",[1, -1, -1], [0, 0, 0], [0, 1, 0], [0, 1, -1])
        p7 = Puzzle("7",[-1, 1, 0], [0, 0, 0], [1, -1, -1], [1, 0, 0])
        p8 = Puzzle("8",[1, -1, 0], [0, -1, 1], [0, 0, 0], [1, -1, 1])
        p9 = Puzzle("9",[0, 1, 0], [1, 0, -1], [0, 0, 0], [0, 0, 1])

        match = true
        global counter = 1
        global puzzlePiecesDict = Dict("A"=>A,"B"=>B,"C"=>C,"D"=>D,"E"=>E,"F"=>F,"G"=>G,"H"=>H,"I"=>I,"J"=>J,"K"=>K,"L"=>L,"N"=>N,"P"=>P,"Q"=>Q,"S"=>S,
            "T"=>T,"U"=>U,"V"=>V,"W"=>W,"X"=>X,"Y"=>Y,"Z"=>Z,"0"=>p0,"1"=>p1,"2"=>p2,"3"=>p3,"5"=>p5,"6"=>p6,"7"=>p7,"8"=>p8, "9" => p9)
        cornerPieces = [p4 M O]

        board = Board(6,6)
        board[1,1] = rotr90!(rotr90!(M))

        edgeDict = collectEdges(puzzlePiecesDict)
        solvePath = [(2,1), (1,2), (2,2), (1,3), (2,3), (3,1), (3,2), (3,3),
                (1,4), (2,4), (3,4), (4,1), (4,2), (4,3), (4,4), (5,1), (5,2),
                (5,3), (5,4), (1,5), (2,5), (3,5), (4,5), (5,5), (6,2), (6,3),
                (6,4), (6,5), (2,6), (3,6), (4,6), (5,6)]
        matchPath = ["t", "l", "t", "l", "t", "t", "t", "t",
                "l", "t", "t", "t", "l", "l", "l", "t", "l",
                "l", "l", "l", "t", "t", "t", "t", "t", "l", "l", "l",
                "l", "t", "t", "t"]


        while match & (counter < 30)
            match = addPiece!(board, edgeDict, solvePath[counter], matchPath[counter])
            counter += 1
            numEmpty= 36-sum([board[i,j] isa EmptyPuzzle for i in 1:6 for j in 1:6])
            if numEmpty > minEmpty
                minEmpty = numEmpty
                println(board)
            end
        end
    end
end

Ik zou niet met EmptyPuzzle werken, maar Board definieren als

Board = Array{Union{Puzzle,Nothing}}

met overloading op de show functie voor Board.

Ik zou ook dimensie $N$ als parametrisch type van Puzzle maken.

Wrm id en idSym als twee attributen?

Ik ben wat tegen deadlines aan het botsen dus ben het snel aan het schrijven ;) merci voor de tips ik zal het later nog wat opkuisen. Wel ik heb een symbool nodig voor de lookup table maar een string om printen maar nu besef ik dat dat properder kan Op zo 12 jan. 2020 om 19:07 schreef Michiel Stock <notifications@github.com>

…

Ik zou niet met EmptyPuzzle werken, maar Board definieren als Board = Array{Union{Puzzle,Nothing}} met overloading op de show functie voor Board. Ik zou ook dimensie $N$ als parametrisch type van Puzzle maken. Wrm id en idSym als twee attributen? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/16bad2a496efd2566dafddd79343b62a?email_source=notifications&email_token=ACYUUXBAJKZWRYWI5NJGY7DQ5NL7TA5CNFSM4KFZBPR2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF7LXC#gistcomment-3135345>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACYUUXFVVHYYFCDGB3344QLQ5NL7TANCNFSM4KFZBPRQ> .