Solving 15Puzzle with Julia

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)
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") • Did you test the code with other testcases? Did it provide the correct output on those? – Mast Sep 3 '20 at 21:13 • Yes. [1,2,3,4,5,6,7,9,8] works fine.....as does [6,5,4,1,7,3,9,8,2] Sep 3 '20 at 21:29 • 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. Sep 17 '20 at 10:00 • @Gr3g-prog sorry to leave you waiting, you didn't ping me on SO, so I forgot. Oct 11 '20 at 15:24 2 Answers 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 # CartesianIndexs 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 prints 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.

• Sorry for delay...got sidetracked on some other things. Great code style. Thanks for this. Dec 11 '20 at 8:35

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
• 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. Sep 17 '20 at 4:51
• Works Now! Thanks again for insight. Sep 17 '20 at 7:14