--[[
This is a Lua version of Donald Knuth's sliding-block solver, but with
a few changes to allow the goal to have fewer pieces than the start.
It also fixes a couple of bugs in Knuth's code (thanks to Tom Rokicki).

The original CWEB program is available here:
https://www-cs-faculty.stanford.edu/~knuth/programs/sliding.w

Or you might prefer this typeset version:
http://www.trevorrow.com/glu/sliding.pdf
--]]

local glu = glu()
local cp = require "cplus" -- for cp.process
local fmt = string.format

-- comment out the next 2 lines to see console output
local print = function()end
io.write = print

-- solution will be passed back to caller as an array of board states
local board_states = {}
local found_solution = false -- need this instead of non-local "goto hurray"

-- these allow goal to specify fewer pieces than start
local gcount = 0            -- number of pieces in goal
local simple_goal = false   -- true if gcount < bcount
local gboard = {}           -- board with goal position
local gpiece = {}
local gplace = {}

local style = 0
local verbose = 0
local bdry = 999999
local obst = 999998
local maxsize = 256
local boardsize = maxsize * 3 + 2
local bufsize = 1024
local hashsize = math.floor(2^13)
local memsize = math.floor(2^25)
local maxmoves = 1000
local board = {} -- [boardsize]
local aboard = {} -- [boardsize]
local rows = 0
local cols = 0
local colsp = 0
local ul, lr = 0, 0
local delta = {} -- delta[4] = { 1, -1 }
local off = {} -- [maxsize]
local offstart = {} -- [16]
local buf = {} -- char[bufsize]
local bcount = 0 -- number of pieces in start
local piece = {} -- [maxsize]
local apiece = {} -- [maxsize]
local place = {} -- [maxsize]
local aplace = {} -- [maxsize]
local xboard = {} -- char[boardsize]
local config = {} -- [maxsize / 8]
local hash = {} -- [hashsize]
local hashh = {} -- [hashsize]
local pos = {} -- [memsize + maxsize / 8 + 1]
local cutoff = 0
local cutoffh = 0
local curpos = 0
local curposh = 0
local source = 0
local sourceh = 0
local nextsource, nextsourceh = 0, 0
local maxpos = 0
local maxposh = 0
local configs = 0
local configsh = 0
local oldconfigs = 0
local milestone = {} -- [maxmoves]
local milestoneh = {} -- [maxmoves]
local shortcut = 0
local goalhash = 0
local goal = {} -- [maxsize / 8]
local start = {} -- [maxsize / 8]
local head = {} -- [maxsize + 1]
local out = {} -- [maxsize + 1]
local inn = {} -- [maxsize + 1]   was keyword "in" so renamed to inn
local link = {} -- [boardsize]
local olink = {} -- [boardsize]
local ilink = {} -- [boardsize]
local perm = {} -- [maxsize + 1]
local iperm = {} -- [maxsize + 1]
local decision = {} -- char[maxsize]
local inx = {} -- [maxsize]
local lstart = {} -- [maxsize]
local super = {} -- [maxsize]
local uni = { {}, {}, {}, {} } -- [4][256]

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

local function warning(msg)
    glu.warn(msg)
end

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

local function boardover()
    warning("Sorry, I can't handle that large a board;\nplease increase maxsize.")
end

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

local function bcell(j, k)
    return board[ul + j * colsp + k]
end

local function acell(j, k)
    return aboard[ul + j * colsp + k]
end

local function gcell(j, k)
    return gboard[ul + j * colsp + k]
end

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

local function hashcode(x)
    return uni[1][x & 0xff] + uni[2][(x >> 8) & 0xff] +
           uni[3][(x >> 16) & 0xff] + uni[4][x >> 24]
end

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

