#!/usr/bin/lua


--[[
     8-puzzle solver


     The 8-puzzle is a small board game for a single player. It consists
     of 8 square tiles numbered 1 through 8 and one blank space on a 3 x 3
     board.
     (A 15-puzzle, using a 4 x 4 board, is commonly sold as a child's puzzle.
     An 8-puzzle is used here to keep the search space reasonable.)
     Moves of the puzzle are made by sliding an adjacent tile into the
     position occupied by the blank space, which has the effect of exchanging
     the positions of the tile and blank space. Only tiles that are horizontally
     or vertically adjacent (not diagonally adjacent) may be moved into the blank
     space.


     Goal states are:


        1 2 3        1 2 3
        4 5 6        8 0 4
        7 8 0        7 6 5


     See also: 3.2.Example Problems (Russel S. and Norvig P. (2003).
     Atificial Intelligence. A Modern Approach. Second Edition. Prentice Hall)


     This program is made available under the GNU GPL version 2.0 or greater.


     This program is distributed WITHOUT ANY WARRANTY; without even the
     implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


     Copyright (C) 2009, Vadym Shpuryk 




local P = {}
local P_mt = { __index = P }


local Puzzle = {
                  {  -- Goal 1
                     Goal = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} },
                     Test = {
                              { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} }, -- inv=0  "Goal" passed
                              { {7, 2, 4}, {5, 0, 6}, {8, 3, 1} }  -- inv=16 passed
                            }
                  },
                  {  -- Goal 2
                     Goal = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} },
                     Test = {
                              { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} }, -- inv=0  "Goal" passed
                              { {2, 4, 3}, {1, 0, 6}, {7, 5, 8} }, -- inv=11 No Solution
                              { {1, 2, 3}, {4, 0, 8}, {5, 6, 7} }, -- inv=10 passed
                              { {1, 3, 4}, {8, 6, 2}, {7, 0, 5} }, -- inv=4  "Easy" passed
                              { {2, 8, 1}, {0, 4, 3}, {7, 6, 5} }, -- inv=10 "Medium" passed
                              { {2, 8, 1}, {4, 6, 3}, {0, 7, 5} }, -- inv=10 "Hard" passed
                              { {5, 6, 7}, {4, 0, 8}, {3, 2, 1} }  -- inv=16 "Worst" passed
                     }
                  }
               }


local RowOf = {}
local ColOf = {}
local Queue = {}
local Vertices = {}




function MakeIndexes(goal)
--[[
    For Goal state:
        1 2 3
        4 5 6
        7 8 0
    --             1 2 3 4 5 6 7 8 0
    local RowOf = {1,1,1,2,2,2,3,3,3}
    local ColOf = {1,2,3,1,2,3,1,2,3}


    For Goal state:
        1 2 3
        8 0 4
        7 6 5
    --             1 2 3 4 5 6 7 8 0
    local RowOf = {1,1,1,2,3,3,3,2,2}
    local ColOf = {1,2,3,3,3,2,1,1,2}
]]
    local RowOf = {}
    local ColOf = {}
    local index
    for x = 1,3 do
        for y = 1,3 do
            index = goal[x][y]
            if goal[x][y] == 0 then index = 9 end
            RowOf[index] = x
            ColOf[index] = y
        end
    end
    return RowOf,ColOf
end




function P:new()
    return setmetatable( { State = {{},{},{}}, Ancestor = 0, Cost = 0 , Heuristics = 0 }, P_mt )
end




function P:print()
    for x = 1,3 do
        for y = 1,3 do
            io.write(string.format("%2i ", self.State[x][y]))
        end
        print()
    end
    print("--- H+C="..self.Heuristics.."+"..self.Cost..", A="..self.Ancestor.." ---")
end




function P:RecalcHeuristics()
    local r = 0
    for x = 1,3 do
        for y = 1,3 do
            if self.State[x][y] ~= 0 then
                r = r +
                    math.abs( RowOf[ self.State[x][y] ] -x ) +
                    math.abs( ColOf[ self.State[x][y] ] -y )
                    -- print(self.State[x][y], x, y, r)
            end
        end
    end
    self.Heuristics = r
end




