15 puzzle solver: Difference between revisions
Content added Content deleted
(Undo revision 306069 by Kaviyarasu (talk)) |
|||
Line 2,564: | Line 2,564: | ||
{{output}} <pre> |
{{output}} <pre> |
||
FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd |
FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd |
||
</pre> |
|||
====Alternate==== |
|||
<lang Lua> |
|||
---------- |
|||
-- SOLVER |
|||
---------- |
|||
local table_concat = table.concat -- local alias |
|||
local function Solver(root, h, successors) |
|||
local pathlist, pathhash, iters |
|||
-- it is required that "h(node)" returns: |
|||
-- 0 when "is_goal(node)==true" |
|||
-- >0 when "is_goal(node)==false" |
|||
-- (because it allows for some simplification herein) |
|||
local FOUND = 0 -- ie: "is_goal(node)==true" |
|||
local NOT_FOUND = 1e9 -- some number larger than largest possible f |
|||
local function hash(node) |
|||
return table_concat(node,",") |
|||
end |
|||
local function search(g, bound) |
|||
iters = iters + 1 |
|||
--if ((iters % 1000000) == 0) then print("iterations:", iters) end |
|||
local node = pathlist[#pathlist] |
|||
local h = h(node) |
|||
local f = g + h |
|||
if (f > bound) then return f end |
|||
if (h == FOUND) then return FOUND end |
|||
local min = NOT_FOUND |
|||
for succ, cost in successors(node) do |
|||
local succhash = hash(succ) |
|||
if (not pathhash[succhash]) then |
|||
pathlist[#pathlist+1], pathhash[succhash] = succ, true |
|||
local t = search(g+cost, bound) |
|||
if (t == FOUND) then return FOUND end |
|||
if (t < min) then min = t end |
|||
pathlist[#pathlist], pathhash[succhash] = nil, nil |
|||
end |
|||
end |
|||
return min |
|||
end |
|||
return { |
|||
solve = function() |
|||
pathlist = { root } |
|||
pathhash = { [hash(root)] = true } |
|||
iters = 0 |
|||
local bound = h(root) |
|||
while true do |
|||
bound = search(0, bound) |
|||
if (bound == FOUND) then return bound, iters, pathlist end |
|||
if (bound == NOT_FOUND) then return bound, iters, nil end |
|||
end |
|||
end |
|||
} |
|||
end |
|||
------------------ |
|||
-- DOMAIN SUPPORT |
|||
------------------ |
|||
local i2c = { [0]=0, 1,2,3,4, 1,2,3,4, 1,2,3,4, 1,2,3,4 } -- convert index to column |
|||
local i2r = { [0]=0, 1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4 } -- convert index to row |
|||
local R, U, L, D = 1, -4, -1, 4 -- move indexing values |
|||
local movenames = { -- move names |
|||
[0]="", [R]="r", [U]="u", [L]="l", [D]="d" |
|||
} |
|||
local succmoves = { -- successor directions |
|||
{R,D}, {R,L,D}, {R,L,D}, {L,D}, |
|||
{R,U,D}, {R,U,L,D}, {R,U,L,D}, {U,L,D}, |
|||
{R,U,D}, {R,U,L,D}, {R,U,L,D}, {U,L,D}, |
|||
{R,U}, {R,U,L}, {R,U,L}, {U,L} |
|||
} |
|||
local manhdists = { -- manhattan distances |
|||
{ [0]=0, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6 }, |
|||
{ [0]=0, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5 }, |
|||
{ [0]=0, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4 }, |
|||
{ [0]=0, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3 }, |
|||
{ [0]=0, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5 }, |
|||
{ [0]=0, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4 }, |
|||
{ [0]=0, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3 }, |
|||
{ [0]=0, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2 }, |
|||
{ [0]=0, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4 }, |
|||
{ [0]=0, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3 }, |
|||
{ [0]=0, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2 }, |
|||
{ [0]=0, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1 }, |
|||
{ [0]=0, 3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3 }, |
|||
{ [0]=0, 4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2 }, |
|||
{ [0]=0, 5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1 }, |
|||
{ [0]=0, 6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0 }, |
|||
} |
|||
--- create a state from a pattern, optionally applying a move |
|||
local function state(patt, move) |
|||
local node = {} |
|||
for k,v in pairs(patt) do node[k] = v end |
|||
if (move) then |
|||
local e = node.e |
|||
local ep = e + move |
|||
node[e], node[ep] = node[ep], 0 |
|||
node.e, node.m = ep, move |
|||
end |
|||
return node |
|||
end |
|||
--- iterator for successors of node |
|||
local function successors(node) |
|||
local moves = succmoves[node.e] |
|||
local i, n = 0, #moves |
|||
return function() |
|||
i = i + 1 |
|||
if (i <= n) then |
|||
return state(node, moves[i]), 1 |
|||
end |
|||
end |
|||
end |
|||
--- hueristic estimate of travel cost from node to goal |
|||
local function h(node) |
|||
local sum, ijx, jix, t = 0, 1, 1 |
|||
for i = 1, 4 do |
|||
local colmax, rowmax = 0, 0 |
|||
for j = 1, 4 do |
|||
t = node[ijx] |
|||
sum = sum + manhdists[ijx][t] -- manhattan |
|||
if (i2r[t] == i) then -- row conflicts |
|||
if (t > rowmax) then rowmax=t else sum=sum+2 end |
|||
end |
|||
t = node[jix] |
|||
if (i2c[t] == i) then -- col conflicts |
|||
if (t > colmax) then colmax=t else sum=sum+2 end |
|||
end |
|||
ijx, jix = ijx+1, jix+4 |
|||
end |
|||
jix = jix - 15 |
|||
end |
|||
return sum |
|||
end |
|||
------------------ |
|||
-- PRINT SUPPORT: |
|||
------------------ |
|||
local function printnode(node) |
|||
print("+--+--+--+--+") |
|||
for i = 0, 12, 4 do |
|||
print( string.format("|%2d|%2d|%2d|%2d|", node[i+1], node[i+2], node[i+3], node[i+4]) ) |
|||
print("+--+--+--+--+") |
|||
end |
|||
end |
|||
local function printpath(path) |
|||
-- note that #path is 1 longer than solution due to root node at path[1] |
|||
-- concatenated result will be correct length since movenames[root.m]=="" |
|||
local t = {} |
|||
for i, node in ipairs(path) do |
|||
t[i] = movenames[node.m] |
|||
end |
|||
local pathstr = table_concat(t) |
|||
print("SOLUTION: " .. pathstr .. " (length: " .. #pathstr .. ")") |
|||
end |
|||
--------- |
|||
-- TASKS: |
|||
--------- |
|||
-- goal is implied by h(), never actually used (see solver's notes) |
|||
-- local goal = state({ 1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0, e=16, m=0 }) |
|||
do |
|||
print("PRIMARY TASK (OPTIMALLY)") |
|||
local sclock = os.clock() |
|||
local root = state({ 15,14,1,6, 9,11,4,12, 0,10,7,3, 13,8,5,2, e=9, m=0 }) |
|||
printnode(root) |
|||
local solver = Solver(root, h, successors) |
|||
local bound, iters, path = solver:solve() |
|||
printpath(path) |
|||
printnode(path[#path]) |
|||
print("ITERATIONS: " .. iters) |
|||
print("ELAPSED: " .. (os.clock()-sclock) .. "s") |
|||
end |
|||
print() |
|||
do |
|||
print("EXTRA CREDIT TASK (APPROXIMATELY, NON-OPTIMALLY)") |
|||
-- only primary task specifies "fewest possible moves" |
|||
-- extra credit task only specifies "solve", so.. |
|||
local sclock = os.clock() |
|||
local root = state({ 0,12,9,13, 15,11,10,14, 3,7,2,5, 4,8,6,1, e=1, m=0 }) |
|||
printnode(root) |
|||
local function hec(node) |
|||
-- overweighting h makes it not admissible, |
|||
-- causing solver to favor g when minimizing, |
|||
-- leading to non-optimal (but much easier to find!) solutions |
|||
return h(node)*1.5 |
|||
end |
|||
local solver = Solver(root, hec, successors) |
|||
local bound, iters, path = solver:solve() |
|||
printpath(path) --> 86, optimal solution is known to be 80 |
|||
printnode(path[#path]) |
|||
print("ITERATIONS: " .. iters) |
|||
print("ELAPSED: " .. (os.clock()-sclock) .. "s") |
|||
end |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
PRIMARY TASK (OPTIMALLY) |
|||
+--+--+--+--+ |
|||
|15|14| 1| 6| |
|||
+--+--+--+--+ |
|||
| 9|11| 4|12| |
|||
+--+--+--+--+ |
|||
| 0|10| 7| 3| |
|||
+--+--+--+--+ |
|||
|13| 8| 5| 2| |
|||
+--+--+--+--+ |
|||
SOLUTION: rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd (length: 52) |
|||
+--+--+--+--+ |
|||
| 1| 2| 3| 4| |
|||
+--+--+--+--+ |
|||
| 5| 6| 7| 8| |
|||
+--+--+--+--+ |
|||
| 9|10|11|12| |
|||
+--+--+--+--+ |
|||
|13|14|15| 0| |
|||
+--+--+--+--+ |
|||
ITERATIONS: 4963696 |
|||
ELAPSED: 34.279s |
|||
EXTRA CREDIT TASK (APPROXIMATELY, NON-OPTIMALLY) |
|||
+--+--+--+--+ |
|||
| 0|12| 9|13| |
|||
+--+--+--+--+ |
|||
|15|11|10|14| |
|||
+--+--+--+--+ |
|||
| 3| 7| 2| 5| |
|||
+--+--+--+--+ |
|||
| 4| 8| 6| 1| |
|||
+--+--+--+--+ |
|||
SOLUTION: rrdldruldluruldrdrrululdrddlluurrddlluurrdrdllurrdlluruurddluurddluulddrdluluruldddrrr (length: 86) |
|||
+--+--+--+--+ |
|||
| 1| 2| 3| 4| |
|||
+--+--+--+--+ |
|||
| 5| 6| 7| 8| |
|||
+--+--+--+--+ |
|||
| 9|10|11|12| |
|||
+--+--+--+--+ |
|||
|13|14|15| 0| |
|||
+--+--+--+--+ |
|||
ITERATIONS: 1325248 |
|||
ELAPSED: 9.101s |
|||
</pre> |
</pre> |
||