SudokuLua/sudoku.lua

-- dbg = require ("debugger")
-- dbg.auto_where = 2

function table2string(t)
    local myself = table2string
    local l = {}
    local n = 0
    for k, v in pairs(t) do
        n = n + 1
        if type(v) == "table" then
            l[n] = k .. ': ' .. myself(v)
        elseif type(v) == "string" then
            l[n] = k .. ': ' .. '"' .. v .. '"'
        else
            l[n] = k .. ': ' .. v
        end
    end
    return "{" .. table.concat(l, ", ") .. "}"
end

function find(array, element)
    local index = 0
    for i = 1, #array do
        if array[i] == element then
            index = i
            break
        end
    end
    return index
end

function createEmptyBoard()
    local b = {}
    for i = 1, 9 do
        b[i] = {}
        for j = 1, 9 do
            b[i][j] = 0
        end
    end
    return b
end

function cloneBoard(b)
    local c = {}
    for i = 1, 9 do
        c[i] = {}
        for j = 1, 9 do
            c[i][j] = b[i][j]
        end
    end
    return c
end

function loadBoard(fn)
    local boards = {}
    local r = 0
    local board = {}
    for line in love.filesystem.lines(fn) do
        if line:gsub("%s+", "") == "" then
            table.insert(boards, board)
            board = {}
            r = 0
        else
            r = r + 1
            local c = 0
            board[r] = {}
            for item in line:gmatch("%w+") do
                c = c + 1
                board[r][c] = tonumber(item)
            end
        end
    end
    table.insert(boards, board)
    return boards
end

function saveBoard(fn, b1, b2)
    local f = io.open(fn, "w")
    for row = 1, 9 do
        f:write(table.concat(b1[row], " "))
        f:write("\n")
    end
    f:write("\n")
    for row = 1, 9 do
        f:write(table.concat(b2[row], " "))
        f:write("\n")
    end
    f:close()
end

function showBoard(board)
    for row = 1, 9 do
        print(table.concat(board[row], " "))
    end
end

function checkBoardsEqual(b1, b2)
    for i = 1, 9 do
        for j = 1, 9 do
            if b1[i][j] ~= b2[i][j] then return false end
        end
    end
    return true
end

function iterZones(board)
    local row = 0
    local column = 0
    local block = 0
    return function()
        local a = {}
        local p = {}
        if row < 9 then
            row = row + 1
            for i = 1, 9 do
                a[i] = board[row][i]
                p[i] = {row, i}
            end
            return a, p
        end
        if column < 9 then
            column = column + 1
            for i = 1, 9 do
                a[i] = board[i][column]
                p[i] = {i, column}
            end
            return a, p
        end
        if block < 9 then
            block = block + 1
            local dx = math.floor((block - 1) / 3)
            local dy = (block - 1) % 3
            local n = 0
            for i = 1, 3 do
                for j = 1, 3 do
                    local x = i + 3 * dx
                    local y = j + 3 * dy
                    n = n + 1
                    a[n] = board[x][y]
                    p[n] = {x, y}
                end
            end
            return a, p
        end
    end
end

function checkAUX(zone, pos)
    local isComplete = true
    local ok = true
    local conflictList = {}
    local n = 0
    for i = 1, 8 do
        for j = i+1, 9 do
            if zone[i] == 0 then
                isComplete = false
            elseif zone[i] == zone[j] then
                ok = false
                n = n + 1
                conflictList[n] = {x1=pos[i][1], y1=pos[i][2], x2=pos[j][1], y2=pos[j][2]}
            end
        end
    end
    return ok, isComplete, conflictList
end

function checkBoard(board)
    local ok = true
    local isComplete = true
    local conflictList = {}
    for zone, pos in iterZones(board) do
        local tOk, tIsComplete, tConflictList = checkAUX(zone, pos)
        if not tOk then ok = false end
        if not tIsComplete then isComplete = false end
        for _, conflict in ipairs(tConflictList) do
            table.insert(conflictList, conflict)
        end
    end
    if not ok then isComplete = false end
    return ok, isComplete, conflictList
end

function calCellValidOptions(board, x, y)
    if board[x][y] ~= 0 then return {} end
    local u = {}
    local v = {}
    for i = 1, 9 do
        if board[x][i] ~= 0 then table.insert(u, board[x][i]) end
        if board[i][y] ~= 0 then table.insert(u, board[i][y]) end
    end
    local dx = math.floor((x - 1) / 3) * 3
    local dy = math.floor((y - 1) / 3) * 3
    for i = 1, 3 do
        for j = 1, 3 do
            local a = board[i+dx][j+dy]
            if a ~= 0 then table.insert(u, a) end
        end
    end
    for i = 1, 9 do
        local found = false
        for _, elm in ipairs(u) do
            if elm == i then found = true; break end
        end
        if not found then table.insert(v, i) end
    end
    return v
