programming-lua/exercises/ch02/ex2.lua

N = 8 -- board size

-- check whether position (n,c) is free from attacks
local function isplaceok(a, n, c)
    for i = 1, n - 1 do   -- for each queen already placed
        if (a[i] == c) or -- same column?
            (a[i] - i == c - n) or -- same diagonal?
            (a[i] + i == c + n) then -- same diagonal?
            return false  -- place can be attacked
        end
    end
    return true -- no attacks; place is OK
end

-- print a board
local function printsolution(a)
    for i = 1, N do -- for each row
        for j = 1, N do -- and for each column
            -- write "X" or "-" plus a space
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

local function reverse(a, s, e)
    for i = s, e / 2 do
        local counter_i = e - (i - 1)
        local tmp = a[i]
        a[i] = a[counter_i]
        a[counter_i] = tmp
    end
end

local function generatePermutations()
    local p1 = { 1, 2, 3, 4, 5, 6, 7, 8}
    local ps = {p1}

    while true do
        local newP = {}
        local last_p = ps[#ps]
        for i = 1, #last_p do
            newP[i] = last_p[i]
        end

        local k = nil
        for i = #newP, 1, -1 do
            if newP[i + 1] == nil then
                goto continue
            end
            if newP[i] < newP[i + 1] then
                k = i
                break
            end
            ::continue::
        end
        if k == nil then
            break
        end

        local l = nil
        for i = #newP, 1, -1 do
            if newP[k] < newP[i] then
                l = i
                break
            end
        end

        if l == nil then
            print("ERROR: l was nil")
            os.exit(1)
        end

        local tmp = newP[k]
        newP[k] = newP[l]
        newP[l] = tmp

        reverse(newP, k + 1, #newP)

        print(k, l)

        table.insert(ps, newP)
    end

    return ps
end

local perms = generatePermutations()
for i = 1, #perms do
    print(table.unpack(perms[i]))
end

print(#perms)