15 puzzle solver: Difference between revisions

</lang>

{{output}} <pre>

</pre>

=={{header|Lua}}==

<lang Lua>

#!/usr/bin/lua

--[[

Solve 3X3 sliding tile puzzle using Astar on Lua. Requires 3mb and

millions of recursions.

by RMM 2020-may-1

]]--

local SOLUTION_LIMIT, MAX_F_VALUE = 100,100

local NR, NC, RCSIZE = 4,4,4*4

local Up, Down, Right, Left = 'u','d','r','l'

local G_cols = {} -- goal columns

local G_rows = {} -- goal rows

local C_cols = {} -- current cols

local C_rows = {} -- current rows

local Goal = {}

local Tiles = {} -- the puzzle

local Solution = {} -- final path is instance of desc

local desc = {} -- descending path

desc[0] = 0 -- override Lua default "1" index

-- @brief create C compatible array for Lua

local function Amake( list )

array = {}

for i=0, #list do

array[i] = list[i+1] -- simulate "C" array in Lua

end

return array

end

G_cols= Amake({0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, } )

G_rows= Amake({0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, } )

C_cols= Amake({0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, } )

C_rows= Amake({0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, } )

Tiles = Amake({ 15,14,1,6, 9,11,4,12, 0,10,7,3, 13,8,5,2,} )

Goal = Amake({1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0,} )

local m1 = {recursions=0, found=0, threshold=0, times=0, steps=0,}

-- ---------------------------------------------------------------

-- return 1D array index given 2D row,column

local function rcidx( row, col )

return (row * NR + col)

end

-- @brief recursive search

-- @return f_score

local function search( depth, x_row, x_col, h_score)

local move, go_back_move, last_move_by_current

local f_score, ix, min, temp, hscore2, idx1

local N_minus_one = NR - 1;

local rc1 = {row=0,col=0}

local rc2 = {row=0,col=0}

local gtmp = {row=0,col=0}

f_score = depth + h_score;

if f_score > m1.threshold then return f_score end

if h_score == 0 then do

m1.found = 1

Solution = table.concat(desc)

return f_score end end

m1.recursions = m1.recursions+1

m1.times = m1.times + 1

if m1.times > 200000 then do

print("Recursions ",m1.recursions)

m1.times = 0

end end

min = 999999

last_move_by_current = desc[depth];

rc1.row = x_row;

rc1.col = x_col;

for ix = 0,3 do

if ix==0 then do

move = Up;

go_back_move = Down;

rc2.row = x_row - 1;

rc2.col = x_col;

end

elseif ix==1 then do

move = Down;

go_back_move = Up;

rc2.row = x_row + 1;

rc2.col = x_col;

end

elseif ix==2 then do

move = Left;

go_back_move = Right;

rc2.row = x_row;

rc2.col = x_col - 1;

end

elseif ix==3 then do

move = Right;

go_back_move = Left;

rc2.row = x_row;

rc2.col = x_col + 1;

end end

if move==Up and x_row==0 then goto next end

if move==Down and x_row==N_minus_one then goto next end

if move==Left and x_col==0 then goto next end

if move==Right and x_col==N_minus_one then goto next end

if last_move_by_current==go_back_move then goto next end

hscore2 = h_score

idx1 = Tiles[rcidx(rc2.row,rc2.col)]

gtmp.row = G_rows[idx1]

gtmp.col = G_cols[idx1]

local h_adj=0

if go_back_move==Up then do

if gtmp.row < C_rows[idx1] then

h_adj = -1 else h_adj = 1 end end

end

if go_back_move==Down then do

if gtmp.row > C_rows[idx1] then

h_adj = -1 else h_adj = 1 end end

end

if go_back_move==Left then do

if gtmp.col < C_cols[idx1] then

h_adj = -1 else h_adj = 1 end end

end

if go_back_move==Right then do

if gtmp.col > C_cols[idx1] then

h_adj = -1 else h_adj = 1 end end

end

hscore2 = hscore2 + h_adj

C_rows[0] = rc2.row;

C_cols[0] = rc2.col;

C_rows[idx1] = rc1.row;

C_cols[idx1] = rc1.col;

Tiles[rcidx(rc1.row,rc1.col)] = idx1;

Tiles[rcidx(rc2.row,rc2.col)] = 0;

desc[depth+1] = move

desc[depth+2] = '\0'

temp = search(depth+1, rc2.row, rc2.col, hscore2); -- descend

-- regress

Tiles[rcidx(rc1.row,rc1.col)] = 0

Tiles[rcidx(rc2.row,rc2.col)] = idx1

desc[depth+1] = '\0'

C_rows[0] = rc1.row;

C_cols[0] = rc1.col;

C_rows[idx1] = rc2.row;

C_cols[idx1] = rc2.col;

if m1.found == 1 then return temp end

if temp < min then min = temp end

::next:: -- Lua does not have "continue;" so uses goto

end -- end for

m1.found = 0;

-- return the minimum f_score greater than m1.threshold

return min;

end

-- @brief Run solver using A-star algorithm

-- @param Tiles .. 3X3 sliding tile puzzle

local function solve(Tiles)

local temp, i,j

local x_row, x_col, h_score = 0,0,0

m1.found = 0;

for i=0,(NR-1) do

for j=0, (NC-1) do

G_rows[ Goal[rcidx(i,j)] ] = i;

G_cols[ Goal[rcidx(i,j)] ] = j;

C_rows[ Tiles[rcidx(i,j)] ] = i;

C_cols[ Tiles[rcidx(i,j)] ] = j;

end

end

for i=0,(NR-1) do

for j=0, (NC-1) do

if Tiles[rcidx(i,j)] == 0 then do

x_row = i;

x_col = j;

break;

end

end

end

end

desc[0] = '$'

desc[1] = '\0'

h_score = 0; -- Manhattan/Taxicab heuristic

for i = 1,(RCSIZE-1) do

h_score = h_score + (math.abs(C_rows[i] - G_rows[i]) +

math.abs(C_cols[i] - G_cols[i]))

end

m1.threshold = h_score

print("solve -> search")

while true do

temp = search( 0, x_row, x_col, h_score);

if m1.found == 1 then do

print("Gound solution of length",#Solution-1)

print(Solution)

break;

end end

if temp > MAX_F_VALUE then do

print("Maximum f value reached! terminating! \n");

break; end

end

m1.threshold = temp;

end -- while

return 0

end

-- show sliding tile puzzle rows and columns

local function print_tiles( pt)

local i,j,num

for i=0,(NR-1) do

for j=0, (NC-1) do

num = pt[rcidx(i,j)]

io.write(string.format("%02d ", num))

end

print("")

end

print("")

end

-- main(void) {

print("Solve sliding 15 tile puzzle");

m1.recursions = 0

m1.times=0

print_tiles(Tiles);

print_tiles(Goal)

solve(Tiles);

</lang>

{{output}} <pre>

FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd