N-Queens problem

nqueens.lua

-- Programming in Lua, Chapter 10, Page 98

local N = 8

-- Number of solutions up to N=10
local num_solutions = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724}

-- Check whether (row, col) can be attacked by queens
local function isok(queens, row, col)
    for i = 1, row-1 do
        if (queens[i] == col) or
           (queens[i] - (row - i) == col) or
           (queens[i] + (row - i) == col) then
           return false
       end
    end
    return true
end

-- Print board
local function printsolution(queens)
    for i = 1, N do
        for j = 1, N do
            io.write(queens[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

-- Place queen on row
local function addqueen(queens, row)
    if row > N then
        printsolution(queens)
    else
        for col = 1, N do
            if isok(queens, row, col) then
                queens[row] = col
                addqueen(queens, row+1)
            end
        end
    end
end

-- Hooks

local found_solutions = {}

local function count_solutions()
    if debug.getinfo(2, "n").name == "printsolution" then
        found_solutions[N] = (found_solutions[N] or 0) + 1
    end
end

local function_calls = {}

local function count_function_calls()
    local fn = debug.getinfo(2, "n").name
    function_calls[fn] = (function_calls[fn] or 0) + 1
end

debug.sethook(count_function_calls, "c")
addqueen({}, 1)
debug.sethook()
for f, c in pairs(function_calls) do
    print(f .. ": " .. c)
end
assert(function_calls.printsolution == num_solutions[N])