function P:Initialize(...)
    if ... then                        -- it's possible to use predefined State table
        self.State = ...
    else
        local num
        local exist = {}
        math.randomseed(os.time())
        math.random()
        for x = 1,3 do
            for y = 1,3 do
                repeat
                    num = math.random(0, 8)
                until exist[num] == nil
                exist[num] = true      -- e.g.: { [5] = true }
                self.State[x][y] = num
            end
        end
    end
    self.Ancestor = 0                  -- 0 - root vertex
    self:RecalcHeuristics()
    table.insert(Vertices, self)
    table.insert(Queue, 1)
end




function P:Check(value)
    local inv = 0
    for i = 1,9 do
        local x,y = RowOf[i], ColOf[i]
        if self.State[x][y] == value then
            return inv
        end
        if self.State[x][y] > value then
            inv = inv + 1
        end
    end
    return inv
end




function P:isSolution()
    local inv = 0
    for x = 1,3 do
        for y = 1,3 do
            if self.State[x][y] > 0 then
                inv = inv + self:Check(self.State[x][y])
            end
        end
    end
    print("inv="..inv)
    if (inv % 2 == 0) then
       return true
    else
       return false
    end
end




function P_mt:__eq(v)                  -- used by isGoal()
    for x = 1,3 do
        for y = 1,3 do
            if self.State[x][y] ~= v.State[x][y] then
                return false
            end
        end
    end
    return true
end




function isGoal(goal,v)
    local Goal = P:new()
    Goal.State = goal
    if Goal == v then                  -- see function P_mt:__eq()
        return true
    end
    return false
end




function P:copy(tov)
    for x = 1,3 do
        for y = 1,3 do
            tov.State[x][y] = self.State[x][y]
        end
    end
end




function Neighbour(v, idx)
    local zx, zy
    for x = 1,3 do
        for y = 1,3 do
            if v.State[x][y] == 0 then
                zx = x
                zy = y
                break
            end
        end
    end


    local dx = {-1,  0,  1,  0}
    local dy = { 0, -1,  0,  1}


    for k = 1,4 do
        local i = zx + dx[k]
        local j = zy + dy[k]
        if i >= 1 and j >= 1 and i <= 3 and j <= 3 then
             Vertex = P:new()
             v:copy(Vertex)                         -- copy v.State to Vertex.State
             Vertex.State[i][j] = 0                 -- new position for "0"
             Vertex.State[zx][zy] = v.State[i][j]
             Vertex.Cost = v.Cost + 1               -- Parent_vertex_cost + 1
             Vertex:RecalcHeuristics()
             Vertex.Ancestor = idx
             for i = 1,#Vertices do
                 if Vertex == Vertices[i] then
                     Vertex = nil
                     break;
                 end
             end
             if Vertex ~= nil then
                 -- 
                 table.insert(Vertices, Vertex)


                 table.insert(Queue, #Vertices)
                 table.sort(Queue, function(a,b) return Vertices[a].Heuristics+Vertices[a].Cost < Vertices[b].Heuristics+Vertices[b].Cost end)


                 print("Queue("..#Queue..")="..table.concat(Queue, ", ").."\n")
                 -- 
             end
        end
    end
end




-- main


local puznumber = 1                    -- Puzzle number
local testnumber = 2                   -- Test number




local puzzle = Puzzle[puznumber]
local Goal = puzzle.Goal
local Test = puzzle.Test[testnumber]


RowOf,ColOf = MakeIndexes(Goal)
print("RowOf="..table.concat(RowOf, ", "))
print("ColOf="..table.concat(ColOf, ", "))


local A = P:new()
A:Initialize(Test)
A:print()


if A:isSolution() then
    print("Solution Exists");
else
    print("No Solution");
    os.exit()
end


-- os.exit()


local v = P:new()
local c = 0                            -- iteration counter
local idx
while #Queue ~= 0 do
    idx = Queue[1]                     -- index of Vertices current element
    v = Vertices[idx]
    table.remove(Queue,1)
    c = c + 1
    if isGoal(Goal,v) then
        print("--- Finish ---")
        v:print()
        local t = v.Ancestor
        if t > 0 then
            while Vertices[t].Ancestor ~= 0 do
                Vertices[t]:print()
                t = Vertices[t].Ancestor
           end
        end
        print("Iterations="..c)
        break
    else
        Neighbour(v, idx)
    end
end