3
\$\begingroup\$

Asking here instead of SO as suggested.

I'm trying to use Julia to solve the common tile game 15 Puzzle using Julia using A* algorithm. I am quite new to the language and my style may seem very C like. When I try the following code, I run out of memory. I'm not sure if its related to the use of a pointer style in my structs or just bad design.

struct Node
    parent
    f::Int64
    board::Array{Int64,1}
end

function findblank(A::Array{Int64,1})
    x = size(A,1)
    for i = 1:x
        if A[i] == x
            return i
        end
    end
    return -1
end

function up(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if blank / Nsq <= 1
        return nothing
    end
    B[blank-Nsq],B[blank] = B[blank],B[blank-Nsq]
    return B
end

function down(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank / Nsq) > (Nsq -1)
        return nothing
    end
    B[blank+Nsq],B[blank] = B[blank],B[blank+Nsq]
    return B
end

function left(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank % Nsq) == 1
        return nothing
    end
    B[blank-1],B[blank] = B[blank],B[blank-1]
    return B
end

function right(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank % Nsq) == 0
        return nothing
    end
    B[blank+1],B[blank] = B[blank],B[blank+1]
    return B
end

function manhattan(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    r = 0
    for i in 1:N
        if (A[i]==i || A[i]==N)
            continue
        end
        row1 = floor((A[i]-1) / Nsq)
        col1 = (A[i]-1) % Nsq
        row2 = floor((i-1) / Nsq)
        col2 = (i-1) % Nsq
        r+= abs(row1 - row2) + abs(col1 - col2)
    end
    return r
end  

# start = [1,2,3,4,5,6,7,9,8]
# start = [6,5,4,1,7,3,9,8,2] #26 moves
start = [7,8,4,11,12,14,10,15,16,5,3,13,2,1,9,6] # 50 moves
goal = [x for x in 1:length(start)]
# println("The manhattan distance of $start is  $(manhattan(start))")
g = 0
f = g + manhattan(start)
pq = PriorityQueue()
actions = [up,down,left,right]
dd = Dict{Array{Int64,1},Int64}()
snode = Node(C_NULL,f,start)
enqueue!(pq,snode,f)
pos_seen = 0
moves = 0
while (!isempty(pq))
    current = dequeue!(pq)
    if haskey(dd,current.board)
        continue
    else
        push!(dd, current.board =>current.f)
    end
    if (current.board == goal)
        while(current.board != start)
            println(current.board)
            global moves +=1
            current = current.parent[]
        end
        println(start)
        println("$start solved in $moves moves after looking at $pos_seen positions")
        break
    end
    global pos_seen+=1
    global g+=1
    for i in 1:4
        nextmove = actions[i](current.board)
        if (nextmove === nothing || nextmove == current.board || haskey(dd,nextmove))
            continue
        else
            global f = g+manhattan(nextmove)
            n = Node(Ref(current),f,nextmove)
            enqueue!(pq,n,f)
        end
    end
end
println("END")
\$\endgroup\$
4
  • \$\begingroup\$ Did you test the code with other testcases? Did it provide the correct output on those? \$\endgroup\$
    – Mast
    Sep 3 '20 at 21:13
  • \$\begingroup\$ Yes. [1,2,3,4,5,6,7,9,8] works fine.....as does [6,5,4,1,7,3,9,8,2] \$\endgroup\$
    – Gr3g-prog
    Sep 3 '20 at 21:29
  • \$\begingroup\$ Please do not append code to your question, doing so goes against the Question + Answer style of Code Review. If you'd like a review of your latest version of the code please post a new question. Additionally please see what you may and may not do after receiving answers for alternate options. \$\endgroup\$
    – Peilonrayz
    Sep 17 '20 at 10:00
  • \$\begingroup\$ @Gr3g-prog sorry to leave you waiting, you didn't ping me on SO, so I forgot. \$\endgroup\$ Oct 11 '20 at 15:24
3
\$\begingroup\$

That was a fun exercise to work on! I completely refactored the code; the basic complexity issue Marc mentions still holds.

I recommend this blog post for the cartesian indexing tricks.

# we need this include
using DataStructures


# let's define some constants -- barcode is explained below
const Barcode = Int64 # can be switche out for a larger type if necessary
const Board = Matrix{Int64}

# assuming `board` is a square matrix
boardsize(board) = size(board, 1)

# shorter version, altough we get rid of this below
# by storing the blank position instead of recalculating
findblank(board) = findfirst(==(length(board)), board)

# save some array allocation: instead of hashing, we can directly 
# encode each board permutation in a sufficiently large integer
# by using the length of the board as basis of a number system
function barcode(board)
    s = one(Barcode) # be type stable!
    bc = zero(Barcode)
    base = length(board)
    
    for n in board
        bc += n * s
        s *= base
    end

    return bc
end

# those four function can be generalized.  we conveniently use 
# `CartesianIndex`s here, as in `manhattan`.
function try_move(board, blank, action)
    delta = CartesianIndex(action...)
    moved = blank + delta
    
    if !checkbounds(Bool, board, moved)
        return nothing
    else
        new_board = copy(board)
        new_board[blank], new_board[moved] = new_board[moved], new_board[blank]
        return new_board, moved
    end
end

# I think I got this right... since we store the board as a matrix 
# anyway, we can directly access the indices.
function manhattan(board)
    N = boardsize(board)
    
    return sum(CartesianIndices(board)) do ix
        row1, col1 = Tuple(ix)
        col2, row2 = divrem(board[ix] - 1, N) .+ 1 # column major!
        abs(row1 - row2) + abs(col1 - col2)
    end
end


# redo some things.  storing the `f` here is not necessary; on the 
# other hand, we can get rid of recalculating the blank position and 
# and simply store it here, after every move.
# the parent can become a small `Union`, no need for pointers
# (never use `C_NULL` unless for interop!)
# the barcodes also only need to be calculated once
struct Node
    board::Board
    blank::CartesianIndex
    parent::Union{Node, Nothing}
    barcode::Barcode

    function Node(
        board::Board,
        blank::CartesianIndex,
        parent::Union{Node, Nothing}
    )
        @assert size(board, 1) == size(board, 2)
        return new(board, blank, parent, barcode(board))
    end
end

Node(board, blank) = Node(board, blank, nothing)

# factor out this loop into its own function -- it is not part of the 
# solution, but needed only once the solution is found
function backtrace(node)
    current_node = node
    trace = Board[current_node.board]
    
    while !isnothing(current_node.parent)
        current_node = current_node.parent
        push!(trace, current_node.board)
    end

    return reverse(trace)
end


# since this remains global, make it a constant. also, it is of known
# size and immutable, so a tuple is better
const ACTIONS = ((+1, 0), (-1, 0), (0, -1), (0, +1))

function try_solve(start_board, goal_board)
    g = 0
    
    pq = PriorityQueue()
    start_node = Node(start_board, findblank(start_board))
    
    enqueue!(pq, start_node, manhattan(start_board))
    seen_barcodes = Set{Barcode}([start_node.barcode])
    goal_barcode = barcode(goal_board)

    # early return, since otherwise we only check immediately
    # after a move
    (start_node.barcode == goal_barcode) && return start_node, 1
    
    while !isempty(pq)
        g += 1
        current_node = dequeue!(pq)
        
        for action in ACTIONS
            move_result = try_move(current_node.board, current_node.blank, action)
            
            if !isnothing(move_result)
                moved_board, new_blank = move_result
                new_node = Node(moved_board, new_blank, current_node)
                
                if new_node.barcode == goal_barcode
                    return new_node, length(seen_barcodes)
                elseif new_node.barcode ∉ seen_barcodes
                    f = g + manhattan(moved_board)
                    enqueue!(pq, new_node, f)
                    push!(seen_barcodes, new_node.barcode)
                end
            end
        end
    end

    # I tried to keep `print`s out of the calculation function; this
    # one's useful for debugging, though:
    # println("Tried $(length(seen_barcodes)) boards")
    return nothing
end

# put main code into a function -- always put as many things into
# functions as possible
function main()
    # Again, Julia matrices are column major, so I needed to 
    # transpose the boards to meaningfully work with the indexing

    # 0 moves
    # start_board = [
    #     1 4 7
    #     2 5 8
    #     3 6 9
    # ]

    # 4 moves
    # start_board = [
        # 1 9 4
        # 2 5 7
        # 3 6 8
    # ]
    
    # 26 moves
    # start_board = [
    #     6 1 9
    #     5 7 8
    #     4 3 2
    # ]
    
    # 50 moves
    start_board = [
        7  12  16  2
        8  14   5  1
        4  10   3  9
        11 15  13  6
    ]
    
    # quick way to initialize the reference matrix
    goal_board = reshape(1:length(start_board), size(start_board))

    println("The manhattan distance of the start board is $(manhattan(start_board))")
    
    # let's also print some time and memory statistics
    @time solution = try_solve(start_board, goal_board)
    
    if !isnothing(solution)
        solution_node, pos_seen = solution
        trace = backtrace(solution_node)

        println("Solved puzzle in $(length(trace)) moves after looking at $pos_seen positions.  Steps: ")
        foreach(println, trace)
    else
        println("Failed to solve puzzle")
        println(start_board)
    end
end

# corresponds to `if __name__ == __main__` in Python; only run
# `main()` when called as a script
if abspath(PROGRAM_FILE) == @__FILE__
    main()
end

A cool improvement would be to use multithreading for processing the queue. And one probably could also completely avoid storing the board as matrix by switching to the barcode representation everywhere (basically, a bitvector in a generalized basis) -- both left as an exercise. There are even succinter codings for permuations, though.

I tried running the 50-moves problem, but killed the program at 1 GiB.

\$\endgroup\$
1
  • \$\begingroup\$ Sorry for delay...got sidetracked on some other things. Great code style. Thanks for this. \$\endgroup\$
    – Gr3g-prog
    Dec 11 '20 at 8:35
3
\$\begingroup\$

It looks like you store the board after each movement for each possibility, that's a lot of arrays in memory, no wonder it fills your memory

for your second example, your code looks for 157523 positions, which is half of the total possibilities.

the number of permutations for 1:16 is enormous, the a-star algorithm is probably not sufficient

even if you look at only 1% of the total possibilities, you would need hundreds of gigabytes if not terabytes to store them

[6, 5, 4, 1, 7, 3, 9, 8, 2] solved in 26 moves after looking at 157523 positions

julia> using Combinatorics

julia> length(permutations(1:9))
362880

julia> length(permutations(1:16))
20922789888000
\$\endgroup\$
2
  • \$\begingroup\$ Thanks @Marc. By comparison, the version I wrote in pure C only looks at 4434 positions and also solves in 26 moves. I'm sure that something is missing in my code but being new to Julia cant seem to put my finger on it. \$\endgroup\$
    – Gr3g-prog
    Sep 17 '20 at 4:51
  • \$\begingroup\$ Works Now! Thanks again for insight. \$\endgroup\$
    – Gr3g-prog
    Sep 17 '20 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.