local function fill_board(board, piece, place)
    local j, c, k, t = 0,0,0,0
    for j = 0, ul-1 do board[j] = bdry end
    for j = ul, lr do board[j] = -1 end
    j = ul + cols
    while j <= lr do
        board[j] = bdry
        j = j + colsp
    end
    while j <= lr + colsp do
        board[j] = bdry
        j = j+1
    end
    local p = 0
    j = ul
    local pcount = 0
    c = 0
    while buf[p] ~= '\n' do
        while board[j] >= 0 do
            j = j+1
            if j > lr then return -1 end
        end
        if buf[p] == '0' then
            board[j] = 0
            t = 0
        elseif buf[p] >= '1' and buf[p] <= '9' then
            t = tonumber(buf[p])
        elseif buf[p] >= 'a' and buf[p] <= 'f' then
            t = tonumber(buf[p],16)
        elseif buf[p] == 'x' then
            t = 0
            board[j] = obst
        else
            return -2
        end
        if t ~= 0 then
            pcount = pcount+1
            piece[pcount] = t
            place[pcount] = j
            board[j] = pcount
            k = offstart[t]
            while off[k] ~= 0 do
                if j + off[k] < ul or j + off[k] > lr or board[j + off[k]] >= 0 then
                    c = c+1
                else
                    board[j + off[k]] = pcount
                end
                k = k+1
            end
        end
        j = j+1
        p = p+1
    end
    while j <= lr do
        if board[j] < 0 then board[j] = 0 end
        j = j+1
    end
    return c, pcount
end

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

local function get_board(board, piece, cell)
    -- this routine is used to return the solution back to the caller
    local bstring = ""
    for j = 0, rows-1 do
        for k = 0, cols-1 do
            if cell(j, k) < 0 then
                bstring = bstring.."?" -- should never happen
            elseif cell(j, k) < obst then
                bstring = bstring..fmt("%x", piece[cell(j, k)])
            elseif cell(j, k) == obst then
                bstring = bstring.."x"
            else
                bstring = bstring.." " -- should never happen
            end
        end
        bstring = bstring.."\n"
    end
    return bstring
end

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

local function print_board(board, piece, cell)
    for j = 0, rows-1 do
        for k = 0, cols-1 do
            if cell(j, k) < 0 then
                io.write("?") -- should never happen
            elseif cell(j, k) < obst then
                io.write(fmt("%x", piece[cell(j, k)]))
            elseif cell(j, k) == obst then
                io.write("x")
            else
                io.write(" ") -- should never happen
            end
        end
        io.write("\n")
    end
    --[[ Knuth's code:
    for j = 0, rows-1 do
        for k = 0, cols-1 do
            if cell(j, k) == cell(j - 1, k) and cell(j, k) ~= 0 and cell(j, k) < obst then
                io.write(" |")
            else
                io.write("  ")
            end
        end
        io.write("\n")
        for k = 0, cols-1 do
            if cell(j, k) < 0 then
                io.write(" ?")
            elseif cell(j, k) < obst then
                if cell(j, k) == cell(j, k - 1) and cell(j, k) ~= 0 and cell(j, k) < obst then
                    io.write("-")
                else
                    io.write(" ")
                end
                io.write(fmt("%x", piece[cell(j, k)]))
            else
                io.write("  ")
            end
        end
        io.write("\n")
    end
    --]]
end

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

local function pack(board, piece)
    local i, j, k, p, s, t = 0,0,0,0,0,0
    for j = ul, lr do xboard[j] = 0 end
    i = 0
    s = 0
    p = 28
    j = ul
    t = bcount
    while t ~= 0 do
        if board[j] < obst and xboard[j] == 0 then
            k = piece[board[j]]
            if k ~= 0 then
                t = t-1
                s = s + (k << p)
                k = offstart[k]
                while off[k] ~= 0 do
                    xboard[j + off[k]] = 1
                    k = k+1
                end
            end
            if p == 0 then
                config[i] = s
                i = i+1
                s = 0
                p = 28
            else
                p = p-4
            end
        end
        j = j+1
    end
    if p ~= 28 then
        config[i] = s
        i = i+1
    end
    return i
