--[[
A Lua application for creating and solving sliding-block puzzles.
By Andrew Trevorrow (andrew@trevorrow.com), August 2020.
--]]

local glu = glu()
local cv = canvas()
local gp = require "gplus"
local cp = require "cplus"
local fmt = string.format

require "KnuthSolver"   -- implements Donald Knuth's solving algorithm

local cvwd, cvht = 850, 600     -- initial canvas dimensions
local minwd, minht = 670, 450   -- minimum canvas dimensions
local topgap = 90               -- vertical space for buttons
local puzzlename = "untitled"   -- current name of puzzle
local maxsize = 10              -- maximum puzzle size
local minsize = 2               -- minimum puzzle size
local numrows, numcols = 5, 4   -- initial puzzle size
local startboard = {}           -- start board (has numrows x numcols cells)
local finalboard = {}           -- final board (ditto)
local maxblocks = 15            -- maximum number of distinct blocks (1 to f)
local blockoffsets = {}         -- cell offsets for each distinct block
local blocklabels = {}          -- labels for each distinct block
local blockcolors = {}          -- colors for each distinct block
local selected = {}             -- selected blocks (only in start board)
local obstructed = 666          -- an obstructed board cell
local style = 5                 -- move style used by knuth_solver (0 to 5)
local solving = false           -- currently solving puzzle?
local fastmoves = false         -- show solution quickly?
local playsounds = true         -- play various sounds?
local volume = 0.2              -- sound level (0.0 to 1.0)
local simple_finish = false     -- true if finish has fewer blocks than start

-- editing:
local editmode = false          -- currently editing puzzle?
local drawstate = 1             -- 0 for empty, 1 for block, else obstructed
local clickedboard              -- which board was ctrl/right-clicked
local clickedrow, clickedcol    -- which cell was ctrl/right-clicked

-- for undo/redo:
local undomove = {}     -- stack of moves that can be undone
local redomove = {}     -- stack of moves that can be redone
local undoedit = {}     -- stack of edits that can be undone
local redoedit = {}     -- stack of edits that can be redone

-- pixel values set by SetBoardLocations:
local cellsize      -- size of cell containing a 1x1 block
local blocksize     -- size of a 1x1 block
local boardwd       -- width of each board
local boardht       -- height of each board
local xs, ys        -- top left corner of startboard
local xf, yf        -- top left corner of finalboard
local startrect     -- bounding box of startboard
local finalrect     -- bounding box of finalboard

-- various colors:
local bg_color = {90,90,90,255}         -- for viewport *and* canvas background
local border_color = cp.black           -- for borders and obstructed cells
local block_color = {230,200,140,255}   -- for plain blocks
local empty_color = {150,150,150,255}   -- for empty cells
local grid_color = {110,110,110,255}    -- for grid lines

-- create SlidingBlocks folder inside user-specific data directory:
local pathsep = glu.getdir("app"):sub(-1)
local datadir = glu.getdir("data").."SlidingBlocks"..pathsep
glu.makedir(datadir)

-- some puzzles are supplied in puzzdir:
local puzzdir = glu.getdir("current").."puzzles"..pathsep
local lastpuzzle = puzzdir.."Red_Donkey.txt"

local initdir = datadir     -- initial directory for loading/saving puzzles
local recentfiles = {}      -- an array with the most recently loaded files
local maxrecent = 15        -- maximum number of recently loaded files

-- user settings are stored in this file:
local settingsfile = datadir.."SlidingBlocks.prefs"

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

