n queens problem

in lua

puzzle

Source Code

``````-- N_Queens problem solving algorithm implementation
-- See: http://en.wikipedia.org/wiki/Eight_queens_puzzle

-- Creates a NxN matrix
local function makeBoard(size)
local board = {}
for i = 1, size do board[i] = {}
for j = 1, size do board[i][j] = false end
end
return board
end

-- Checks if a queen position is legit
local function isAllowed(board, x, y, N)
for i = 1, x - 1 do
local notAllowed = board[i][y]
or (i <= y and board[x - i][y  -i])
or (y + i <= N and board[x - i][y + i])
if notAllowed then return false end
end
return true
end

-- Solves recursively the N_Queens puzzle
local function solve(board, x, N)
for y = 1, N do
if isAllowed(board, x, y, N) then
board[x][y] = true
if x == N or solve(board, x + 1, N) then return true end
board[x][y] = false
end
end
return false
end

-- N-Queens puzzle solving function
-- N      : the problem size
-- return : a NxN matrix of booleans,
--    true matches a queen position
local function queens(N)
board = makeBoard(N)
local solved = solve(board, 1, N)
return board
end

return queens
``````
``````-- Tests for nqueens.lua
local nqueens = require 'nqueens'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Compares two grids
local function same(t1, t2)
for k, row in ipairs(t1) do
for line, v in ipairs(row) do
if v ~= t2[k][line] then return false end
end
end
return true
end

-- A 8-Queens solution
local queens8 = {
{true, false, false, false, false, false, false, false},
{false, false, false, false, true, false, false, false},
{false, false, false, false, false, false, false, true},
{false, false, false, false, false, true, false, false},
{false, false, true, false, false, false, false, false},
{false, false, false, false, false, false, true, false},
{false, true, false, false, false, false, false, false},
{false, false, false, true, false, false, false, false},
}

run('NQueens test', function()
assert(same(nqueens(8), queens8))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````