end

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

local function print_config(config, n)
    local j = 0
    while j < n - 1 do
        io.write(fmt("%08x", config[j]))
        j = j+1
    end
    local t = config[n - 1]
    j = 8
    while (t & 0xf) == 0 do
        t = t >> 4
        j = j-1
    end
    -- io.write(fmt("%0*x", j, t)) -- "%0*x" is not valid in Lua
    io.write(fmt("%0"..j.."x", t))
end

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

local function unpack(board, piece, place, config, coffset)
    local i, j, k, p, s, t = 0,0,0,0,0,0
    for j = ul, lr do xboard[j] = 0 end
    p = 0
    i = 0
    j = ul
    t = bcount
    while t ~= 0 do
        if board[j] < obst and xboard[j] == 0 then
            if p == 0 then
                s = config[i + coffset]
                i = i+1
                p = 28
            else
                p = p-4
            end
            k = (s >> p) & 0xf
            if k ~= 0 then
                board[j] = t
                piece[t] = k
                place[t] = j
                k = offstart[k]
                while off[k] ~= 0 do
                    xboard[j + off[k]] = 1
                    board[j + off[k]] = t
                    k = k+1
                end
                t = t-1
            else
                board[j] = 0
            end
        end
        j = j+1
    end
    while j <= lr do
        if board[j] < obst and xboard[j] == 0 then board[j] = 0 end
        j = j+1
    end
    return i
end

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

local function print_big(hi, lo)
    print(fmt("%.15g", hi * 4294967296.0 + lo))
end

local function print_bigx(hi, lo)
    if hi ~= 0 then
        print(fmt("%x%08x", hi, lo))
    else
        print(fmt("%x", lo))
    end
end

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

local function hashin(trick)
    local h, j, k, n, bound = 0,0,0,0,0
    n = pack(board, piece)
    h = hashcode(config[0])
    j = 1
    while j < n do
        h = h ~ hashcode(config[j])
        j = j+1
    end
    h = h & (hashsize - 1)
    if hashh[h] == cutoffh then
        if hash[h] < cutoff then
            goto newguy
        end
    elseif hashh[h] < cutoffh then
        goto newguy
    end
    bound = hash[h] - cutoff
    j = hash[h] & (memsize - 1)
    while true do
        local nope = false
        for k = 0, n-1 do
            if config[k] ~= pos[j + 2 + k] then
                nope = true
                break
            end
        end
        
        if nope then
            bound = bound - pos[j]
            if bound < 0 then break end
            j = (j - pos[j]) & (memsize - 1)
            -- continue while loop
        else
            if trick then
                if bound < shortcut then return false end
                n = (j - source) & (memsize - 1)
                if pos[j + 1] == n then return false end
                pos[j + 1] = n
                return true
            end
            return false
        end
    end
    
    ::newguy::

    j = curpos & (memsize - 1)
    pos[j] = curpos - hash[h]
    local temp = 0
    if pos[j] > curpos then temp = 1 end
    if pos[j] > memsize or curposh > hashh[h] + temp then
        pos[j] = memsize
    end
    pos[j + 1] = curpos - source
    for k = 0, n-1 do pos[j + 2 + k] = config[k] end
    hash[h] = curpos
    hashh[h] = curposh

    if configs == oldconfigs or verbose > 0 then
        print_config(config, n)
        if verbose > 0 then
            io.write(" (")
            print_big(configsh, configs)
            io.write("=#")
            print_bigx(curposh, curpos)
            io.write(", from #")
            print_bigx(sourceh, source)
            io.write(")\n")
        end
    end
    configs = configs+1
    if configs == 0 then configsh = configsh+1 end

    curpos = curpos+(n + 2)
    if curpos < n + 2 then curposh = curposh+1 end
    if (curpos & (memsize - 1)) < (n + 2) then curpos = curpos & (-memsize) end
    if curposh == maxposh then
        if curpos <= maxpos then goto okay end
    elseif curposh < maxposh then
        goto okay
    end
    glu.exit("Sorry, but memsize isn't big enough for this puzzle.")
    
    ::okay::
    
    if simple_goal then
        -- check if pieces in goal board match pieces in current board
        for r = 0, rows-1 do
            for c = 0, cols-1 do
                local gval = gcell(r,c)
                if gval > 0 and gpiece[gval] ~= piece[bcell(r,c)] then
                    -- no match
                    return trick
                end
            end
        end
        
        -- the above code detects the vast majority of non-matching boards but
        -- there are cases where we need to check the location of matching pieces

        -- create an array of locations for each piece in board
        local bplace = {}        
        for j = ul, lr do xboard[j] = 0 end
        for r = 0, rows-1 do
            for c = 0, cols-1 do
                local j = ul + r * colsp + c
                local cell = board[j]
                if cell > 0 and cell < obst and xboard[j] == 0 then
                    local k = piece[cell]
                    bplace[cell] = j           -- location of top left cell
                    k = offstart[k]
                    while off[k] ~= 0 do
                        xboard[j + off[k]] = 1 -- ignore later cells in this block
                        k = k+1
                    end
                end
            end
        end
        -- now check locations of matching pieces in goal and board
        for r = 0, rows-1 do
            for c = 0, cols-1 do
                local gval = gcell(r,c)
                if gval > 0 and gval < obst and gplace[gval] ~= bplace[bcell(r,c)] then
                    -- locations are different
                    return trick
                end
            end
        end
        
        goto solved
    end
       
    if h == goalhash then
        for k = 0, n-1 do
            if config[k] ~= goal[k] then return trick end
        end
        goto solved
    else
        return trick
    end

    ::solved::

    -- put final board position in board_states if empty
    -- (board_states will not be empty if knuth_solver had to goto restart)
    if #board_states == 0 then
        board_states = { get_board(board, piece, bcell) }
    end
    
    -- Lua doesn't allow goto hurray here
    found_solution = true
    -- no need to return anything