function ReadSettings()
    local f = io.open(settingsfile, "r")
    if f then
        while true do
            -- look for keyword=value lines created by WriteSettings
            local line = f:read("*l")
            if not line then break end
            local keyword, value = line:match("([^=]+)=(.*)")
            if not value then -- ignore keyword
            elseif keyword == "cvwd" then cvwd = tonumber(value) or minwd
            elseif keyword == "cvht" then cvht = tonumber(value) or minht
            elseif keyword == "numrows" then numrows = tonumber(value) or 5
            elseif keyword == "numcols" then numcols = tonumber(value) or 4
            elseif keyword == "style" then style = tonumber(value) or 5
            elseif keyword == "fastmoves" then fastmoves = tostring(value) == "true"
            elseif keyword == "playsounds" then playsounds = tostring(value) == "true"
            elseif keyword == "volume" then volume = tonumber(value) or 0.2
            elseif keyword == "initdir" then initdir = value
            elseif keyword == "lastpuzzle" then lastpuzzle = value
            elseif keyword == "recentfile" then
                -- only add file if it can be opened
                local tempfile = io.open(value, "r")
                if tempfile then
                    recentfiles[#recentfiles+1] = value
                    tempfile:close()
                end
            end
        end
        f:close()
    end
    -- do some sanity checks
    if cvwd < minwd then cvwd = minwd end
    if cvht < minht then cvht = minht end
    if numrows < minsize then numrows = minsize end
    if numcols < minsize then numcols = minsize end
    if numrows > maxsize then numrows = maxsize end
    if numcols > maxsize then numcols = maxsize end
    if style < 0 then style = 0 end
    if style > 5 then style = 5 end
    if volume < 0.0 then volume = 0.0 end
    if volume > 1.0 then volume = 1.0 end
end

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

function WriteSettings()
    local f = io.open(settingsfile, "w")
    if f then
        -- keywords must match those in ReadSettings, but order doesn't matter
        f:write("cvwd=", tostring(cvwd), "\n")
        f:write("cvht=", tostring(cvht), "\n")
        f:write("numrows=", tostring(numrows), "\n")
        f:write("numcols=", tostring(numcols), "\n")
        f:write("style=", tostring(style), "\n")
        f:write("fastmoves=", tostring(fastmoves), "\n")
        f:write("playsounds=", tostring(playsounds), "\n")
        f:write("volume=", tostring(volume), "\n")
        f:write("initdir=", initdir, "\n")
        f:write("lastpuzzle=", lastpuzzle, "\n")
        for i = 1, math.min(maxrecent, #recentfiles) do
            f:write("recentfile=", recentfiles[i], "\n")
        end
        f:close()
    end
end

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

local exit_button
local help_button
local new_button
local load_button
local save_button
local undo_button
local redo_button
local undoall_button
local redoall_button
local solve_button
local edit_checkbox
local block_button
local empty_button
local obstr_button

function CreateButtons()
    cp.buttonrgba = {0,100,255,255}
    cp.textshadowx = 2
    cp.textshadowy = 2

    cp.buttonwd = 60
    exit_button = cp.button("Exit", glu.exit)
    exit_button.setbackcolor(cp.red)
    help_button = cp.button("Help", ShowHelp)

    cp.buttonwd = 30
    undo_button = cp.button("<", Undo, {true, true}) -- call Refresh and play sound
    redo_button = cp.button(">", Redo, {true, true}) -- ditto
    undoall_button = cp.button("|<", UndoAll)
    redoall_button = cp.button(">|", RedoAll)
    
    if glu.os() == "Windows" then
        undo_button.yoffset = -1
        redo_button.yoffset = -1
        undoall_button.yoffset = -1
        redoall_button.yoffset = -1
    end

    cp.buttonwd = 70
    new_button = cp.button("New...", NewPuzzle)
    load_button = cp.button("Load...", LoadPuzzle)
    save_button = cp.button("Save...", SavePuzzle)
    solve_button = cp.button("Solve", SolvePuzzle)

    cp.buttonwd = 22
    block_button = cp.button(" ", SetDrawState, {1})
    empty_button = cp.button(" ", SetDrawState, {0})
    obstr_button = cp.button(" ", SetDrawState, {obstructed})
    block_button.ht = 22
    empty_button.ht = 22
    obstr_button.ht = 22
    block_button.radius = 0
    empty_button.radius = 0
    obstr_button.radius = 0
    block_button.setbackcolor(block_color)
    empty_button.setbackcolor(empty_color)
    obstr_button.setbackcolor(border_color)

    -- add a couple of spaces to label so it's easier to click
    edit_checkbox = cp.checkbox("Edit  ", ToggleEditMode)
    edit_checkbox.settextshadow(0, 0)
    edit_checkbox.setlabelcolor(cp.white)
    edit_checkbox.radius = 3
end

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

local style_popup, style_rect
local puzzles_popup, puzzles_rect
local recent_popup, recent_rect
local options_popup, options_rect
local edit_popup

function CreatePopUpMenus()
    cp.menubg = cp.buttonrgba
    cp.menufont = "default-bold"
    cp.menufontsize = 10

    style_popup = cp.popupmenu()
    style_popup.settextshadow(0, 0)
    for i = 0, 5 do
        style_popup.additem("Style "..i, SetStyle, {i})
    end
    style_popup.additem("Help...", ShowStyleHelp)

    puzzles_popup = cp.popupmenu()
    puzzles_popup.rightgap = 0 -- no tick/radio mark
    puzzles_popup.settextshadow(0, 0)
    -- append supplied puzzles
    local files = glu.getfiles(puzzdir)
    table.sort(files)
    for _,filename in ipairs(files) do
        if #filename > 4 and filename:sub(-4) == ".txt" then
            puzzles_popup.additem(filename:sub(1,-5), LoadPuzzle, {puzzdir..filename})
        end
    end

    recent_popup = cp.popupmenu()
    recent_popup.rightgap = 0 -- no tick/radio mark
    recent_popup.settextshadow(0, 0)
    -- items are added in ClickInRecent
    
    options_popup = cp.popupmenu()
    options_popup.settextshadow(0, 0)
    options_popup.additem("Fast Solution", ToggleFastMoves)
    options_popup.additem("Play Sounds", ToggleSounds)
    options_popup.additem("Set Volume...", SetVolume)

    edit_popup = cp.popupmenu()
    edit_popup.settextshadow(0, 0)
    edit_popup.rightgap = 0 -- no tick/radio mark
    edit_popup.additem("Number Every Block", NumberEveryBlock)
    edit_popup.additem("Number Matching Blocks", NumberMatchingBlocks)
    edit_popup.additem("Change Label in This Block...", ChangeLabel)
    edit_popup.additem("Change Label in Matching Blocks...", ChangeMatchingLabels)
    edit_popup.additem("Remove All Labels", RemoveAllLabels)
    edit_popup.additem("---", nil)
    edit_popup.additem("Color Every Block", ColorEveryBlock)
    edit_popup.additem("Color Matching Blocks", ColorMatchingBlocks)
    edit_popup.additem("Change Color of This Block...", ChangeColor)
    edit_popup.additem("Change Color of Matching Blocks...", ChangeMatchingColors)
    edit_popup.additem("Remove All Colors", RemoveAllColors)
    edit_popup.additem("---", nil)
    edit_popup.additem("Delete This Block", DeleteBlock)
    edit_popup.additem("Delete Matching Blocks", DeleteMatchingBlocks)
    edit_popup.additem("---", nil)
    edit_popup.additem("Copy Start to Finish", DuplicateStart)
    edit_popup.additem("Clear Board", ClearBoard)
end

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

function DrawBackground()
    cv.blend(0)
    cv.rgba(bg_color)
    cv.fill()

    local hgap = 10
    local totalwd = 2*60 + 4*30 + 4*70 + 12*hgap
    local x = (cvwd - totalwd) // 2
    local y = 20
    local thin = boardwd < 160

    solve_button.enable(not (solving or editmode))
    new_button.enable(not solving)
    load_button.enable(not solving)
    save_button.enable(not (solving or editmode))
    if editmode then
        undo_button.enable(#undoedit > 0 and not solving)
        redo_button.enable(#redoedit > 0 and not solving)
        undoall_button.enable(#undoedit > 0 and not solving)
        redoall_button.enable(#redoedit > 0 and not solving)
    else
        undo_button.enable(#undomove > 0 and not solving)
        redo_button.enable(#redomove > 0 and not solving)
        undoall_button.enable(#undomove > 0 and not solving)
        redoall_button.enable(#redomove > 0 and not solving)
    end

    solve_button.show(x, y);   x = x + solve_button.wd   + hgap*2
    undoall_button.show(x, y); x = x + undoall_button.wd + hgap
    undo_button.show(x, y);    x = x + undo_button.wd    + hgap
    redo_button.show(x, y);    x = x + redo_button.wd    + hgap
    redoall_button.show(x, y); x = x + redoall_button.wd + hgap*2
    new_button.show(x, y);     x = x + new_button.wd     + hgap
    load_button.show(x, y);    x = x + load_button.wd    + hgap
    save_button.show(x, y);    x = x + save_button.wd    + hgap*2
    help_button.show(x, y);    x = x + help_button.wd    + hgap
    exit_button.show(x, y)

    edit_checkbox.enable(not solving)
    edit_checkbox.hide()
    if thin then
        edit_checkbox.show(xs-edit_checkbox.wd-20, ys-edit_checkbox.ht-8, editmode)
    else
        edit_checkbox.show(xs, ys-edit_checkbox.ht-8, editmode)
    end
    
    local buttht = solve_button.ht
    local textwd, textht, rectwd

    cv.blend(2)
    cv.font("default-bold", 10)
    cv.rgba(cp.white)
    
    local function draw_triangle(r)
        local x = r.x+r.wd - 14
        local y = r.y+6
        cv.blend(0)
        for i = 8, 0, -2 do
            cv.line(x, y, x+i, y)
            x = x+1
            y = y+1
        end
        cv.blend(2)
    end

    block_button.hide()
    empty_button.hide()
    obstr_button.hide()
    
    if editmode then
        -- show editing buttons
        block_button.border = 0
        empty_button.border = 0
        obstr_button.border = 0
        if drawstate == 0 then
            empty_button.border = 2
        elseif drawstate == 1 then
            block_button.border = 2
        else
            obstr_button.border = 2
        end
        local midx = cvwd//2
        local bsize = block_button.wd
        local half = bsize//2
        block_button.show(midx-half-bsize-10, ys-bsize-10)
        empty_button.show(midx-half, ys-bsize-10)
        obstr_button.show(midx+half+10, ys-bsize-10)
    end

    textwd, textht = cv.text("t", "START")
    if thin and editmode then
        cv.paste("t", xs-5, ys-textht-10)
    else
        cv.paste("t", xs+(boardwd-textwd)//2, ys-textht-10)
    end
    
    textwd, textht = cv.text("t", "FINISH")
    if thin and editmode then
        cv.paste("t", xf+boardwd-textwd+5, yf-textht-10)
    else
        cv.paste("t", xf+(boardwd-textwd)//2, yf-textht-10)
    end
    
    local vgap = 12
    local yoff = 0
    if glu.os() == "Windows" then yoff = -1 end

    if editmode then
        if #undoedit > 0 then
            textwd, textht = cv.text("t", "Undo")
            cv.paste("t", undoall_button.x+(undo_button.wd*2+10-textwd)//2, undo_button.y+undo_button.ht+vgap)
        end
        if #redoedit > 0 then
            textwd, textht = cv.text("t", "Redo")
            cv.paste("t", redo_button.x+(redo_button.wd*2+10-textwd)//2, undo_button.y+undo_button.ht+vgap)
        end
    else
        textwd, textht = cv.text("t", "Moves: "..#undomove)
        cv.paste("t", undo_button.x+5, undo_button.y+undo_button.ht+vgap)
    end
    
    textwd, textht = cv.text("t", "Style "..style)
    rectwd = solve_button.wd+2
    style_rect = {x=solve_button.x+(solve_button.wd-rectwd)//2, y=solve_button.y+buttht+vgap,
                  wd=rectwd, ht=textht}
    cp.round_rect(style_rect.x, style_rect.y, style_rect.wd, style_rect.ht, 3, 0, cp.buttonrgba)
    cv.paste("t", style_rect.x+10, style_rect.y+yoff)
    draw_triangle(style_rect)

    textwd, textht = cv.text("t", "Puzzles")
    rectwd = 10+textwd+20
    puzzles_rect = {x=load_button.x+load_button.wd//2-rectwd-5, y=load_button.y+buttht+vgap,
                    wd=rectwd, ht=textht}
    cp.round_rect(puzzles_rect.x, puzzles_rect.y, puzzles_rect.wd, puzzles_rect.ht, 3, 0, cp.buttonrgba)
    cv.paste("t", puzzles_rect.x+10, puzzles_rect.y+yoff)
    draw_triangle(puzzles_rect)

    textwd, textht = cv.text("t", "Recent")
    rectwd = 10+textwd+20
    recent_rect = {x=load_button.x+load_button.wd//2+5, y=load_button.y+buttht+vgap,
                   wd=rectwd, ht=textht}
    cp.round_rect(recent_rect.x, recent_rect.y, recent_rect.wd, recent_rect.ht, 3, 0, cp.buttonrgba)
    cv.paste("t", recent_rect.x+10, recent_rect.y+yoff)
    draw_triangle(recent_rect)

    textwd, textht = cv.text("t", "Options")
    rectwd = 10+textwd+20
    options_rect = {x=help_button.x+(help_button.wd-rectwd)//2, y=help_button.y+buttht+vgap,
                    wd=rectwd, ht=textht}
    cp.round_rect(options_rect.x, options_rect.y, options_rect.wd, options_rect.ht, 3, 0, cp.buttonrgba)
    cv.paste("t", options_rect.x+10, options_rect.y+yoff)
    draw_triangle(options_rect)
end

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

function PointInRect(x, y, r)
    if x < r.x or x > r.x+r.wd-1 then return false end
    if y < r.y or y > r.y+r.ht-1 then return false end
    return true
end

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

function SetBoardLocations()
    -- set cellsize, blocksize, etc depending on numrows, numcols
    -- and current canvas dimensions
    
    local hgap = 50     -- horizontal space between boards
    local hborder = 40  -- minimum horizontal border at left and right edges
    local vborder = 30  -- minimum vertical border above and below boards
    
    local cellwd = (cvwd - hgap - 2*hborder) // (2*numcols)
    local cellht = (cvht - topgap - 2*vborder) // numrows
    cellsize = math.min(cellwd, cellht)
    blocksize = cellsize - 2
    boardwd = numcols * cellsize
    boardht = numrows * cellsize
    
    xs = (cvwd // 2) - (hgap // 2) - boardwd
    xf = (cvwd // 2) + (hgap // 2)
    
    ys = topgap + (cvht - topgap - boardht) // 2
    yf = ys

    startrect = {x=xs, y=ys, wd=boardwd, ht=boardht}
    finalrect = {x=xf, y=yf, wd=boardwd, ht=boardht}
end

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

function RestoreNegatedCells(board)
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = board[r][c]
            if cell < 0 then board[r][c] = -cell end
        end
    end
end

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

function DrawBlock(board, r, c, cell, x, y)
    -- draw the given block where the top left cell in the block
    -- is at board[r][c] and x,y is the top left corner of the board
    local max = math.max

    local function neighbor(row, col, offsets)
        -- return true if {row,col} exists in offsets
        for _,v in ipairs(offsets) do
            if row == v[1] and col == v[2] then return true end
        end
        return false
    end

    local color = blockcolors[cell] or block_color
    if board == startboard and selected[r..","..c] then
        cv.rgba(max(0,color[1]-90), max(0,color[2]-90), max(0,color[3]-90), 255)
    else
        cv.rgba(color)
    end
    cv.blend(0)
    cv.fill(x+(c-1)*cellsize+1, y+(r-1)*cellsize+1, blocksize, blocksize)

    if #blockoffsets[cell] > 1 then
        -- draw other cells in this block and connect joined edges
        local offsets = blockoffsets[cell]
        for i = 2, #offsets do
            local ro = offsets[i][1]
            local co = offsets[i][2]
            local rr = r + ro
            local cc = c + co
            if neighbor(ro-1, co, offsets) and board[rr-1][cc] == cell then
                -- join rr-1,cc and rr,cc
                cv.fill(x+(cc-1)*cellsize+1, y+(rr-1)*cellsize-1, blocksize, 2)
            end
            if neighbor(ro+1, co, offsets) and board[rr+1][cc] == cell then
                -- join rr+1,cc and rr,cc
                cv.fill(x+(cc-1)*cellsize+1, y+rr*cellsize-1, blocksize, 2)
            end
            if neighbor(ro, co-1, offsets) and board[rr][cc-1] == cell then
                -- join rr,cc-1 and rr,cc
                cv.fill(x+(cc-1)*cellsize-1, y+(rr-1)*cellsize+1, 2, blocksize)
            end
            if neighbor(ro, co+1, offsets) and board[rr][cc+1] == cell then
                -- join rr,cc+1 and rr,cc
                cv.fill(x+cc*cellsize-1, y+(rr-1)*cellsize+1, 2, blocksize)
            end
            -- check if cell is bottom right corner of 4 cells connected in a square
            -- (note that the top left cell could be +ve or -ve)
            if neighbor(ro-1, co-1, offsets) and math.abs(board[rr-1][cc-1]) == cell and
               neighbor(ro-1, co  , offsets) and board[rr-1][cc] == -cell and
               neighbor(ro  , co-1, offsets) and board[rr][cc-1] == -cell then
                -- fill hole in the middle of the 4 cells
                cv.fill(x+(cc-1)*cellsize-1, y+(rr-1)*cellsize-1, 2, 2)
            end
            -- draw cell and negate it to avoid seeing it again
            cv.fill(x+(cc-1)*cellsize+1, y+(rr-1)*cellsize+1, blocksize, blocksize)
            board[rr][cc] = -cell
        end
    end

    if blocklabels[cell] then
        -- draw label in top left corner of cell
        if board == startboard and selected[r..","..c] then
            cv.rgba(cp.white)
        else
            cv.rgba(cp.black)
        end
        cv.font("default",10)
        cv.blend(2)
        cv.text("t", blocklabels[cell])
        cv.paste("t", x+(c-1)*cellsize+6, y+(r-1)*cellsize+4)
        cv.blend(0)
    end
end

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

function DrawBoard(board, x, y)
    cv.blend(0)
    cv.rgba(empty_color)
    cv.fill(x, y, boardwd, boardht)
    
    -- draw grid lines
    cv.rgba(grid_color)
    for r = 0, numrows do
        cv.fill(x, y+r*cellsize-1, boardwd, 2)
    end
    for c = 0, numcols do
        cv.fill(x+c*cellsize-1, y, 2, boardht)
    end

    -- draw outer border
    cv.rgba(border_color)
    cp.round_rect(x-5, y-5, boardwd+10, boardht+10, 0, 5, {})
    
    -- draw cells
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = board[r][c]
            if cell == obstructed then
                cv.rgba(border_color)
                cv.fill(x+(c-1)*cellsize, y+(r-1)*cellsize, cellsize, cellsize)
            elseif cell > 0 then
                DrawBlock(board, r, c, cell, x, y)
                -- this negates cells after the 1st
            end
        end
    end
    RestoreNegatedCells(board)
end

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

function Refresh()
    glu.check(false)    -- avoid partial updates of canvas
    DrawBackground()

    DrawBoard(startboard, xs, ys)
    DrawBoard(finalboard, xf, yf)

    cv.update()         -- canvas covers viewport
    glu.check(true)     -- restore event checking
end

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

function GetBlockOffsets(val, rows, cols)
    -- val is a string representing a block (eg. "001/111/1")
    -- so check it is a connected block that fits within the given board;
    -- if so then return an array of {row,col} offsets relative to
    -- the topmost and leftmost non-zero cell in the block
    local offsets = { {0,0} }
    local numones = 0
    local r, c = 1, 1
    local r1, c1

    for i = 1, #val do
        local ch = val:sub(i,i)
        if ch == '1' then
            if c > cols then
                glu.warn("Block has too many columns: "..val)
                return
            end
            numones = numones+1
            if numones == 1 then
                -- offsets is { {0,0} }
                r1 = r
                c1 = c
            else
                offsets[#offsets+1] = {r-r1, c-c1}
            end
            c = c+1
        elseif ch == '0' then
            c = c+1
        else
            -- ch is '/' so add another row
            if r == rows then
                glu.warn("Block has too many rows: "..val)
                return
            end
            r = r+1
            c = 1
        end
    end

    if numones == 0 then
        glu.warn("Block is empty: "..val)
        return
    elseif numones == 1 then
        -- this block only occupies 1 cell (offsets is { {0,0} })
        return offsets
    else
        -- check that multiple 1s are orthogonally connected
        -- (Knuth's solver doesn't require this but it simplifies this script)
        local function neighbor(r,c)
            -- return 1 if {r,c} exists in offsets, otherwise 0
            for _,v in ipairs(offsets) do
                if r == v[1] and c == v[2] then return 1 end
            end
            return 0
        end
        for _,v in ipairs(offsets) do
            local r, c = v[1], v[2]
            if neighbor(r+1, c) + neighbor(r, c+1) +
               neighbor(r-1, c) + neighbor(r, c-1) == 0 then
                glu.warn("Block is not connected: "..val)
                return
            end
        end
        
        return offsets
    end
end

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

function CreateBoard(position, boff, rows, cols)
    -- parse a position string like "1xx200000000033" and return a 2D board array
    -- filled with rows x cols cells, along with the total number of blocks
    local board = {}
    local tblocks = 0
    
    for r = 0, rows+1 do
        board[r] = {}
        for c = 0, cols+1 do
            if r < 1 or r > rows or c < 1 or c > cols then
                -- invisible boundary has obstructed cells
                board[r][c] = obstructed
            else
                -- mark inner cells as available
                board[r][c] = -1
            end
        end
    end
    
    local used = {}
    local r = 1
    local c = 1
    for i = 1, #position do
        local ch = position:sub(i,i)
        if ch == '0' then
            board[r][c] = 0
        elseif ch == 'x' then
            board[r][c] = obstructed
        elseif (ch >= '1' and ch <= '9') or (ch >= 'a' and ch <= 'f') then
            local bnum = tonumber(ch,16)
            if boff[bnum] then
                used[bnum] = true
                tblocks = tblocks+1
                -- use offsets to add this block to the board
                for _,v in ipairs(boff[bnum]) do
                    local rr = r + v[1]
                    local cc = c + v[2]
                    if rr < 1 or rr > rows or cc < 1 or cc > cols then
                        glu.warn(fmt("Block %s is outside board:\n%s", ch, position))
                        return
                    end
                    if board[rr][cc] ~= -1 then
                        glu.warn(fmt("Block %s overwrites cell in position:\n%s", ch, position))
                        return
                    end
                    board[rr][cc] = bnum
                end
            else
                glu.warn(fmt("Unknown block (%s) in position:\n%s", ch, position))
                return
            end
        else
            glu.warn(fmt("Unexpected character (%s) in position:\n%s", ch, position))
            return
        end
        if i < #position then
            -- find next available cell
            repeat
                c = c+1
                if c > cols then
                    c = 1
                    r = r+1
                    if r > rows then
                        glu.warn("The position is too big for the specified board:\n"..position)
                        return
                    end
                end
            until board[r][c] == -1
        end
    end
    
    -- count the blocks used
    local ucount = 0
    for _,_ in pairs(used) do ucount = ucount+1 end
    
    -- set any remaining available cells to 0
    for r = 1, rows do
        for c = 1, cols do
            if board[r][c] == -1 then board[r][c] = 0 end
        end
    end
    
    return board, tblocks, ucount
end

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

function LoadPuzzle(filepath)
    if filepath == nil then
        -- prompt for puzzle file
        filepath = glu.open("Load a puzzle", "Puzzle (*.txt)|*.txt", initdir)
        if #filepath == 0 then return end
        -- update initdir by stripping off the file name
        initdir = filepath:gsub("[^"..pathsep.."]+$","")
    end

    local f <close> = io.open(filepath, "r")
    if not f then
        glu.warn("Failed to open file:\n"..filepath)
        return
    end

    local name = filepath:match("([^"..pathsep.."]+)%.txt$")
    if name == nil or #name == 0 then name = "unknown" end

    --[[
    Puzzle files must start with lines in Knuth's format; eg:
        
        5 x 5 (silly example)
        1 = 111/01
        2 = 101/111
        3 = 1
        1xx200000000033
        000xx00033001002
        
    These can be followed by optional lines with block labels and colors:
    
        autolabel           label all blocks with their corresponding number
        label 1 = xxx       set label of block 1 to "xxx"
        color 2 = 255,0,0   set color of block 2 to red
    
    Then comes optional lines with undo/redo info:
    
        undo = 1xx00/.../   rows*(cols+1) characters encoding the board state
        ...
        redo = 1xx32/.../   ditto
        ...
    --]]

    local line = f:read("*l")
    if not line then
        glu.warn("Failed to read first line!")
        return
    end

    local rows, cols = line:match("^(%d+) x (%d+)")
    rows = tonumber(rows)
    cols = tonumber(cols)
    if rows == nil or cols == nil then
        glu.warn("First line must specify rows x columns!\n"..line)
        return
    end
    if rows < minsize or cols < minsize or rows > maxsize or cols > maxsize then
        glu.warn(fmt("Rows and columns must be from %d to %d!", minsize, maxsize))
        return
    end

    local boff = {}
    while true do
        line = f:read("*l")
        if not line then
            glu.warn("File ended unexpectedly!")
            return
        end
        local n, val = line:match("^([1-9a-f]) = ([10/]+)")
        if n == nil or val == nil then
            break
        else
            -- convert val into an array of offsets
            local offsets = GetBlockOffsets(val, rows, cols)
            if not offsets then
                return -- an error was detected
            end
            boff[tonumber(n,16)] = offsets
        end
    end

    -- count the number of distinct blocks
    local dcount = 0
    for _,_ in pairs(boff) do dcount = dcount+1 end

    -- line should have start position
    local start = line

    -- get final position
    local final = f:read("*l")
    if not final then
        glu.warn("Failed to read final position!")
        return
    end

    -- validate start and final positions
    local sboard, scount, sused = CreateBoard(start, boff, rows, cols)
    if not sboard then
        return -- error detected
    end
    if sused ~= dcount then
        glu.warn("The start position does not use all the blocks:\n"..position)
        return
    end
    -- the final position doesn't have to use all the blocks
    local fboard, fcount = CreateBoard(final, boff, rows, cols)
    if not fboard then
        return -- error detected
    end
    if scount < fcount then
        glu.warn("The start position uses fewer blocks than the final position!")
        return
    end

    -- get optional labels, colors, and undo/redo info
    local labels = {}
    local colors = {}
    local undo = {}
    local redo = {}
    while true do
        line = f:read("*l")
        if not line then break end
        if line == "autolabel" then
            for k,_ in pairs(boff) do
                labels[k] = tostring(k)
            end
        elseif line:find("^label ") then
            local n, label = line:match("^label ([1-9a-f]) = (.+)")
            if n and label then
                n = tonumber(n,16)
                if not boff[n] then
                    glu.warn("Label is for an unknown block:\n"..line)
                    return
                end
                labels[n] = label
            end
        elseif line:find("^color ") then
            local n, r, g, b = line:match("^color ([1-9a-f]) = (%d+),(%d+),(%d+)")
            if n and r and g and b then
                n = tonumber(n,16)
                if not boff[n] then
                    glu.warn("Color is for an unknown block:\n"..line)
                    return
                end
                r = tonumber(r)
                g = tonumber(g)
                b = tonumber(b)
                if r >= 0 and r <= 255 and
                   g >= 0 and g <= 255 and
                   b >= 0 and b <= 255 then
                    colors[n] = {r,g,b,255}
                else
                    glu.warn("Bad color value (must be 0 to 255):\n"..line)
                    return
                end
            end
        elseif line:find("^undo = .") then
            local undodata = line:match("^undo = ([0-9a-fx/]+)")
            if not undodata then
                glu.warn("Bad undo data:\n"..line)
                return
            end
            if #undodata ~= rows*(cols+1) then
                glu.warn("Bad undo data (wrong length):\n"..line)
                return
            end
            undo[#undo+1] = undodata:gsub("/","\n")
        elseif line:find("^redo = ") then
            local redodata = line:match("^redo = ([0-9a-fx/]+)")
            if not redodata then
                glu.warn("Bad redo data:\n"..line)
                return
            end
            if #redodata ~= rows*(cols+1) then
                glu.warn("Bad redo data (wrong length):\n"..line)
                return
            end
            redo[#redo+1] = redodata:gsub("/","\n")
        end
    end

    -- we only get here if the given file specified a valid puzzle
    glu.settitle("Sliding Blocks ["..name.."]")
    puzzlename = name
    numrows = rows
    numcols = cols
    startboard = sboard
    finalboard = fboard
    blockoffsets = boff
    blockcolors = colors
    blocklabels = labels
    selected = {}
    simple_finish = scount > fcount
    
    undomove = undo
    redomove = redo
    
    table.insert(recentfiles, 1, filepath)
    -- remove any other occurrence of filepath
    for i = 2, #recentfiles do
        if recentfiles[i] == filepath then
            table.remove(recentfiles, i)
        end
    end
    
    lastpuzzle = filepath
    editmode = false
    undoedit = {}
    redoedit = {}

    SetBoardLocations()
    Refresh()
    return true
end

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

function NewPuzzle(rows, cols)
    if rows == nil or cols == nil then
        -- prompt for puzzle dimensions
        local answer = glu.getstring("Enter the puzzle size as rows x columns:", numrows.."x"..numcols)
        if answer == nil then
            return
        end
        rows, cols = answer:match("(%d+)[ x]+(%d+)")
        rows = tonumber(rows)
        cols = tonumber(cols)
        if rows == nil or cols == nil or rows < minsize or cols < minsize or
                                         rows > maxsize or cols > maxsize then
            glu.warn(fmt("Rows and columns must be numbers from %d to %d!", minsize, maxsize))
            return
        end
    end
    
    lastpuzzle = ""
    puzzlename = "untitled"
    glu.settitle("Sliding Blocks ["..puzzlename.."]")
    numrows = rows
    numcols = cols
    blockoffsets = {}
    blocklabels = {}
    blockcolors = {}
    startboard = CreateBoard("0", {}, numrows, numcols) -- empty board
    finalboard = CreateBoard("0", {}, numrows, numcols) -- ditto
    selected = {}
    simple_finish = false
    
    editmode = true
    drawstate = 1
    undoedit = {}
    redoedit = {}
    undomove = {}
    redomove = {}
    
    SetBoardLocations()
    Refresh()
end

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

function SavePuzzle()
    -- prompt for file name and location
    local filepath = glu.save("Save current puzzle", "Puzzle (*.txt)|*.txt",
                              initdir, puzzlename..".txt")
    if #filepath == 0 then return end

    -- update initdir by stripping off the file name
    initdir = filepath:gsub("[^"..pathsep.."]+$","")

    local f = io.open(filepath, "w")
    if not f then
        glu.warn("Failed to create puzzle file!")
        return
    end
    
    -- see LoadPuzzle for file format    
    local data = GetPuzzleData()
    f:write(data)
    for k,label in pairs(blocklabels) do
        f:write(fmt("label %x = %s\n", k, label))
    end
    for k,rgba in pairs(blockcolors) do
        f:write(fmt("color %x = %d,%d,%d\n", k, rgba[1], rgba[2], rgba[3]))
    end
    for i = 1, #undomove do
        f:write(fmt("undo = %s\n", undomove[i]:gsub("\n","/")))
    end
    for i = 1, #redomove do
        f:write(fmt("redo = %s\n", redomove[i]:gsub("\n","/")))
    end
    
    f:close()
    
    puzzlename = filepath:match("([^"..pathsep.."]+)%.txt$")
    if puzzlename == nil then
        puzzlename = filepath:match("([^"..pathsep.."]+)$")
    end
    glu.settitle("Sliding Blocks ["..puzzlename.."]")
    
    lastpuzzle = filepath
    table.insert(recentfiles, 1, filepath)
    -- remove any other occurrence of filepath
    for i = 2, #recentfiles do
        if recentfiles[i] == filepath then
            table.remove(recentfiles, i)
        end
    end
end

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

function FlashBoards()
    cv.copy(xs, ys, boardwd, boardht, "board1")
    cv.copy(xf, yf, boardwd, boardht, "board2")
    
    cv.target("board1")
    cv.replace("*#-60 *#-60 *#-60 *#")
    cv.target("board2")
    cv.replace("*#-60 *#-60 *#-60 *#")
    cv.target()
    cv.paste("board1", xs, ys)
    cv.paste("board2", xf, yf)
    cv.update()
    glu.sleep(200)
    
    cv.delete("board1")
    cv.delete("board2")
    Refresh()
end

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

function GetKnuthBoard(board)
    -- return string representing given board in format required by knuth_solver
    local pos = ""
    
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = board[r][c]
            if cell >= 0 then
                if cell == 0 then
                    pos = pos..'0'
                elseif cell == obstructed then
                    pos = pos..'x'
                else
                    pos = pos..fmt("%x", cell)
                    -- negate other cells belonging to this block
                    local offsets = blockoffsets[cell]
                    for o = 2, #offsets do
                        local ro = offsets[o][1]
                        local co = offsets[o][2]
                        board[r+ro][c+co] = -cell
                    end
                end
            end
        end
    end
    RestoreNegatedCells(board)
    
    return pos.."\n"
end

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

function GetPuzzleData()
    -- create data string for current puzzle in format required by knuth_solver
    local data = fmt("%d x %d\n", numrows, numcols)
    for k,offsets in pairs(blockoffsets) do
        local shape = ""
        local minc, maxc = 0, 0
        for _,v in ipairs(offsets) do
            local r = v[1]
            local c = v[2]
            if c < minc then minc = c end
            if c > maxc then maxc = c end
        end
        local r = 0
        local c = minc
        for _,v in ipairs(offsets) do
            if v[1] > r then
                shape = shape..'/'
                r = v[1]
                c = minc
            end
            if v[2] > c then
                for i = 1, v[2]-c do shape = shape..'0' end
                c = v[2]+1
            else
                c = c+1
            end
            shape = shape..'1'
        end
        data = data..fmt("%x = %s\n", k, shape)
    end
    
    local spos = GetKnuthBoard(startboard)
    local fpos = GetKnuthBoard(finalboard)

    return data..spos..fpos
end

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

-- while searching for a solution we display a dialog box with progress info and a Cancel button

local cancel_button, progressx, progressy, progresswd

function CreateSearchDialog()
    cp.disable_all() -- prevent the existing buttons from being clicked

    cp.buttonwd = 0
    cancel_button = cp.button("Cancel", glu.exit)
    cancel_button.setborder(0)
    local buttht = cancel_button.ht

    -- save canvas in a clip and then darken everything
    cv.copy(0,0,0,0,"canvas")
    cv.replace("*#-60 *#-60 *#-60 *#")
    
    -- draw the dialog in middle of canvas
    cv.blend(0)
    cv.rgba(cp.black)
    cv.font("default-bold",12)
    local textwd, textht = cv.text("q",[[
Searching for the shortest solution.
This might take a while...]])
    local dialogwd, dialoght = textwd+40, textht+60+buttht+20
    local x = (cvwd - dialogwd)//2
    local y = (cvht - dialoght)//2
    cv.rgba(cp.gray)
    cp.round_rect(x+5, y+5, dialogwd, dialoght, 10, 0, {0,0,0,128}) -- shadow
    cp.round_rect(x, y, dialogwd, dialoght, 10, 1, cp.white)
    cancel_button.show(x+(dialogwd-cancel_button.wd)//2, y+dialoght-buttht-20)
    cv.blend(2)
    cv.paste("q", x+20, y+20)
    cv.delete("q")
    
    -- set position of text for UpdateSearchDialog
    progressx = x+20
    progressy = y+20+textht+5
    progresswd = dialogwd-21
    
    cv.update()
    glu.sleep(500)
end

function UpdateSearchDialog(progress)
    -- called periodically by knuth_solver
    cv.font("default",10)
    cv.rgba(cp.black)
    local textwd, textht = cv.text("p", progress)
    cv.rgba(cp.white)
    cv.blend(0)
    cv.fill(progressx, progressy, progresswd, textht)
    cv.blend(2)
    cv.paste("p", progressx, progressy)
    cv.delete("p")
    cv.update()
end

function DeleteSearchDialog()
    -- remove Cancel button
    cancel_button.hide()
    cancel_button = nil

    -- restore canvas
    cv.blend(0)
    cv.paste("canvas",0,0)
    cv.delete("canvas")
    
    cp.enable_all() -- restore the buttons that were disabled by cp.disable_all
    Refresh()
end

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

function GetBoardState(board)
    --[[
    return a string representing the given board using the same format
    as the strings returned by by knuth_solver; ie. for silly.txt:
        111xx
        21200
        22200
        00000
        33000
    --]]
    local state = ""
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = board[r][c]
            if cell <= maxblocks then
                state = state..fmt("%x",cell)
            else
                -- assume obstructed
                state = state.."x"
            end
        end
        state = state.."\n"
    end
    
    if board == startboard then
        -- to undo/redo moves we also need to append data for any selected blocks
        for rowcol,_ in pairs(selected) do
            state = state..rowcol.."\n"
        end
    end
    
    return state
end

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

function UpdateBoard(board, newpos, call_refresh, play_sound)
    -- update given board to show new position
    if play_sound and playsounds then
        cv.sound("play", "sounds/move.wav", volume)
    end
    
    local i = 0
    for r = 1, numrows do
        for c = 1, numcols do
            i = i+1
            local ch = newpos:sub(i,i)
            if ch == 'x' then
                board[r][c] = obstructed
            else
                -- ch is '0'..'9' or 'a'..'f'
                board[r][c] = tonumber(ch,16)
            end
        end
        i = i+1 -- skip "\n" or "/"
    end
    
    if board == startboard then
        selected = {}
        if #newpos > i then
            -- GetBoardState appended extra lines for selected blocks
            newpos = newpos:sub(i+1)
            for rowcol in string.gmatch(newpos, "(%d+,%d+)\n") do
                selected[rowcol] = true
            end
        end
    end
    
    if call_refresh then Refresh() end
    
    if solving and not fastmoves then
        for i = 1, 10 do
            glu.sleep(30)
            -- allow some events while showing solution
            local event = cp.process( glu.getevent() )
            if event:find("^key") then
                HandleKey(event)
            elseif event:find("^cclick") then
                -- check for click in options_rect
                local _, x, y, button, mods = gp.split(event)
                if button == "left" and mods == "none" then
                    ClickInOptions(tonumber(x), tonumber(y))
                end
            end
        end
    end
end

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

function PuzzleSolved()
    if simple_finish then
        -- finalboard has fewer blocks than startboard so check if all blocks
        -- in finalboard are in same positions in startboard
        for r = 1, numrows do
            for c = 1, numcols do
                local cell = finalboard[r][c]
                if cell > 0 and cell ~= obstructed then
                    if startboard[r][c] ~= cell then
                        return false
                    end
                    -- the cells are the same but they could belong to two different blocks
                    -- that are the same shape but in adjacent horizontal locations
                    local stop, sleft = FindTopLeftCell(startboard, r, c, cell)
                    local ftop, fleft = FindTopLeftCell(finalboard, r, c, cell)
                    if stop ~= ftop or sleft ~= fleft then
                        -- start cell is in an adjacent (but identical) block
                        return false
                    end
                end
            end
        end
    else
        -- puzzle is solved if startboard and finalboard are identical
        for r = 1, numrows do
            for c = 1, numcols do
                if startboard[r][c] ~= finalboard[r][c] then return false end
            end
        end
    end
    -- get here if solved
    return true
end

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

function SolvePuzzle()
    if next(blockoffsets) == nil then
        glu.warn("There are no blocks!")
        return
    end
    if PuzzleSolved() then
        -- silently indicate that the puzzle is already solved
        FlashBoards()
        return
    end
    
    -- create a temporary file with the required info for knuth_solver
    local tempfile = glu.getdir("temp").."puzzle.txt"
    local f = io.open(tempfile, "w")
    if not f then
        glu.warn("Failed to create temporary file!")
        return
    end
    f:write(GetPuzzleData())
    f:close()
    
    -- knuth_solver knows nothing about selected blocks so deselect them
    selected = {}
    
    -- disable most buttons
    solving = true
    Refresh()
    
    CreateSearchDialog()
    
    local soln
    local function solve()
        soln = knuth_solver(style, tempfile, UpdateSearchDialog)
    end

    -- call knuth_solver inside xpcall so we can detect if user cancels search
    local status, err = xpcall(solve, gp.trace)
    if err then
        glu.continue("")
        if err:find("^GLU: ABORT SCRIPT") then
            -- user hit escape key or Cancel button
        else
            glu.warn(err)
        end
    end
    
    DeleteSearchDialog()

    if soln == nil then
        -- an error occurred, or user cancelled search
    elseif #soln == 0 then
        local msg = "There is no solution!"
        if style < 3 then
            msg = msg.."\nTry using a style greater than 2."
        end
        glu.note(msg)
    else
        --[[
        soln is an array of strings representing all board positions from start to finish;
        for example, the positions for silly.txt are (using style 5):
            111xx       000xx       000xx
            21200       00000       00033
            22200  -->  00111  -->  00111
            00000       00212       00212
            33000       33222       00222
        --]]
        redomove = {}
        for i = 1, #soln-1 do
            -- remember this move
            undomove[#undomove+1] = soln[i]
            -- show the move needed to get from soln[i] to soln[i+1]
            -- (note that Refresh is called but only play sound if fastmoves is false)
            UpdateBoard(startboard, soln[i+1], true, not fastmoves)
        end
        if playsounds then cv.sound("play", "sounds/success.wav", volume) end
        FlashBoards()
    end
    
    -- enable buttons
    solving = false
    Refresh()
end

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

function Undo(call_refresh, play_sound)
    if solving then return end
    if editmode then
        -- undo edit
        if #undoedit > 0 then
            -- push current edit state onto redoedit
            redoedit[#redoedit+1] = GetEditState()
            -- pop old edit state off undoedit and restore it
            RestoreEditState(table.remove(undoedit))
            if call_refresh then Refresh() end
        end
    elseif #undomove > 0 then
        -- push current state of startboard onto redomove
        redomove[#redomove+1] = GetBoardState(startboard)
        -- pop old state off undomove and show it
        UpdateBoard(startboard, table.remove(undomove), call_refresh, play_sound)
    end
end

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

function Redo(call_refresh, play_sound)
    if solving then return end
    if editmode then
        -- redo edit
        if #redoedit > 0 then
            -- push current edit state onto undoedit
            undoedit[#undoedit+1] = GetEditState()
            -- pop new edit state off redoedit and restore it
            RestoreEditState(table.remove(redoedit))
            if call_refresh then Refresh() end
        end
    elseif #redomove > 0 then
        -- push current state of startboard onto undomove
        undomove[#undomove+1] = GetBoardState(startboard)
        -- pop new state off redomove and show it
        UpdateBoard(startboard, table.remove(redomove), call_refresh, play_sound)
    end
end

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

function UndoAll()
    if solving then return end
    -- undo all edits or all moves
    if editmode then
        -- undo all edits
        if #undoedit > 0 then
            repeat
                Undo(false, false) -- no Refresh, no sound
            until #undoedit == 0
            Refresh()
        end
    elseif #undomove > 0 then
        repeat
            Undo(false, false) -- no Refresh, no sound
        until #undomove == 0
        Refresh()
    end
end

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

function RedoAll()
    if solving then return end
    -- redo all edits or all moves
    if editmode then
        -- redo all edits
        if #redoedit > 0 then
            repeat
                Redo(false, false) -- no Refresh, no sound
            until #redoedit == 0
            Refresh()
        end
    elseif #redomove > 0 then
        -- redo all moves
        repeat
            Redo(false, false) -- no Refresh, no sound
        until #redomove == 0
        Refresh()
    end
end

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

function ShowHelp()
    local msg = [[
Keyboard commands:

Hit Z to undo a move/edit.
Hit shift-Z to redo a move/edit.
Hit enter to undo all moves/edits.
Hit shift-enter to redo all moves/edits.
Hit 0 to 5 to set the move style.
Hit F to toggle fast solution.
Hit P to toggle sound play.
Hit up/down arrows to change volume.
Hit H to see this help.
Hit escape to exit.

Shift-click to select a set of blocks that can
then be moved together (only needed to solve
some puzzles in a minimum number of moves).

When the Edit box is ticked:

Alt-click to copy a block and drag it
to a new location in either board.

Ctrl-click or right-click in either board to
get a pop-up menu with editing commands.]]
    if glu.os() == "Mac" then
        msg = msg:gsub("enter","return")
        msg = msg:gsub("Alt","Option")
    end
    glu.note(msg)
end

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

function ShowStyleHelp()
    local msg = [[
The style numbers tell Knuth's solver what type of moves are allowed:

Style 0:
Move a single block one step left, right, up, or down.

Style 1:
Move a single block one or more steps in the same direction.

Style 2:
Move a single block one or more steps in different directions.

Style 3:
Move a set of blocks one step left, right, up, or down.

Style 4:
Move a set of blocks one or more steps in the same direction.

Style 5:
Move a set of blocks one or more steps in different directions.

Note that some puzzles cannot be solved using style numbers less than 3.]]
    glu.note(msg)
end

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

function SetStyle(newstyle)
    if style ~= newstyle then
        style = newstyle
        Refresh()
    end
end

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

function SetVolume(newvol)
    if newvol == nil then
        -- prompt for volume
        newvol = glu.getstring("Enter a volume from 0.0 to 1.0:", tostring(volume))
        if newvol == nil then
            return
        end
        newvol = tonumber(newvol)
        if newvol == nil or newvol < 0.0 or newvol > 1.0 then
            glu.warn("Volume must be from 0.0 to 1.0!")
            return
        end
    end

    volume = newvol
    if volume > 1.0 then volume = 1.0 end
    if volume < 0.0 then volume = 0.0 end
    if playsounds and not solving then
        cv.sound("play", "sounds/move.wav", volume)
    end
end

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

function ToggleSounds()
    playsounds = not playsounds
end

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

function ToggleFastMoves()
    fastmoves = not fastmoves
end

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

function CountBlocks(board)
    -- return the total number of blocks in the given board
    -- along with the distinct blocks actually used
    local total = 0
    local used = {}
    
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = board[r][c]
            if cell > 0 and cell ~= obstructed then
                used[cell] = true
                total = total+1
                -- negate other cells belonging to this block
                local offsets = blockoffsets[cell]
                for i = 2, #offsets do
                    local ro = offsets[i][1]
                    local co = offsets[i][2]
                    board[r+ro][c+co] = -cell
                end
            end
        end
    end
    RestoreNegatedCells(board)
    
    local ucount = 0
    for _,_ in pairs(used) do ucount = ucount+1 end

    return total, used, ucount
end

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

function ValidPuzzle()
    -- if startboard and finalboard are valid then return true
    local distinct = 0
    for _,_ in pairs(blockoffsets) do
        distinct = distinct+1
    end
    local stotal, sused, scount = CountBlocks(startboard)
    local ftotal, fused, fcount = CountBlocks(finalboard)
    if stotal > ftotal then
        if ftotal == 0 then
            glu.warn("The finish must have at least one block!")
            return false
        end
        -- puzzle is only valid if all block(s) used in finish are used in start
        local valid = true
        for block,_ in pairs(fused) do
            if not sused[block] then
                valid = false
                break
            end
        end
        if valid then
            simple_finish = true
            return true
        end
        -- continue to distinct checks
    elseif stotal < ftotal then
        glu.warn("The finish has more blocks than the start!")
        return false
    end
    if scount ~= distinct or fcount ~= distinct then
        glu.warn("The start and finish use a different set of blocks!")
        return false
    end
    
    -- puzzle is valid
    simple_finish = false
    return true
end

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

function ToggleEditMode()
    if editmode then
        if ValidPuzzle() then
            editmode = false
        end
    else
        editmode = true
        drawstate = 1
        undomove = {}
        redomove = {}
        selected = {}
    end
    Refresh()
end

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

function SetDrawState(state)
    drawstate = state
    Refresh()
end

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

function ClickInStyle(x, y)
    -- check for click in "Style n" box
    if not PointInRect(x, y, style_rect) then return false end
    
    for i = 0, 5 do
        style_popup.tickitem(i+1, style == i)
    end
    
    style_popup.show(style_rect.x, style_rect.y+style_rect.ht+1)
    return true
end

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

function ClickInPuzzles(x, y)
    -- check for click in "Puzzles" box
    if not PointInRect(x, y, puzzles_rect) then return false end
    
    puzzles_popup.show(puzzles_rect.x, puzzles_rect.y+puzzles_rect.ht+1)
    return true
end

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

function ClickInRecent(x, y)
    -- check for click in "Recent" box
    if not PointInRect(x, y, recent_rect) then return false end

    recent_popup.clearitems() -- remove all existing items

    for i = 1, math.min(maxrecent, #recentfiles) do
        local filename = recentfiles[i]:match("([^"..pathsep.."]+)$")
        filename = filename:gsub("%.txt$","")
        recent_popup.additem(filename, LoadPuzzle, {recentfiles[i]})
    end
    
    recent_popup.show(recent_rect.x, recent_rect.y+recent_rect.ht+1)
    return true
end

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

function ClickInOptions(x, y)
    -- check for click in "Options" box
    if not PointInRect(x, y, options_rect) then return false end
    
    options_popup.tickitem(1, fastmoves)
    options_popup.tickitem(2, playsounds)
    
    options_popup.show(options_rect.x, options_rect.y+options_rect.ht+1)
    return true
end

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

function FindTopLeftCell(board, row, col, cell)
    -- return position of top left cell in given block
    local offsets = blockoffsets[cell]
    for r = 1, numrows do
        for c = 1, numcols do
            if board[r][c] == cell then
                for i = 1, #offsets do
                    local ro = r + offsets[i][1]
                    local co = c + offsets[i][2]
                    if ro == row and co == col then
                        RestoreNegatedCells(board)
                        return r, c
                    else
                        -- ignore any later cells in this block
                        board[ro][co] = -cell
                    end
                end
            end
        end
    end
    -- should never get here
    error("Bug! Failed to find top left cell.")
end

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

local push_up = {}
local push_down = {}
local push_left = {}
local push_right = {}

function GetPush(board, ro, co, cell, deltar, deltac)
    -- find all the blocks connected to the given block in the given direction
    -- and if they exist return 1 if they can all be pushed in that direction
    
    local push_block -- stores the blocks that need to be pushed
    if deltar < 0 then push_block = push_up end
    if deltar > 0 then push_block = push_down end
    if deltac < 0 then push_block = push_left end
    if deltac > 0 then push_block = push_right end

    -- build a list of all cells in all the connected blocks that need to move
    local cell_list = {}
    
    local function append_cells(ro, co, block)
        local offsets = blockoffsets[block]
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            cell_list[#cell_list+1] = {r, c}
        end
    end
    
    append_cells(ro, co, cell)
    push_block[ro..","..co] = true    
    local i = 0
    while i < #cell_list do
        i = i+1
        local r, c = table.unpack(cell_list[i])
        local nextr, nextc = r+deltar, c+deltac
        local nextcell = board[nextr][nextc]
        if nextcell == obstructed then
            -- no movement is possible
            return 0
        end
        if nextcell > 0 then
            local ro, co = FindTopLeftCell(board, nextr, nextc, nextcell)
            if not push_block[ro..","..co] then
                append_cells(ro, co, nextcell)
                push_block[ro..","..co] = true
            end
        end
    end
    
    -- negate all the cells in cell_list
    local numcells = #cell_list
    for i = 1, numcells do
        local r = cell_list[i][1]
        local c = cell_list[i][2]
        board[r][c] = -board[r][c]
    end
    
    -- see if all the cells can be moved
    local canmove = 0
    for i = 1, numcells do
        local r = cell_list[i][1]
        local c = cell_list[i][2]
        if board[r+deltar][c+deltac] <= 0 then canmove = canmove+1 end
    end
    
    RestoreNegatedCells(board)
    
    if canmove == numcells then
        return 1
    else
        return 0
    end
end

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

function GetMoves(board, ro, co, cell)
    -- return the possible single-cell movement directions for the given block
    local up, down, left, right = 0,0,0,0
    local offsets = blockoffsets[cell]
    local numcells = #offsets

    -- negate all cells in block
    for i = 1, numcells do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        board[r][c] = -cell
    end

    local uc,dc,lc,rc = 0,0,0,0
    for i = 1, numcells do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        if board[r-1][c  ] <= 0 then uc = uc+1 end
        if board[r+1][c  ] <= 0 then dc = dc+1 end
        if board[r  ][c-1] <= 0 then lc = lc+1 end
        if board[r  ][c+1] <= 0 then rc = rc+1 end
    end
    
    RestoreNegatedCells(board)

    -- block movement is possible if ALL cells could be moved
    if uc == numcells then up = 1 end
    if dc == numcells then down = 1 end
    if lc == numcells then left = 1 end
    if rc == numcells then right = 1 end

    -- check if block can be moved by pushing connected block(s)
    push_up = {}
    push_down = {}
    push_left = {}
    push_right = {}
    if up    == 0 then up    = GetPush(board, ro, co, cell, -1,  0) end
    if down  == 0 then down  = GetPush(board, ro, co, cell,  1,  0) end
    if left  == 0 then left  = GetPush(board, ro, co, cell,  0, -1) end
    if right == 0 then right = GetPush(board, ro, co, cell,  0,  1) end
    
    return up, down, left, right
end

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

function PushBlocks(board, blocks, deltar, deltac)
    -- negate all block cells
    for rowcol,_ in pairs(blocks) do
        local ro, co = rowcol:match("(%d+),(%d+)")
        ro = tonumber(ro)
        co = tonumber(co)
        local cell = board[ro][co]
        local offsets = blockoffsets[cell]
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r][c] = -cell
        end
    end

    -- shift the negated cells by the desired amount
    local startrow, endrow, rowinc = 1, numrows, 1
    local startcol, endcol, colinc = 1, numcols, 1
    if deltac == 0 then
        -- shift up or down
        if deltar > 0 then
            startrow = numrows
            endrow = 1
            rowinc = -1
        end
    else
        -- deltar is 0 so shift left or right
        if deltac > 0 then
            startcol = numcols
            endcol = 1
            colinc = -1
        end
    end
    for r = startrow, endrow, rowinc do
        for c = startcol, endcol, colinc do
            local cell = board[r][c]
            if cell < 0 then
                board[r+deltar][c+deltac] = -cell
            end
        end
    end
    
    -- change -ve cells to 0
    for r = 1, numrows do
        for c = 1, numcols do
            if board[r][c] < 0 then board[r][c] = 0 end
        end
    end
    
    -- update locations of any selected blocks
    local newlocation = {}
    local rowcol = next(selected, nil)
    while rowcol do
        if blocks[rowcol] then
            -- this selected block has moved
            local ro, co = rowcol:match("(%d+),(%d+)")
            ro = tonumber(ro)
            co = tonumber(co)
            newlocation[(ro+deltar)..","..(co+deltac)] = true
        else
            -- this selected block wasn't moved
            newlocation[rowcol] = true
        end
        selected[rowcol] = nil
        rowcol = next(selected, nil)
    end
    for rowcol,_ in pairs(newlocation) do
        selected[rowcol] = true
    end
end

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

function MoveBlock(board, ro, co, cell, deltar, deltac)
    if playsounds then cv.sound("play", "sounds/move.wav", volume) end
    
    -- check if we need to move a set of connected blocks
    if deltar < 0 and next(push_up) then
        PushBlocks(board, push_up, deltar, deltac)
    elseif deltar > 0 and next(push_down) then
        PushBlocks(board, push_down, deltar, deltac)
    elseif deltac < 0 and next(push_left) then
        PushBlocks(board, push_left, deltar, deltac)
    elseif deltac > 0 and next(push_right) then
        PushBlocks(board, push_right, deltar, deltac)
    else
        -- move a single block, so first set current cells to -1
        local offsets = blockoffsets[cell]
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r][c] = -1
        end

        -- put block in new position
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r+deltar][c+deltac] = cell
        end
    
        -- change -1 cells to 0
        for r = 1, numrows do
            for c = 1, numcols do
                if board[r][c] < 0 then board[r][c] = 0 end
            end
        end
    end
    
    Refresh()
    return ro+deltar, co+deltac
end

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

function GetSelectedMoves(board, ro_unused, co_unused, cell_unused)
    -- return the possible single-cell movement directions for the selected blocks
    local up, down, left, right = 0,0,0,0
    local totalcells = 0
    
    -- negate all cells in all selected blocks
    for rowcol,_ in pairs(selected) do
        local ro, co = rowcol:match("(%d+),(%d+)")
        ro = tonumber(ro)
        co = tonumber(co)
        local cell = board[ro][co]
        local offsets = blockoffsets[cell]
        local numcells = #offsets
        totalcells = totalcells + numcells
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r][c] = -cell
        end
    end
    
    -- now check if selected blocks can be moved
    local uc,dc,lc,rc = 0,0,0,0
    for rowcol,_ in pairs(selected) do
        local ro, co = rowcol:match("(%d+),(%d+)")
        ro = tonumber(ro)
        co = tonumber(co)
        local cell = board[ro][co]
        local offsets = blockoffsets[-cell] -- cell is negated
        local numcells = #offsets
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            if board[r-1][c  ] <= 0 then uc = uc+1 end
            if board[r+1][c  ] <= 0 then dc = dc+1 end
            if board[r  ][c-1] <= 0 then lc = lc+1 end
            if board[r  ][c+1] <= 0 then rc = rc+1 end
        end
    end
    
    RestoreNegatedCells(board)
    
    -- movement is only possible if ALL cells in ALL blocks could be moved
    if uc == totalcells then up = 1 end
    if dc == totalcells then down = 1 end
    if lc == totalcells then left = 1 end
    if rc == totalcells then right = 1 end
    
    return up, down, left, right
end

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

function MoveSelectedBlocks(board, ro, co, cell_unused, deltar, deltac)
    if playsounds then cv.sound("play", "sounds/move.wav", volume) end
    
    local newro = ro + deltar
    local newco = co + deltac

    -- negate all selected block cells
    for rowcol,_ in pairs(selected) do
        local ro, co = rowcol:match("(%d+),(%d+)")
        ro = tonumber(ro)
        co = tonumber(co)
        local cell = board[ro][co]
        local offsets = blockoffsets[cell]
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r][c] = -cell
        end
    end

    -- shift the negated cells by the desired amount
    local startrow, endrow, rowinc = 1, numrows, 1
    local startcol, endcol, colinc = 1, numcols, 1
    if deltac == 0 then
        -- shift up or down
        if deltar > 0 then
            startrow = numrows
            endrow = 1
            rowinc = -1
        end
    else
        -- deltar is 0 so shift left or right
        if deltac > 0 then
            startcol = numcols
            endcol = 1
            colinc = -1
        end
    end
    for r = startrow, endrow, rowinc do
        for c = startcol, endcol, colinc do
            local cell = board[r][c]
            if cell < 0 then
                board[r+deltar][c+deltac] = -cell
            end
        end
    end
    
    -- change -ve cells to 0
    for r = 1, numrows do
        for c = 1, numcols do
            if board[r][c] < 0 then board[r][c] = 0 end
        end
    end
    
    -- update locations of selected blocks
    local newlocation = {}
    local rowcol = next(selected, nil)
    while rowcol do
        local ro, co = rowcol:match("(%d+),(%d+)")
        ro = tonumber(ro)
        co = tonumber(co)
        newlocation[(ro+deltar)..","..(co+deltac)] = true
        selected[rowcol] = nil
        rowcol = next(selected, nil)
    end
    for rowcol,_ in pairs(newlocation) do
        selected[rowcol] = true
    end
    
    Refresh()
    return newro, newco
end

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

function ClickInBoard(x, y, button, mods, board, xo, yo, boardrect)
    local row = 1 + (y - yo) // cellsize
    local col = 1 + (x - xo) // cellsize
    if row > numrows then row = numrows end
    if col > numcols then col = numcols end
    local cell = board[row][col]
    if cell == 0 or cell == obstructed then return end
    
    if board == finalboard then
        glu.note("You can only change the finish position in Edit mode.")
        return
    end

    -- click is in a block so find top left cell in block
    local ro, co = FindTopLeftCell(board, row, col, cell)

    if button ~= "left" or mods ~= "none" then
        if button == "left" and mods == "shift" then
            local topleft = ro..","..co
            if selected[topleft] then
                -- deselect ALL selected blocks
                selected = {}
            else
                -- select this block
                selected[topleft] = true
            end
            Refresh()
        end
        return
    end
    
    -- check if we're moving a single block or a group of selected blocks
    local getmoves = GetMoves
    local move = MoveBlock
    if selected[ro..","..co] then
        getmoves = GetSelectedMoves
        move = MoveSelectedBlocks
    end

    -- check if this block can be moved and in which direction
    local up, down, left, right = getmoves(board, ro, co, cell)
    if up + down + left + right == 0 then
        -- block can't be moved
        glu.beep()
        return
    end
    
    -- block (or set of blocks) can move so allow user to drag it/them
    cv.cursor("hand")
    local oldstate = GetBoardState(board)
    local roff = row - ro
    local coff = col - co
    repeat
        x, y = cv.getxy()
        if x >= 0 and y >= 0 and PointInRect(x, y, boardrect) then
            row = 1 + (y - yo) // cellsize
            col = 1 + (x - xo) // cellsize
            if row > numrows then row = numrows end
            if col > numcols then col = numcols end
            local deltar = row - ro - roff
            local deltac = col - co - coff
            if deltar ~= 0 or deltac ~= 0 then
                -- try to move block
                up, down, left, right = getmoves(board, ro, co, cell)
                if math.abs(deltar) > math.abs(deltac) then
                    -- try up/down first
                    if deltar > 0 and down > 0 then
                        ro, co = move(board, ro, co, cell, 1, 0)
                    elseif deltar < 0 and up > 0 then
                        ro, co = move(board, ro, co, cell, -1, 0)
                    elseif deltac > 0 and right > 0 then
                        ro, co = move(board, ro, co, cell, 0, 1)
                    elseif deltac < 0 and left > 0 then
                        ro, co = move(board, ro, co, cell, 0, -1)
                    end
                else
                    -- try left/right first
                    if deltac > 0 and right > 0 then
                        ro, co = move(board, ro, co, cell, 0, 1)
                    elseif deltac < 0 and left > 0 then
                        ro, co = move(board, ro, co, cell, 0, -1)
                    elseif deltar > 0 and down > 0 then
                        ro, co = move(board, ro, co, cell, 1, 0)
                    elseif deltar < 0 and up > 0 then
                        ro, co = move(board, ro, co, cell, -1, 0)
                    end
                end
            end
        end
    until glu.getevent():find("^mup")
    cv.cursor("arrow")
    
    -- check if board has changed
    if GetBoardState(board) ~= oldstate then
        redomove = {}
        undomove[#undomove+1] = oldstate
        Refresh()
        if PuzzleSolved() then
            if playsounds then cv.sound("play", "sounds/success.wav", volume) end
            FlashBoards()
        end
    end
end

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

local rmin, cmin, rmax, cmax

function UpdateBlockOffsets(board, row, col, newblock)
    -- use bounding box to ensure offsets are ordered from top left to bottom right
    local offsets = blockoffsets[newblock]
    if #offsets == 0 then
        offsets[1] = {0,0}
        rmin, cmin = row, col
        rmax, cmax = row, col
    else
        if row < rmin then rmin = row end
        if col < cmin then cmin = col end
        if row > rmax then rmax = row end
        if col > cmax then cmax = col end
        local i = 0
        local ro, co
        for r = rmin, rmax do
            for c = cmin, cmax do
                if board[r][c] == newblock then
                    i = i+1
                    if i == 1 then
                        -- offsets[1] is {0,0}
                        ro, co = r, c
                    else
                        offsets[i] = {r-ro, c-co}
                    end
                end
            end
        end
    end
end

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

function RemoveBlock(board, row, col, cell)
    -- remove given block from given board
    local ro, co = FindTopLeftCell(board, row, col, cell)
    local offsets = blockoffsets[cell]
    for i = 1, #offsets do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        board[r][c] = 0
    end
    -- count how many given cells remain in BOTH boards;
    -- if none then make the block index available for new blocks
    local count = 0
    for r = 1, numrows do
        for c = 1, numcols do
            if startboard[r][c] == cell then count = count+1 end
            if finalboard[r][c] == cell then count = count+1 end
        end
    end
    if count == 0 then
        -- this block index can be used for new blocks
        blockoffsets[cell] = nil
        blocklabels[cell] = nil
        blockcolors[cell] = nil
    end
end

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

function ChangeCell(thisboard, row, col, oldcell, newcell, update_offsets)
    local otherboard = finalboard
    if thisboard == finalboard then otherboard = startboard end

    -- ensure obstructed cell positions in both boards are identical
    if oldcell == obstructed then
        if otherboard[row][col] ~= obstructed then
            -- should never happen
            error("Bug! Cell in other board should be obstructed.")
        end
        otherboard[row][col] = 0
    elseif newcell == obstructed then
        local cell = otherboard[row][col]
        if cell > 0 and cell ~= obstructed then
            -- remove block from other board
            RemoveBlock(otherboard, row, col, cell)
        end
        otherboard[row][col] = obstructed
    end
    
    if oldcell > 0 and oldcell ~= obstructed then
        -- newcell must be 0 or obstructed so remove block from this board
        RemoveBlock(thisboard, row, col, oldcell)
    end
    
    thisboard[row][col] = newcell

    if update_offsets then
        UpdateBlockOffsets(thisboard, row, col, newcell)
    end
    
    Refresh()
end

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

function UniqueBlock(block)
    -- return true if the given block only occurs once
    local numcells = #blockoffsets[block]
    local count = 0
    for r = 1, numrows do
        for c = 1, numcols do
            if startboard[r][c] == block then
                count = count+1
                if count > numcells then return false end
            end
            if finalboard[r][c] == block then
                count = count+1
                if count > numcells then return false end
            end
        end
    end
    -- count is numcells
    return true
end

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

function FindMatchingBlock(block, newlabel, newcolor)
    -- check if changing the label or color of the given block matches another block
    local offsets = blockoffsets[block]
    local numcells = #offsets

    for k,koffsets in pairs(blockoffsets) do
        if k ~= block then
            -- compare labels
            if blocklabels[k] ~= newlabel then
                goto no_match
            end
            -- labels match so compare colors
            if (blockcolors[k] == nil and newcolor) or
               (blockcolors[k] and newcolor == nil) then
                goto no_match
            elseif blockcolors[k] and not gp.equal(blockcolors[k], newcolor) then
                goto no_match
            end
            -- colors match so compare shapes
            if numcells ~= #koffsets then
                goto no_match
            end
            for i,v in ipairs(offsets) do
                if v[1] ~= koffsets[i][1] or
                   v[2] ~= koffsets[i][2] then
                   goto no_match
                end
            end
            return k -- we found a matching block
        end
        ::no_match::
    end

    return 0 -- no match
end

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

function GetNewBlock()
    -- return the first available index for a new block, if possible
    for i = 1, maxblocks do
        if blockoffsets[i] == nil then return i end
    end
    return 0
end

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

function NoMoreBlocks()
    local modname = "alt"
    if glu.os() == "Mac" then modname = "option" end
    glu.warn(fmt("Sorry, no more blocks can be created!\n(The maximum is %d distinct blocks.)\n\n"..
                 "If you want to duplicate an existing block\nthen %s-click and drag it.",
                 maxblocks, modname))
end

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

function ChangeLabel()
    local block = clickedboard[clickedrow][clickedcol]
    local oldlabel = blocklabels[block] or ""
    local newlabel = glu.getstring("Enter a short label for this block:", oldlabel)
    if newlabel == nil or newlabel == oldlabel then
        return
    end
    
    -- changing a block's label or color is not so simple; we have to ensure
    -- that blocks with the same label, color and shape all use the same index
    -- in blocklabels, blockcolors, and blockoffsets

    -- check if this block only occurs once
    local unique = UniqueBlock(block)
    
    local offsets = blockoffsets[block]
    local numcells = #offsets

    if #newlabel == 0 then newlabel = nil end

    -- check if changing the label would make this block a clone of another block
    local match = FindMatchingBlock(block, newlabel, blockcolors[block])    
    if match > 0 then
        -- make the block a clone of the matching block
        local ro, co = FindTopLeftCell(clickedboard, clickedrow, clickedcol, block)
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            clickedboard[r][c] = match
        end
        if unique then
            -- make block index available for creating a new block
            blockoffsets[block] = nil
            blocklabels[block] = nil
            blockcolors[block] = nil
        end
        block = match
    elseif not unique then
        -- the block occurs more than once so we have to create a new block, if possible
        local newblock = GetNewBlock()
        if newblock == 0 then
            NoMoreBlocks()
            return
        end
        
        -- copy offsets and color
        blockoffsets[newblock] = {}
        for i = 1, numcells do
            blockoffsets[newblock][i] = { offsets[i][1], offsets[i][2] }
        end
        blockcolors[newblock] = nil
        if blockcolors[block] then
            blockcolors[newblock] = { table.unpack(blockcolors[block]) }
        end
        
        -- update cells in clickedboard
        local ro, co = FindTopLeftCell(clickedboard, clickedrow, clickedcol, block)
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            clickedboard[r][c] = newblock
        end
        block = newblock
    end
    
    blocklabels[block] = newlabel -- possibly nil    
    Refresh()
end

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

function GetColor(oldcolor, title)
    -- create a custom dialog to get new color
    local newcolor = { table.unpack(oldcolor) }
    local dialogwd, dialoght
    local x, y -- top left corner of dialog box
    local r_slider, g_slider, b_slider
    local ok_hit = false
    local default_hit = false
    
    local function UpdateSlider(slider, ypos, char, val)
        slider.hide() -- erase old slider
        slider.show(x+(dialogwd - slider.wd)//2, ypos, val)
        cv.rgba(cp.white)
        local textx = slider.x+slider.wd+5
        cv.fill(textx, ypos, x+dialogwd-textx-2, slider.ht)
        cv.rgba(cp.black)
        local _, ht = cv.text("temp", char.."="..val)
        cv.paste("temp", textx, ypos+((slider.ht-ht)/2+0.5)//1)
        cv.delete("temp")
    end
    
    local function UpdateColorBox()
        -- update box showing newcolor
        cv.rgba(grid_color)
        cp.round_rect(x+20, g_slider.y+(g_slider.ht-40)//2, 40, 40, 0, 2, newcolor)
    end

    local function ColorChanged(newval, slider)
        -- cp.process passes in the new slider value and the slider
        if slider == r_slider then newcolor[1] = newval end
        if slider == g_slider then newcolor[2] = newval end
        if slider == b_slider then newcolor[3] = newval end
        UpdateSlider(r_slider, y+50, "R", newcolor[1])
        UpdateSlider(g_slider, y+80, "G", newcolor[2])
        UpdateSlider(b_slider, y+110, "B", newcolor[3])
        UpdateColorBox()
        cv.update()
    end

    cp.disable_all() -- prevent current buttons from being clicked

    -- create sliders (ColorChanged will only be called when a slider's value changes)
    r_slider = cp.slider(256, 0, 255, ColorChanged)
    g_slider = cp.slider(256, 0, 255, ColorChanged)
    b_slider = cp.slider(256, 0, 255, ColorChanged)
    r_slider.setbackcolor(cp.red)
    g_slider.setbackcolor(cp.green)
    b_slider.setbackcolor(cp.blue)
    
    -- create buttons
    cp.buttonwd = 0
    local ok_button = cp.button("OK", function() ok_hit = true end)
    local default_button = cp.button("Default Color", function() default_hit = true end)
    local cancel_button = cp.button("Cancel", glu.exit)
    ok_button.setborder(0)
    default_button.setborder(0)
    default_button.setbackcolor(cp.gray)
    cancel_button.setborder(0)
    cancel_button.setbackcolor(cp.gray)
    local buttht = ok_button.ht

    -- save canvas in a clip and then darken everything
    cv.copy(0,0,0,0,"canvas")
    cv.replace("*#-60 *#-60 *#-60 *#")
    
    -- draw the dialog in middle of canvas
    cv.blend(0)
    cv.rgba(cp.black)
    cv.font("default",10)
    local textwd, textht = cv.text("text", title)
    dialogwd, dialoght = 400, 200
    x = (cvwd - dialogwd)//2
    y = (cvht - dialoght)//2
    cv.rgba(cp.gray)
    cp.round_rect(x+5, y+5, dialogwd, dialoght, 0, 0, {0,0,0,128}) -- shadow
    cp.round_rect(x, y, dialogwd, dialoght, 0, 1, cp.white)
    cv.blend(2)
    cv.paste("text", x+(dialogwd-textwd)//2, y+20)
    cv.delete("text")

    -- show buttons and sliders
    ok_button.show(x+dialogwd-ok_button.wd-20, y+dialoght-buttht-20)
    cancel_button.show(ok_button.x-20-cancel_button.wd, y+dialoght-buttht-20)
    default_button.show(x+20, y+dialoght-buttht-20)
    UpdateSlider(r_slider, y+50, "R", newcolor[1])
    UpdateSlider(g_slider, y+80, "G", newcolor[2])
    UpdateSlider(b_slider, y+110, "B", newcolor[3])
    UpdateColorBox()
    cv.update()

    local function DialogEventLoop()
        while true do
            local event = glu.getevent()
            if #event == 0 then
                glu.sleep(5) -- don't hog cpu if idle
            else
                event = cp.process(event)
                if #event == 0 then
                    -- cp.process handled click in button/slider
                    if ok_hit then
                        return
                    elseif default_hit then
                        newcolor = { table.unpack(block_color) }
                        return
                    end
                elseif event == "key return none" then
                    return
                end
            end
        end
    end

    -- call DialogEventLoop inside xpcall so we can detect glu.exit call
    local status, err = xpcall(DialogEventLoop, gp.trace)
    if err then
        glu.continue("")
        if err:find("^GLU: ABORT SCRIPT") then
            -- user hit escape key or Cancel button
            newcolor = nil
        else
            -- Lua runtime error
            glu.warn(err)
        end
    end
    
    -- remove buttons and sliders
    cancel_button.hide()
    cancel_button = nil
    ok_button.hide()
    ok_button = nil
    default_button.hide()
    default_button = nil
    r_slider.hide()
    g_slider.hide()
    b_slider.hide()
    r_slider = nil
    g_slider = nil
    b_slider = nil

    -- restore canvas
    cv.blend(0)
    cv.paste("canvas",0,0)
    cv.delete("canvas")
    
    cp.enable_all() -- restore the buttons that were disabled by cp.disable_all
    Refresh()

    return newcolor
end

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

function ChangeColor()
    local block = clickedboard[clickedrow][clickedcol]
    local oldcolor = blockcolors[block] or block_color
    local newcolor = GetColor(oldcolor, "Choose a color for this block.")
    if newcolor == nil or gp.equal(newcolor, oldcolor) then
        return
    end

    -- check if this block only occurs once
    local unique = UniqueBlock(block)
    
    local offsets = blockoffsets[block]
    local numcells = #offsets

    if gp.equal(newcolor, block_color) then newcolor = nil end

    -- check if changing the color would make this block a clone of another block
    local match = FindMatchingBlock(block, blocklabels[block], newcolor)
    if match > 0 then
        -- make the block a clone of the matching block
        local ro, co = FindTopLeftCell(clickedboard, clickedrow, clickedcol, block)
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            clickedboard[r][c] = match
        end
        if unique then
            -- make block index available for creating a new block
            blockoffsets[block] = nil
            blocklabels[block] = nil
            blockcolors[block] = nil
        end
        block = match
    elseif not unique then
        -- the block occurs more than once so we have to create a new block, if possible
        local newblock = GetNewBlock()
        if newblock == 0 then
            NoMoreBlocks()
            return
        end
        
        -- copy offsets and label
        blockoffsets[newblock] = {}
        for i = 1, numcells do
            blockoffsets[newblock][i] = { offsets[i][1], offsets[i][2] }
        end
        blocklabels[newblock] = blocklabels[block]
        
        -- update cells in clickedboard
        local ro, co = FindTopLeftCell(clickedboard, clickedrow, clickedcol, block)
        for i = 1, numcells do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            clickedboard[r][c] = newblock
        end
        block = newblock
    end
    
    blockcolors[block] = newcolor -- possibly nil
    Refresh()
end

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

function ChangeMatchingLabels()
    local block = clickedboard[clickedrow][clickedcol]
    local oldlabel = blocklabels[block] or ""
    local newlabel = glu.getstring("Enter a short label for the matching blocks:", oldlabel)
    if newlabel == nil or newlabel == oldlabel then
        return
    end

    if #newlabel == 0 then newlabel = nil end

    -- check if changing the label would make these blocks clones of another block
    local match = FindMatchingBlock(block, newlabel, blockcolors[block])    
    if match > 0 then
        -- make all blocks clones of the matching block
        for r = 1, numrows do
            for c = 1, numcols do
                if startboard[r][c] == block then startboard[r][c] = match end
                if finalboard[r][c] == block then finalboard[r][c] = match end
            end
        end
        -- make block index available for creating a new block
        blockoffsets[block] = nil
        blocklabels[block] = nil
        blockcolors[block] = nil
    else
        blocklabels[block] = newlabel
    end
    Refresh()
end

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

function ChangeMatchingColors()
    local block = clickedboard[clickedrow][clickedcol]
    local oldcolor = blockcolors[block] or block_color
    local newcolor = GetColor(oldcolor, "Choose a color for the matching blocks.")
    if newcolor == nil or gp.equal(newcolor, oldcolor) then
        return
    end

    if gp.equal(newcolor, block_color) then newcolor = nil end

    -- check if changing the color would make these blocks clones of another block
    local match = FindMatchingBlock(block, blocklabels[block], newcolor)
    if match > 0 then
        -- make all blocks clones of the matching block
        for r = 1, numrows do
            for c = 1, numcols do
                if startboard[r][c] == block then startboard[r][c] = match end
                if finalboard[r][c] == block then finalboard[r][c] = match end
            end
        end
        -- make block index available for creating a new block
        blockoffsets[block] = nil
        blocklabels[block] = nil
        blockcolors[block] = nil
    else
        blockcolors[block] = newcolor -- possibly nil
    end
    
    Refresh()
end

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

function TooManyBlocks(what)
    local stotal = CountBlocks(startboard)
    local ftotal = CountBlocks(finalboard)
    if (stotal + ftotal) > maxblocks then
        local msg = "Too many blocks to "..what.." every one\n(maximum = "..maxblocks..")."
        if ftotal > 0 then msg = msg.."\nTry deleting the blocks in the finish board." end
        glu.warn(msg)
        return true
    end
    return false
end

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

function NumberEveryBlock()
    if TooManyBlocks("number") then return end
    
    local newoffsets = {}
    local newlabels = {}
    local newcolors = {}
    
    -- label every block with a different number
    local label = 0
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = startboard[r][c]
            if cell > 0 and cell ~= obstructed then
                label = label+1
                newcolors[label] = nil
                if blockcolors[cell] then newcolors[label] = { table.unpack(blockcolors[cell]) } end
                newlabels[label] = tostring(label)
                newoffsets[label] = {}
                local offsets = blockoffsets[cell]
                for i = 1, #offsets do
                    newoffsets[label][i] = { offsets[i][1], offsets[i][2] }
                end
                 -- change and negate all cells belonging to this block
                for i = 1, #offsets do
                    local ro = offsets[i][1]
                    local co = offsets[i][2]
                    startboard[r+ro][c+co] = -label
                end
            end
        end
    end
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = finalboard[r][c]
            if cell > 0 and cell ~= obstructed then
                label = label+1
                newcolors[label] = nil
                if blockcolors[cell] then newcolors[label] = { table.unpack(blockcolors[cell]) } end
                newlabels[label] = tostring(label)
                newoffsets[label] = {}
                local offsets = blockoffsets[cell]
                for i = 1, #offsets do
                    newoffsets[label][i] = { offsets[i][1], offsets[i][2] }
                end
                 -- change and negate all cells belonging to this block
                local offsets = blockoffsets[cell]
                for i = 1, #offsets do
                    local ro = offsets[i][1]
                    local co = offsets[i][2]
                    finalboard[r+ro][c+co] = -label
                end
            end
        end
    end
    RestoreNegatedCells(startboard)
    RestoreNegatedCells(finalboard)

    blockoffsets = newoffsets
    blocklabels = newlabels
    blockcolors = newcolors
    
    Refresh()
end

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

local palette = {
    -- this assumes maxblocks is <= 15
    cp.red, cp.green, {0,128,255,255},
    cp.yellow, cp.magenta, cp.cyan,
    {255,128,0,255}, {128,200,128,255}, {128,128,255,255},
    {255,80,150,255}, {255,220,160,255}, {170,170,255,255},
    {200,255,200,255}, {255,200,255,255}, cp.white
}

function ColorEveryBlock()
    if TooManyBlocks("color") then return end
    
    local newoffsets = {}
    local newlabels = {}
    local newcolors = {}
    
    -- color every block with a different color from palette
    local i = 0
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = startboard[r][c]
            if cell > 0 and cell ~= obstructed then
                i = i+1
                newcolors[i] = palette[i]
                newlabels[i] = blocklabels[cell]
                newoffsets[i] = {}
                local offsets = blockoffsets[cell]
                for o = 1, #offsets do
                    newoffsets[i][o] = { offsets[o][1], offsets[o][2] }
                end
                 -- change and negate all cells belonging to this block
                for o = 1, #offsets do
                    local ro = offsets[o][1]
                    local co = offsets[o][2]
                    startboard[r+ro][c+co] = -i
                end
            end
        end
    end
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = finalboard[r][c]
            if cell > 0 and cell ~= obstructed then
                i = i+1
                newcolors[i] = palette[i]
                newlabels[i] = blocklabels[cell]
                newoffsets[i] = {}
                local offsets = blockoffsets[cell]
                for o = 1, #offsets do
                    newoffsets[i][o] = { offsets[o][1], offsets[o][2] }
                end
                 -- change and negate all cells belonging to this block
                for o = 1, #offsets do
                    local ro = offsets[o][1]
                    local co = offsets[o][2]
                    finalboard[r+ro][c+co] = -i
                end
            end
        end
    end
    RestoreNegatedCells(startboard)
    RestoreNegatedCells(finalboard)

    blockoffsets = newoffsets
    blocklabels = newlabels
    blockcolors = newcolors
    
    Refresh()
end

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

function NumberMatchingBlocks()
    local i = 0
    for k,_ in pairs(blockoffsets) do
        i = i+1
        blocklabels[k] = tostring(i)
    end
    Refresh()
end

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

function ColorMatchingBlocks()
    local i = 0
    for k,_ in pairs(blockoffsets) do
        i = i+1
        blockcolors[k] = palette[i]
    end
    Refresh()
end

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

function RemoveAllLabels()
    blocklabels = {}
    -- check for new clones (ie. blocks with the same shape and color)
    local block = next(blockoffsets, nil)
    while block do
        local match = FindMatchingBlock(block, nil, blockcolors[block])    
        if match > 0 then
            -- make matching blocks clones of block
            for r = 1, numrows do
                for c = 1, numcols do
                    if startboard[r][c] == match then startboard[r][c] = block end
                    if finalboard[r][c] == match then finalboard[r][c] = block end
                end
            end
            -- make match index available for creating a new block
            blockoffsets[match] = nil
            blockcolors[match] = nil
        end
        block = next(blockoffsets, block)
    end
    Refresh()
end

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

function RemoveAllColors()
    blockcolors = {}
    -- check for new clones (ie. blocks with the same shape and label)
    local block = next(blockoffsets, nil)
    while block do
        local match = FindMatchingBlock(block, blocklabels[block], nil)    
        if match > 0 then
            -- make matching blocks clones of block
            for r = 1, numrows do
                for c = 1, numcols do
                    if startboard[r][c] == match then startboard[r][c] = block end
                    if finalboard[r][c] == match then finalboard[r][c] = block end
                end
            end
            -- make match index available for creating a new block
            blockoffsets[match] = nil
            blocklabels[match] = nil
        end
        block = next(blockoffsets, block)
    end
    Refresh()
end

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

function DeleteBlock()
    local cell = clickedboard[clickedrow][clickedcol]
    RemoveBlock(clickedboard, clickedrow, clickedcol, cell)
    Refresh()
end

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

function DeleteMatchingBlocks()
    local cell = clickedboard[clickedrow][clickedcol]
    -- remove this block and any clones from BOTH boards
    for r = 1, numrows do
        for c = 1, numcols do
            if startboard[r][c] == cell then
                RemoveBlock(startboard, r, c, cell)
                Refresh()
            end
        end
    end
    for r = 1, numrows do
        for c = 1, numcols do
            if finalboard[r][c] == cell then
                RemoveBlock(finalboard, r, c, cell)
                Refresh()
            end
        end
    end
    -- block should no longer exist
    if blockoffsets[cell] then
        error("Bug! blockoffsets[cell] should be nil.")
    end
end

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

function DuplicateStart()
    -- first remove any blocks from final board
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = finalboard[r][c]
            if cell > 0 and cell ~= obstructed then
                RemoveBlock(finalboard, r, c, cell)
            end
        end
    end
    -- now copy blocks from start board to final board
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = startboard[r][c]
            if cell > 0 and cell ~= obstructed then
                finalboard[r][c] = cell
            end
        end
    end
    Refresh()
end

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

function ClearBoard()
    local otherboard = finalboard
    if clickedboard == finalboard then otherboard = startboard end
    for r = 1, numrows do
        for c = 1, numcols do
            local cell = clickedboard[r][c]
            if cell == obstructed then
                clickedboard[r][c] = 0
                otherboard[r][c] = 0
                Refresh()
            elseif cell > 0 then
                RemoveBlock(clickedboard, r, c, cell)
                Refresh()
            end
        end
    end
end

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

function EmptyBoard(board)
    -- return true if all cells in given board are empty
    for r = 1, numrows do
        for c = 1, numcols do
            if board[r][c] > 0 then return false end
        end
    end
    return true
end

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

function ShowEditMenu(x, y, board, row, col, cell)
    clickedboard = board    -- for ClearBoard, etc
    clickedrow = row        -- ditto
    clickedcol = col        -- ditto

    local isblock = cell > 0 and cell ~= obstructed
    
    local stotal = CountBlocks(startboard)
    local ftotal = CountBlocks(finalboard)
    local startempty = EmptyBoard(startboard)
    local finalempty = EmptyBoard(finalboard)
    local empty = (board == startboard and startempty) or (board == finalboard and finalempty)
    local hasblocks = (stotal + ftotal) > 0
    local haslabels = next(blocklabels) ~= nil
    local hascolors = next(blockcolors) ~= nil

    -- enable/disable various items
    -- (see CreatePopUpMenus for item numbers)

    edit_popup.enableitem(1, hasblocks)  -- Number Every Block
    edit_popup.enableitem(2, hasblocks)  -- Number Matching Blocks
    edit_popup.enableitem(3, isblock)    -- Change Label in This Block...
    edit_popup.enableitem(4, isblock)    -- Change Label in Matching Blocks...
    edit_popup.enableitem(5, haslabels)  -- Remove All Labels
    --------------------- 6
    edit_popup.enableitem(7, hasblocks)  -- Color Every Block
    edit_popup.enableitem(8, hasblocks)  -- Color Matching Blocks
    edit_popup.enableitem(9, isblock)    -- Change Color of This Block...
    edit_popup.enableitem(10, isblock)   -- Change Color of Matching Blocks...
    edit_popup.enableitem(11, hascolors) -- Remove All Colors
    --------------------- 12
    edit_popup.enableitem(13, isblock)   -- Delete This Block
    edit_popup.enableitem(14, isblock)   -- Delete Matching Blocks
    --------------------- 15
    edit_popup.enableitem(16, not empty) -- Copy Start to Finish
    edit_popup.enableitem(17, not empty) -- Clear Board

    -- show a popup menu with various edit actions
    cv.cursor("arrow")
    edit_popup.show(x, y)
    cv.cursor("pencil")
end

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

function GetBoundingBox(xo, yo, ro, co, cell)
    -- return given block's bounding box (in canvas coordinates)
    local minr = numrows+1
    local minc = numcols+1
    local maxr = 0
    local maxc = 0
    
    local offsets = blockoffsets[cell]
    for i = 1, #offsets do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        if r < minr then minr = r end
        if c < minc then minc = c end
        if r > maxr then maxr = r end
        if c > maxc then maxc = c end
    end

    local bbx = xo + (minc-1)*cellsize
    local bby = yo + (minr-1)*cellsize
    local bbwd = (maxc-minc+1)*cellsize
    local bbht = (maxr-minr+1)*cellsize
    
    -- we also return minc
    return bbx, bby, bbwd, bbht, minc
end

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

function DragBlock(delete, x, y, board, xo, yo, row, col, cell)
    -- drag the clicked block to a location in either board
    -- and return true if it was successfully moved
    
    -- get the block's bounding box in canvas coordinates
    local ro, co = FindTopLeftCell(board, row, col, cell)
    local bbx, bby, bbwd, bbht, mincol = GetBoundingBox(xo, yo, ro, co, cell)
    
    -- create clips big enough for block and its shadow
    local block_clip = "block"
    local shadow_clip = "shadow"
    local temp_clip = "temp"
    cv.create(bbwd+4, bbht+4, block_clip)
    cv.create(bbwd, bbht, shadow_clip)
    cv.create(bbwd, bbht, temp_clip)
    
    -- draw block into temp_clip
    cv.target(temp_clip)
    DrawBlock(board, ro, co, cell, xo-bbx, yo-bby)
    RestoreNegatedCells(board)
    cv.copy(0, 0, bbwd, bbht, shadow_clip)
    cv.target()
    
    -- now ok to delete block if requested
    local offsets = blockoffsets[cell]
    if delete then
        for i = 1, #offsets do
            local r = ro + offsets[i][1]
            local c = co + offsets[i][2]
            board[r][c] = 0
        end
        -- calling Refresh() causes unwanted update
        if board == startboard then
            DrawBoard(startboard, xs, ys, {})
        else
            DrawBoard(finalboard, xf, yf, {})
        end
    end
    
    -- create a clip with current canvas
    local canvas_clip = "canvas"
    cv.create(cvwd, cvht, canvas_clip)
    cv.copy(0, 0, cvwd, cvht, canvas_clip)
    
    -- create shadow by replacing opaque pixels with grid_color
    cv.target(shadow_clip)
    cv.rgba(grid_color)
    cv.replace("* * * 255")
    
    cv.blend(1)
    cv.target(block_clip)
    cv.paste(shadow_clip, 0, 0)
    cv.paste(shadow_clip, 4, 0)
    cv.paste(shadow_clip, 0, 4)
    cv.paste(shadow_clip, 4, 4)
    cv.paste(temp_clip, 2, 2)
    cv.target()
    cv.delete(temp_clip)
    cv.delete(shadow_clip)
    
    local coff = col - mincol
    local roff = row - ro -- ro is minimum row
    local xoff = coff*cellsize + cellsize//2
    local yoff = roff*cellsize + cellsize//2
    
    cv.blend(2)
    cv.paste(block_clip, x-xoff, y-yoff)
    cv.blend(0)
    cv.update()
    
    local prevx, prevy = x, y
    repeat
        x, y = cv.getxy()
        if x >= 0 and y >= 0 then
            if x ~= prevx or y ~= prevy then
                -- mouse has moved
                cv.paste(canvas_clip, 0, 0)
                cv.blend(2)
                cv.paste(block_clip, x-xoff, y-yoff)
                cv.blend(0)
                cv.update()
                prevx, prevy = x, y
            end
        end
    until glu.getevent():find("^mup")
    
    cv.delete(block_clip)
    cv.delete(canvas_clip)
    
    -- check final location
    if PointInRect(x, y, startrect) then
        board = startboard
        xo, yo = xs, ys
    elseif PointInRect(x, y, finalrect) then
        board = finalboard
        xo, yo = xf, yf
    else
        glu.beep()
        Refresh()
        return
    end
    
    -- check that all new cell locations are within board and empty
    roff = row - ro
    coff = col - co
    row = 1 + (y - yo) // cellsize
    col = 1 + (x - xo) // cellsize
    if row > numrows then row = numrows end
    if col > numcols then col = numcols end
    ro = row - roff
    co = col - coff
    for i = 1, #offsets do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        if r < 1 or r > numrows or c < 1 or c > numcols or board[r][c] ~= 0 then
            glu.beep()
            Refresh()
            return
        end
    end
    
    -- block can be copied into board
    for i = 1, #offsets do
        local r = ro + offsets[i][1]
        local c = co + offsets[i][2]
        board[r][c] = cell
    end
    Refresh()
    return true
end

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

function EditBoard(x, y, button, mods, board, xo, yo, boardrect)
    local row = 1 + (y - yo) // cellsize
    local col = 1 + (x - xo) // cellsize
    if row > numrows then row = numrows end
    if col > numcols then col = numcols end
    local cell = board[row][col]

    if button ~= "left" or mods ~= "none" then
        if button == "right" or mods == "ctrl" then
            -- show a pop-up menu with various editing commands
            ShowEditMenu(x, y, board, row, col, cell)
        elseif button == "left" and mods == "alt" then
            if cell > 0 and cell ~= obstructed then
                -- drag a copy of the clicked block to a new location
                cv.cursor("hand")
                DragBlock(false, x, y, board, xo, yo, row, col, cell)
                cv.cursor("pencil")
            end
        end
        return
    end
    
    if drawstate == 1 and cell > 0 and cell ~= obstructed then
        -- save the block's location in case it has to be restored
        local ro, co = FindTopLeftCell(board, row, col, cell)
        -- delete block and drag it to new location
        cv.cursor("hand")
        local moved = DragBlock(true, x, y, board, xo, yo, row, col, cell)
        cv.cursor("pencil")
        if not moved then
            -- restore block to its original location
            local offsets = blockoffsets[cell]
            for i = 1, #offsets do
                local r = ro + offsets[i][1]
                local c = co + offsets[i][2]
                board[r][c] = cell
            end
            Refresh()
        end
        return
    end
    
    local newstate = drawstate
    local newblock = 0
    if newstate == 1 then
        -- search blockoffsets for first available block index
        for i = 1, maxblocks do
            if blockoffsets[i] == nil then
                newblock = i
                blockoffsets[newblock] = {}
                break
            end
        end
        if newblock == 0 then
            NoMoreBlocks()
            return
        end
        newstate = newblock
    end
    
    if cell ~= newstate then
        ChangeCell(board, row, col, cell, newstate, newblock > 0)
    end
    
    local prevrow, prevcol = row, col
    local prevx, prevy = x, y
    repeat
        x, y = cv.getxy()
        if x >= 0 and y >= 0 and PointInRect(x, y, boardrect) then
            if x ~= prevx or y ~= prevy then
                -- mouse has moved
                row = 1 + (y - yo) // cellsize
                col = 1 + (x - xo) // cellsize
                if row > numrows then row = numrows end
                if col > numcols then col = numcols end
                if row ~= prevrow or col ~= prevcol then
                    -- mouse has moved to different cell so we need to ensure
                    -- the resulting cells are connected
                    local deltar, deltac
                    if row >= prevrow then deltar = 1 else deltar = -1 end
                    if col >= prevcol then deltac = 1 else deltac = -1 end
                    for r = prevrow, row, deltar do
                        for c = prevcol, col, deltac do
                            cell = board[r][c]
                            if cell ~= newstate then
                                ChangeCell(board, r, c, cell, newstate, newblock > 0)
                            end
                        end
                    end
                    prevrow, prevcol = row, col
                end
                prevx, prevy = x, y
            end
        end
    until glu.getevent():find("^mup")

    if newblock > 0 then
        -- if an identical block already exists then change new block to that number
        -- and free up the slot in blockoffsets
        local clone = FindClone(newblock)
        if clone then
            for r = 1, numrows do
                for c = 1, numcols do
                    if board[r][c] == newblock then board[r][c] = clone end
                end
            end
            blockoffsets[newblock] = nil
            blocklabels[newblock] = nil
            blockcolors[newblock] = nil
        end
    end
end

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

function FindClone(newblock)
    -- blocklabels[newblock] and blockcolors[newblock] should both be nil
    if blocklabels[newblock] then
        error("Bug! blocklabels[newblock] should be nil.")
    elseif blockcolors[newblock] then
        error("Bug! blockcolors[newblock] should be nil.")
    end
    local newoffsets = blockoffsets[newblock]
    for k,offsets in pairs(blockoffsets) do
        if k ~= newblock then
            -- compare offsets
            if #offsets ~= #newoffsets then
                goto no_match
            end
            for i,v in ipairs(offsets) do
                if v[1] ~= newoffsets[i][1] or
                   v[2] ~= newoffsets[i][2] then
                   goto no_match
                end
            end
            -- offsets match so check labels and colors
            if blocklabels[k] or blockcolors[k] then
                goto no_match
            end
            -- we found a clone
            return k
        end
        ::no_match::
    end
    -- no match so return nil
end

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

function GetEditState()
    -- return the current edit state as a string that encodes the puzzle size,
    -- both boards, blockoffsets, blockcolors, and blocklabels
    local state = numrows.."x"..numcols.."\n"
    
    local sboard = GetBoardState(startboard):gsub("\n","/")
    local fboard = GetBoardState(finalboard):gsub("\n","/")
    
    local offsets = ""
    for k,o in pairs(blockoffsets) do
        offsets = offsets..k.."="
        for i = 1, #o do
            offsets = offsets.."{"..o[i][1]..","..o[i][2].."}"
        end
        offsets = offsets.."/"
    end
    
    local colors = ""
    for k,c in pairs(blockcolors) do
        colors = colors..k.."={"..c[1]..","..c[2]..","..c[3].."}".."/"
    end
    
    -- append labels last because we need to terminate each one with \n
    -- (because it's a character that can't appear in a label)
    local labels = ""
    for k,l in pairs(blocklabels) do
        labels = labels..k.."="..l.."\n"
    end

    state = state.."start:"..sboard.."\n"
    state = state.."final:"..fboard.."\n"
    state = state.."offsets:"..offsets.."\n"
    state = state.."colors:"..colors.."\n"
    state = state.."labels:"..labels.."\n"

    return state
end

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

function RestoreEditState(state)
    -- restore the edit state from the given string created by GetEditState
    local rows, cols, sboard, fboard, offsets, colors, labels =
        state:match("^(%d+)x(%d+)\nstart:([^\n]+)\nfinal:([^\n]+)\n"..
                    "offsets:([^\n]*)\ncolors:([^\n]*)\nlabels:(.*)\n$")
    if not (rows and cols and sboard and fboard and
            offsets and colors and labels) then
        print("RestoreEditState:\n"..state)
        error("Bug! Edit state could not be decoded.")
    end
    
    numrows = tonumber(rows)
    numcols = tonumber(cols)

    -- restore boards
    UpdateBoard(startboard, sboard, false, false) -- no Refresh, no sound
    UpdateBoard(finalboard, fboard, false, false) -- ditto
    
    blockoffsets = {}
    if #offsets > 0 then
        -- offsets should be "1={0,0}{1,1}{1,-1}/2={0,0}/3=.../"
        for k, offs in string.gmatch(offsets, "(%d+)=([^/]+)/") do
            blockoffsets[tonumber(k)] = {}
            -- offs should be "{0,0}{1,1}{1,-1}"
            i = 0
            local koffsets = blockoffsets[tonumber(k)]
            for r, c in string.gmatch(offs, "{([-]?%d+),([-]?%d+)}") do
                i = i+1
                koffsets[i] = { tonumber(r), tonumber(c) }
            end
        end
    end
    
    blockcolors = {}
    if #colors > 0 then
        -- colors should be "1={255,0,0}/2={100,100,200}/.../"
        for k, r, g, b in string.gmatch(colors, "(%d+)={(%d+),(%d+),(%d+)}/") do
            blockcolors[tonumber(k)] = { tonumber(r), tonumber(g), tonumber(b), 255 }
        end
    end

    blocklabels = {}
    if #labels > 0 then
        -- labels should be "1=foo\n2=foo bar\n3=...\n"
        for k, label in string.gmatch(labels, "(%d+)=([^\n]+)\n") do
            blocklabels[tonumber(k)] = label
        end
    end
    
    -- caller will do Refresh when required
end

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

function CheckEditState(oldstate)
    if GetEditState() ~= oldstate then
        redoedit = {}
        undoedit[#undoedit+1] = oldstate
        Refresh()
    end
end

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

function HandleClick(event)
    local _, x, y, button, mods = gp.split(event)
    x = tonumber(x)
    y = tonumber(y)
    if button == "left" and mods == "none" then
        if ClickInStyle(x, y) then return end
        if ClickInPuzzles(x, y) then return end
        if ClickInRecent(x, y) then return end
        if ClickInOptions(x, y) then return end
    end
    if PointInRect(x, y, startrect) then
        if editmode then
            local oldstate = GetEditState()
            EditBoard(x, y, button, mods, startboard, xs, ys, startrect)
            CheckEditState(oldstate)
        else
            ClickInBoard(x, y, button, mods, startboard, xs, ys, startrect)
        end
    elseif PointInRect(x, y, finalrect) then
        if editmode then
            local oldstate = GetEditState()
            EditBoard(x, y, button, mods, finalboard, xf, yf, finalrect)
            CheckEditState(oldstate)
        else
            ClickInBoard(x, y, button, mods, finalboard, xf, yf, finalrect)
        end
    end
end

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

function HandleKey(event)
    if     event == "key h none" then       ShowHelp()
    elseif event == "key z none" then       Undo(true, true) -- call Refresh and play sound
    elseif event == "key z shift" then      Redo(true, true) -- ditto
    elseif event == "key return none" then  UndoAll()
    elseif event == "key return shift" then RedoAll()
    elseif event == "key 0 none" then       SetStyle(0)
    elseif event == "key 1 none" then       SetStyle(1)
    elseif event == "key 2 none" then       SetStyle(2)
    elseif event == "key 3 none" then       SetStyle(3)
    elseif event == "key 4 none" then       SetStyle(4)
    elseif event == "key 5 none" then       SetStyle(5)
    elseif event == "key up none" then      SetVolume(volume+0.1)
    elseif event == "key down none" then    SetVolume(volume-0.1)
    elseif event == "key p none" then       ToggleSounds()
    elseif event == "key f none" then       ToggleFastMoves()
    end
end

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

function CheckViewSize()
    local viewwd, viewht = glu.getview()
    if cvwd ~= viewwd or cvht ~= viewht then
        if viewwd < minwd then viewwd = minwd end
        if viewht < minht then viewht = minht end
        glu.setview(viewwd, viewht)
        cvwd = viewwd
        cvht = viewht
        cv.resize()
        SetBoardLocations()
        Refresh()
    end
end

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

local arrow = true
local prevx, prevy

function CheckCursor()
    -- set cursor to pencil if mouse is over startrect or finalrect
    local x, y = cv.getxy()
    if x >= 0 and y >= 0 then
        if x ~= prevx or y ~= prevy then
            -- mouse has moved
            if PointInRect(x, y, startrect) or
               PointInRect(x, y, finalrect) then
                if arrow then
                    cv.cursor("pencil")
                    arrow = false
                end
            elseif not arrow then
                cv.cursor("arrow")
                arrow = true
            end
            prevx, prevy = x, y
        end
    elseif not arrow then
        cv.cursor("arrow")
        arrow = true
    end
end

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

function InitialPuzzle()
    local f = io.open(lastpuzzle, "r")
    if not f then
        NewPuzzle(numrows, numcols)
    else
        f:close()
        if not LoadPuzzle(lastpuzzle) then
            NewPuzzle(numrows, numcols)
        end
    end
    -- Refresh() has been called
end

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

function EventLoop()
    -- tell Glu we can load .txt files via "file" events
    glu.filetypes(".txt")
    while true do
        local event = cp.process(glu.getevent())
        if #event > 0 then
            if event:find("^cclick") then
                HandleClick(event)
            elseif event:find("^key") then
                HandleKey(event)
            elseif event:find("^file") then
                LoadPuzzle(event:sub(6))
            end
        else
            glu.sleep(5)        -- don't hog cpu if idle
            CheckViewSize()     -- check if user resized window
            if editmode then
                CheckCursor()   -- set cursor to arrow or pencil
            end
        end
    end
end

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

function Main()
    glu.setcolor("viewport", table.unpack(bg_color))
    glu.setview(cvwd, cvht)
    cv.create()
    CreateButtons()
    CreatePopUpMenus()
    InitialPuzzle()
    EventLoop()
end

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

ReadSettings()

status, err = xpcall(Main, gp.trace)
if err then glu.continue(err) end
-- the following code is always executed

glu.check(false)
WriteSettings()
cv.delete()
