95 lines
2.0 KiB
Lua
95 lines
2.0 KiB
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)
|