end

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

local function move(k, del, delo)
    local j, s, t
    s = place[k]
    t = piece[k]
    j = offstart[t]
    while true do
        board[s + off[j]] = 0
        if off[j] == 0 then break end
        j = j+1
    end
    j = offstart[t]
    while true do
        if board[s + del + off[j]] ~= 0 then
            j = offstart[t]
            while true do
                board[s + off[j]] = k
                if off[j] == 0 then break end
                j = j+1
            end
            return
        end
        if off[j] == 0 then break end
        j = j+1
    end
    j = offstart[t]
    while true do
        board[s + del + off[j]] = k
        if off[j] == 0 then break end
        j = j+1
    end
    
    local style2 = hashin(style == 2)
    if found_solution then return end
    
    if style2 or style == 1 then
        j = offstart[t]
        while true do
            board[s + del + off[j]] = 0
            if off[j] == 0 then break end
            j = j+1
        end
        j = offstart[t]
        while true do
            board[s + off[j]] = k
            if off[j] == 0 then break end
            j = j+1
        end
        if style == 1 then
            move(k, del + delo, delo)
            if found_solution then return end
        else
            for j = 0, 3 do
                if delta[j] ~= -delo then
                    move(k, del + delta[j], delta[j])
                    if found_solution then return end
                end
            end
        end
    else
        j = offstart[t]
        while true do
            board[s + del + off[j]] = 0
            if off[j] == 0 then break end
            j = j+1
        end
        
        j = offstart[t]
        while true do
            board[s + off[j]] = k
            if off[j] == 0 then break end
            j = j+1
        end
    end
end

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