end

function buildSearchSpace(board)
    local s = {}
    for i = 1, 9 do
        s[i] = {}
        for j = 1, 9 do
            s[i][j] = calCellValidOptions(board, i, j)
        end
    end
    return s
end

function findPairsIndSearchSpace(board, searchSpace)
    local r = {}
    local zoneIndex = 0
    for zone, pos in iterZones(board) do
        zoneIndex = zoneIndex + 1
        for i = 1, 8 do
            local x1 = pos[i][1]
            local y1 = pos[i][2]
            local s1 = searchSpace[x1][y1]
            if #s1 == 2 then
                for j = i + 1, 9 do
                    local x2 = pos[j][1]
                    local y2 = pos[j][2]
                    local s2 = searchSpace[x2][y2]
                    if #s2 == 2 then
                        if s1[1] == s2[1] and s1[2] == s2[2] then
                            -- if zoneIndex <= 18 or x1 ~= x2 and y1 ~= y2 then
                            table.insert(r, {zoneIndex=zoneIndex, cells={i, j}, pair=s1})
                                -- print("----------")
                                -- print("zone: ", zoneIndex)
                                -- print(table2string(zone))
                                -- print(i, j)
                                -- print(table2string(s1))
                            -- end
                        end
                    end
                end
            end
        end
    end
    return r
end

function showSearchSpace(s)
    local hl = ("+-------+-------+-------+-------+-------+-------+-------+-------+-------+")
    print(hl)
    for i = 1, 27 do
        local x = math.floor((i - 1) / 3) + 1
        local a = (i - 1) % 3
        local row = {}
        for j = 1, 27 do
            local y = math.floor((j - 1) / 3) + 1
            local k = ((j - 1) % 3 + 1) + 3 * a
            local found = false
            for _, m in ipairs(s[x][y]) do
                if m == k then found = true; break end
            end
            if found then
                table.insert(row, k)
            else
                table.insert(row, " ")
            end
            if j % 3 == 0 then table.insert(row, "|") end
        end
        print("| "..table.concat(row, " "))
        if i % 3 == 0 then print(hl) end
    end
end

function getZoneByIndex(board, zoneIndex)
    local index = (zoneIndex - 1) % 9 + 1
    local block = math.floor((zoneIndex - 1) / 9) + 1
    local a = {}
    local p = {}
    if block == 1 then
        for i = 1, 9 do
            a[i] = board[index][i]
            p[i] = {index, i}
        end
    elseif block == 2 then
        for i = 1, 9 do
            a[i] = board[i][index]
            p[i] = {index, i}
        end
    elseif block == 3 then
        local dx = math.floor((index - 1) / 3)
        local dy = (index - 1) % 3
        local n = 0
        for i = 1, 3 do
            for j = 1, 3 do
                local x = i + 3 * dx
                local y = j + 3 * dy
                n = n + 1
                a[n] = board[x][y]
                p[n] = {x, y}
            end
        end
    end
    return a, p
end

function getZonePosByIndex(zoneIndex)
    local index = (zoneIndex - 1) % 9 + 1
    local block = math.floor((zoneIndex - 1) / 9) + 1
    local p = {}
    if block == 1 then
        for i = 1, 9 do
            p[i] = {index, i}
        end
    elseif block == 2 then
        for i = 1, 9 do
            p[i] = {index, i}
        end
    elseif block == 3 then
        local dx = math.floor((index - 1) / 3)
        local dy = (index - 1) % 3
        local n = 0
        for i = 1, 3 do
            for j = 1, 3 do
                local x = i + 3 * dx
                local y = j + 3 * dy
                n = n + 1
                p[n] = {x, y}
            end
        end
    end
    return p
end

function iterZonePos(zoneIndex)
    local p = getZonePosByIndex(zoneIndex)
    local i = 0
    return function()
        if i < 9 then
            i = i + 1
            return p[i][1], p[i][2]
        end
    end
end

function fillSingles(board, searchSpace)
    local count = 0
    for i = 1, 9 do
        for j = 1, 9 do
            if #searchSpace[i][j] == 1 then
                board[i][j] = searchSpace[i][j][1]
                count = count + 1
            end
        end
    end
    return count
