lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


And the eight queens problem... (any board size)

--
Wim


local maxrow = 8

if arg[1] then
	maxrow = tonumber(arg[1])
	if not maxrow or maxrow <= 0 then
		print(arg[0] .. [[ [size]

Print a board of requested size (default is 8) with
queens on each row that do non attack each other
(if possible at all).]])
		return
	end
end

local rows = {}

local function place(n, pos)
	rows[n] = nil
	for i, p in ipairs(rows) do
		if p == pos or p - pos  == n - i or pos - p == n - i then
			return false
		end
	end
	rows[n] = pos
	return true
end

local function proceed(n)
	if n > maxrow then
		return true
	end

	for pos = 1, maxrow do
		if place(n, pos) and proceed(n + 1) then
			return true
		end
	end
end

if proceed(1) then
	for _, pos in ipairs(rows) do
		print(string.rep('.', pos - 1) .. 'Q' .. string.rep('.', maxrow - pos))
	end
else
	print("No solution for board size " .. maxrow .. "!")
end