local function supermove(del, delo)
    local j, s, t = 0,0,0
    j = 0
    while super[j] ~= 0 do
        board[super[j]] = 0
        j = j+1
    end
    j = 0
    while super[j] ~= 0 do
        if board[del + super[j]] ~= 0 then
            j = 0
            while super[j] ~= 0 do
                board[super[j]] = aboard[super[j]]
                j = j+1
            end
            return
        
        end
        j = j+1
    end
    j = 0
    while super[j] ~= 0 do
        board[del + super[j]] = aboard[super[j]]
        j = j+1
    end

    local style5 = hashin(style == 5)
    if found_solution then return end

    if style5 or style == 4 then
        j = 0
        while super[j] ~= 0 do
            board[del + super[j]] = 0
            j = j+1
        end
        j = 0
        while super[j] ~= 0 do
            board[super[j]] = aboard[super[j]]
            j = j+1
        end
        if style == 4 then
            supermove(del + delo, delo)
            if found_solution then return end
        else
            for j = 0, 3 do
                if delta[j] ~= -delo then
                    supermove(del + delta[j], delta[j])
                    if found_solution then return end
                end
            end
        end
    else
        j = 0
        while super[j] ~= 0 do
            board[del + super[j]] = 0
            j = j+1
        end
        
        j = 0
        while super[j] ~= 0 do
            board[super[j]] = aboard[super[j]]
            j = j+1
        end
    end
end

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

local function ideals(del)
    local j, k, l, p, u, v, t = 0,0,0,0,0,0,0
    for j = 0, bcount do
        perm[j] = j
        iperm[j] = j
    end
    l = 0
    p = 0
    
    ::excl::
    
    decision[l] = 0
    lstart[l] = p
    j = inx[l]
    t = j + 1
    while j < t do
        v = perm[j]
        k = inn[v]
        while k >= 0 do
            u = aboard[k]
            if iperm[u] >= t then
                local uu = perm[t]
                local tt = iperm[u]
                perm[t] = u
                perm[tt] = uu
                iperm[u] = t
                iperm[uu] = tt
                t = t+1
            end
            k = ilink[k]
        end
        if decision[0] == 1 then
            v = head[v]
            while v >= 0 do
                super[p] = v
                p = p+1
                v = link[v]
            end
        end
        j = j+1
    end

    if t > bcount then
        if p ~= 0 then
            super[p] = 0
            if decision[0] == 0 then
                supermove(del, del)
            else
                supermove(-del, -del)
            end
            if found_solution then return end
        end
        goto incl
    end
    
    l = l+1
    inx[l] = t
    goto excl
    
    ::incl::
    
    decision[l] = 1
    p = lstart[l]
    j = inx[l]
    t = j + 1
    while j < t do
        u = perm[j]
        k = out[u]
        while k >= 0 do
            v = aboard[k]
            if iperm[v] >= t then
                local vv = perm[t]
                local tt = iperm[v]
                perm[t] = v
                perm[tt] = vv
                iperm[v] = t
                iperm[vv] = tt
                t = t+1
            end
            k = olink[k]
        end
        if decision[0] == 0 then
            u = head[u]
            while u >= 0 do
                super[p] = u
                p = p+1
                u = link[u]
            end
        end
        j = j+1
    end

    if t > bcount then
        if p ~= 0 then
            super[p] = 0
            if decision[0] == 0 then
                supermove(del, del)
            else
                supermove(-del, -del)
            end
            if found_solution then return end
        end

        goto backup
    end
    
    l = l+1
    inx[l] = t
    goto excl
    
    ::backup::
    
    if l ~= 0 then
        l = l-1
        if decision[l] ~= 0 then goto backup end
        goto incl
    end
end

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

-- the code for gb_init_rand and gb_next_rand comes from gb_flip.c

local A = {} -- A[56]= {-1}
A[0] = -1

local gb_fptr = 0 -- index into A

local function mod_diff(x,y)
    return (x - y) & 0x7fffffff
end

local function gb_flip_cycle()
    local ii = 1
    local jj = 32
    while jj <= 55 do
        A[ii] = mod_diff(A[ii],A[jj])
        ii = ii+1
        jj = jj+1
    end
    jj = 1
    while ii <= 55 do
        A[ii] = mod_diff(A[ii],A[jj])
        ii = ii+1
        jj = jj+1
    end
    gb_fptr = 54
    return A[55]