end

function applyFillSinglesRepeatedly(board, s)
    local s = s or buildSearchSpace(board)
    local count = fillSingles(board, s)
    local total = count
    while count ~= 0 do
        s = buildSearchSpace(board)
        count = fillSingles(board, s)
        total = total + count
    end
    return total
end

function eliminatePairsInSearchSpaceAUX(board, searchSpace, pair, zoneIndex, cells)
    local _, pos = getZoneByIndex(board, zoneIndex)
    local count = 0
    for i = 1, 9 do
        if i ~= cells[1] and i ~= cells[2] then
            local x = pos[i][1]
            local y = pos[i][2]
            local del = {}
            for index, v in ipairs(searchSpace[x][y]) do
                if v == pair[1] or v == pair[2] then
                    count = count + 1
                    table.insert(del, index)
                end
            end
            for _, index in ipairs(del) do
                table.remove(searchSpace[x][y], index)
            end
        end
    end
    return count
end

function eliminatePairsInSearchSpace(board, searchSpace)
    local p = findPairsIndSearchSpace(board, searchSpace)
    local count = 0
    for _, m in ipairs(p) do
        count = count + eliminatePairsInSearchSpaceAUX(board, searchSpace, m.pair, m.zoneIndex, m.cells)
    end
    return count
end

function allPairs(board)
    local s = buildSearchSpace(board)
    applyFillSinglesRepeatedly(board, s)
    eliminatePairsInSearchSpace(board, s)
    local count = applyFillSinglesRepeatedly(board, s)
    while count ~= 0 do
        -- print("--------------------------------------------------")
        -- showBoard(board)
        -- showSearchSpace(s)
        -- print(count)
        -- io.read(1)
        s = buildSearchSpace(board)
        eliminatePairsInSearchSpace(board, s)
        count = applyFillSinglesRepeatedly(board, s)
    end
end

function findFirstEmptyCell(board)
    for i = 1, 9 do
        for j = 1, 9 do
            if board[i][j] == 0 then
                return i, j
            end
        end
    end
end

function checkSearchSpace(board, searchSpace)
    local s = searchSpace or buildSearchSpace(board)
    for i = 1, 9 do
        for j = 1, 9 do
            if board[i][j] == 0 then
                if #s[i][j] == 0 then return false end
            end
        end
    end
    return true
end

function findFirstLeastOption(searchSpace)
    local min = 9
    local x, y
    for i = 1, 9 do
        for j = 1, 9 do
            local len = #searchSpace[i][j]
            if len > 0 and len < min then
                min = len
                x = i
                y = j
            end
        end
    end
    return x, y, min
end

function backTrace(trace)
    while true do
        local currentStep = trace[#trace]
        applyFillSinglesRepeatedly(currentStep.board)
        local ok, finished = checkBoard(currentStep.board)
        if not ok then rollBack(trace); goto endOfTheLoop end
        if finished then return currentStep.board end
        local s = buildSearchSpace(currentStep.board)
        ok = checkSearchSpace(currentStep.board, s)
        if not ok then rollBack(trace); goto endOfTheLoop end
        if not currentStep.pointer then
            local x, y = findFirstLeastOption(s)
            currentStep.options = s[x][y]
            currentStep.pointer = 0
            currentStep.x = x
            currentStep.y = y
        end
        currentStep.pointer = currentStep.pointer + 1
        if currentStep.pointer > #currentStep.options then rollBack(trace); goto endOfTheLoop end
        local nextStep = {}
        nextStep.board = cloneBoard(currentStep.board)
        nextStep.board[currentStep.x][currentStep.y] = currentStep.options[currentStep.pointer]
        trace[#trace+1] = nextStep
    ::endOfTheLoop::
    end
end

function rollBack(trace)
    assert(#trace > 1, "Something is very wrong!")
    table.remove(trace)
end

function solve(board)
    local t = {}
    t[1] = {board=cloneBoard(board),}
    return backTrace(t)
end

return {
    loadBoard = loadBoard,
    cloneBoard = cloneBoard,
    createEmptyBoard = createEmptyBoard,
    calCellValidOptions = calCellValidOptions,
    checkBoard = checkBoard,
    applyFillSinglesRepeatedly = applyFillSinglesRepeatedly,
    showBoard = showBoard,
    checkBoardsEqual = checkBoardsEqual, 
    saveBoard = saveBoard,
    solve = solve,
}