end

local function gb_next_rand()
    if A[gb_fptr] >= 0 then
        local result = A[gb_fptr]
        gb_fptr = gb_fptr - 1
        return result
    else
        return gb_flip_cycle()
    end
end

local function gb_init_rand(seed)
    local prev = seed
    local nxt = 1
    local m = mod_diff(prev,0)
    seed = m
    prev = m
    A[55] = prev
    local i = 21
    while i ~= 0 do
        A[i] = nxt
        nxt = mod_diff(prev,nxt)
        if seed & 1 ~= 0 then
            seed = 0x40000000 + (seed>>1)
        else
            seed = seed>>1
        end
        nxt = mod_diff(nxt,seed)
        prev= A[i]
        i = (i+21)%55
    end
    gb_flip_cycle()
    gb_flip_cycle()
    gb_flip_cycle()
    gb_flip_cycle()
    gb_flip_cycle()
end

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

local function init_tables()
    -- need to initialize some tables
    for j = 0, hashsize-1 do
        hash[j] = 0
        hashh[j] = 0
    end

    for j = 0, maxsize-1 do inx[j] = 0 end

    delta[0] = 1
    delta[1] = -1

    piece[0] = 0
    apiece[0] = 0
    gpiece[0] = 0
    
    offstart[0] = 0 -- play safe
end

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

function knuth_solver(move_style, puzzle_file, show_progress)
    local j, k, t = 0,0,0
    local d = 0
    local curo = 0
    
    style = move_style
    verbose = 0
    
    init_tables()
    
    -- load puzzle_file
    local f <close> = io.open(puzzle_file, "r")
    if not f then
        warning("Failed to open file:\n"..puzzle_file)
        return
    end

    local line = f:read("*l")
    if not line then
        warning("Could not read first line!")
        return
    end
    rows, cols = line:match("(%d+) x (%d+)")
    rows = tonumber(rows)
    cols = tonumber(cols)
    if rows == nil or cols == nil or rows <= 0 or cols <= 0 then
        warning("Bad specification of rows x cols!")
        return
    end
    if rows * cols > maxsize then boardover() return end

    colsp = cols + 1
    delta[2] = colsp
    delta[3] = -colsp
    
    ul = colsp
    lr = (rows + 1) * colsp - 2

    for j = 1, 15 do offstart[j] = -1 end
    while true do
        ::continue::
        line = f:read("*l")
        if not line then
            warning("Could not read next line!")
            return
        end
        for i = 1, #line do buf[i-1] = line:sub(i,i) end
        buf[#line] = '\n'
        
        if (buf[0] == '\n') then goto continue end
        if buf[1] ~= ' ' or buf[2] ~= '=' or buf[3] ~= ' ' then break end
        if buf[0] >= '1' and buf[0] <= '9' then
            t = tonumber(buf[0])
        elseif buf[0] >= 'a' and buf[0] <= 'f' then
            t = tonumber(buf[0],16)
        else
            warning(fmt("Bad piece name (%c)!", buf[0]))
            return
        end
        if offstart[t] >= 0 then
            warning(fmt("Redefinition of piece %c is being ignored.", buf[0]))
        else
            offstart[t] = curo
            local p = 4
            t = -1
            j = 0
            k = 0
            while true do
                if buf[p] == '1' then
                    if t < 0 then
                        t = k
                    else
                        off[curo] = k - t
                        curo = curo+1
                    end
                    if curo >= maxsize then boardover() return end
                    j = j+1
                    k = k+1
                elseif buf[p] == '0' then
                    j = j+1
                    k = k+1
                elseif buf[p] == '/' then
                    k = k + (colsp - j)
                    j = 0
                elseif buf[p] == '\n' then
                    goto offsets_done
                else
                    warning(fmt("Bad character `%c' in definition of piece %c!", buf[p], buf[0]))
                    return
                end
                p = p+1
            end
            ::offsets_done::
            if t < 0 then
                warning(fmt("Piece %c is empty!", buf[0]))
                return
            end
            off[curo] = 0
            curo = curo+1
            if curo >= maxsize then boardover() return end
        end
    end

    t, bcount = fill_board(board, piece, place)
    if t ~= 0 then
        if t > 0 then
            if t == 1 then
                warning("Oops, you filled a cell twice!")
            else
                warning("Oops, you overfilled cells!")
            end
        elseif t == -1 then
            warning("Oops, your board wasn't big enough!")
        else
            warning("Oops, the configuration contains an illegal character!")
        end
        return
    end
    if bcount == 0 then
        warning("The puzzle doesn't have any pieces!")
        return
    end
    
    print() -- clear the console
    print("Starting configuration:")
    print_board(board, piece, bcell)
    local start_board = get_board(board, piece, bcell)

    line = f:read("*l")
    if not line then
        warning("Failed to read stopping configuration!")
        return
    end
    f:close()
    for i = 1, #line do buf[i-1] = line:sub(i,i) end
    buf[#line] = '\n'

    t, gcount = fill_board(aboard, apiece, aplace)
    if t ~= 0 then
        if t > 0 then
            if t == 1 then
                warning("Oops, you filled a cell twice!")
            else
                warning("Oops, you overfilled cells!")
            end
        elseif t == -1 then
            warning("Oops, your board wasn't big enough!")
        else
            warning("Oops, the configuration contains an illegal character!")
        end
        return
    end
    print("\nStopping configuration:")
    print_board(aboard, apiece, acell)

    for j = ul, lr do
        if (board[j] < obst) ~= (aboard[j] < obst) then
            warning("The dead cells (x's) are in different places!")
            return
        end
    end
    
    simple_goal = gcount < bcount
    if simple_goal then
        -- create a board with the goal position
        fill_board(gboard, gpiece, gplace)
    end

    gb_init_rand(0)
    for j = 1, 4 do
        for k = 1, 255 do
            uni[j][k] = gb_next_rand()
        end
        uni[j][0] = 0   -- needed for hashcode
    end

    print(fmt("\n(using moves of style %d)", style))

    t = pack(board, piece)
    for k = 0, t-1 do
        start[k] = config[k]
    end
    
    board_states = {}   -- initialize this before restart

    ::restart::
    
    found_solution = false

    if not simple_goal then
        t = pack(aboard, apiece)
        goalhash = 0
        for k = 0, t-1 do
            goal[k] = config[k]
            goalhash = goalhash ~ hashcode(config[k])
        end
        goalhash = goalhash & (hashsize - 1)
    end

    curpos, cutoff, milestone[0] = 1,1,1
    curposh, cutoffh, milestoneh[0] = 0,0,0
    source, sourceh, configs, configsh, oldconfigs, d = 0,0,0,0,0,0
    maxposh = 1
    print("*** Distance 0:")

    hashin(false)
    if found_solution then goto hurray end
    
    if verbose <= 0 then print(".") end

    d = 1
    while d < maxmoves do
        print(fmt("*** Distance %d:", d))
        milestone[d] = curpos
        milestoneh[d] = curposh
        oldconfigs = configs

        if d > 1 then
            cutoff = milestone[d - 2]
            cutoffh = milestoneh[d - 2]
        end
        shortcut = curpos - cutoff
        maxpos = cutoff + memsize
        maxposh = cutoffh
        if maxpos < memsize then maxposh = maxposh + 1 end
        source = milestone[d - 1]
        sourceh = milestoneh[d - 1]
        while source ~= milestone[d] or sourceh ~= milestoneh[d] do
        
            -- check for click in Cancel button
            cp.process( glu.getevent() )

            j = unpack(board, piece, place, pos, (source & (memsize - 1)) + 2) + 2
            nextsource = source + j
            nextsourceh = sourceh
            if nextsource < j then nextsourceh = nextsourceh + 1 end
            if (nextsource & (memsize - 1)) < j then nextsource = nextsource & -memsize end
            if style < 3 then
                for j = 0, 3 do
                    for k = 1, bcount do
                        move(k, delta[j], delta[j])
                        if found_solution then
                            goto hurray
                        end
                    end
                end
            else
                for j = 0, bcount do head[j] = -1 end
                for j = 0, lr + colsp do
                    k = board[j]
                    if k ~= 0 then
                        if k >= obst then k = 0 end
                        aboard[j] = k
                        link[j] = head[k]
                        head[k] = j
                    else
                        aboard[j] = -1
                    end
                end

                for j = 0, bcount do
                    out[j] = -1
                    inn[j] = -1
                end
                for j = 0, bcount do
                    k = head[j]
                    while k >= ul do
                        t = aboard[k - colsp]
                        if t ~= j and t >= 0 and (out[t] < 0 or aboard[out[t]] ~= j) then
                            olink[k] = out[t]
                            out[t] = k
                            ilink[k - colsp] = inn[j]
                            inn[j] = k - colsp
                        end
                        k = link[k]
                    end
                end
                
                ideals(colsp)
                if found_solution then goto hurray end
                
                head[0] = lr + 1
                for j = 0, bcount do
                    out[j] = -1
                    inn[j] = -1
                end
                for j = 0, bcount do
                    k = head[j]
                    while k >= ul do
                        t = aboard[k - 1]
                        if t ~= j and t >= 0 and (out[t] < 0 or aboard[out[t]] ~= j) then
                            olink[k] = out[t]
                            out[t] = k
                            ilink[k - 1] = inn[j]
                            inn[j] = k - 1
                        end
                        k = link[k]
                    end
                end
                
                ideals(1)
                if found_solution then goto hurray end
            end
            source = nextsource
            sourceh = nextsourceh
        end

        if configs == oldconfigs then
            -- tell caller there is no solution
            return {}
        end
        if verbose <= 0 then
            print(fmt(" and %d more.", configs - oldconfigs - 1))
        end
        
        -- update the search dialog to give an indication of progress
        show_progress(fmt("Distance %d (%d positions)", d, configs - oldconfigs))
        
        d = d+1
    end
    
    warning(fmt("No solution found yet (maxmoves=%d)!", maxmoves))
    if true then return end

    ::hurray:: -- get here if found_solution is true

    if d == 0 then
        -- caller checks for this so should never see
        print("The puzzle is solved in zero moves!")
        return
    end
    
    print("... Solution!")

    if curposh ~= 0 or curpos > memsize then
        maxpos = curpos - memsize
        if maxpos > curpos then
            maxposh = curposh - 1
        else
            maxposh = curposh
        end
    else
        maxpos = 0
        maxposh = 0
    end
    for j = 0, lr + colsp do aboard[j] = board[j] end
    while sourceh > maxposh or (sourceh == maxposh and source >= maxpos) do
        d = d-1
        if d == 0 then
            print("Success! (solved in "..#board_states.." moves)")
            table.insert(board_states, 1, start_board)
            return board_states
        end
        
        print(fmt("\n%d:", d))
        k = source & (memsize - 1)
        unpack(aboard, apiece, aplace, pos, k + 2)
        print_board(aboard, apiece, acell)
        
        table.insert(board_states, 1, get_board(aboard, apiece, acell))
        
        if source < pos[k + 1] then sourceh = sourceh-1 end
        source = source - pos[k + 1]
    end

    warning(fmt("(Unfortunately I've forgotten how to get to level %d,\n"..
                "so I'll have to reconstruct that part.\nPlease bear with me.)", d))
    for j = 0, hashsize-1 do
        hash[j] = 0
        hashh[j] = 0
    end
    unpack(board, piece, place, start, 0)
    
    simple_goal = false
    goto restart
end
