<h3 id="目录">目录</h3>
- Eeight Queen
- 判断是否可以放置
- 递归放置
- 只打印第一个值
- 排列的方式
- 对比
Eight Queen
8皇后问题： 在一个8*8的棋盘上放置八个皇后，她们之间相互不能影响。 通过一个表来存储，键值表示行，值表示列。
判断是否可以放置
因为键值已经保证不会再同一行，所以我们需要判断的就只有列和斜方向的。 在斜方向，左斜和右斜。右斜列减行相同则同处一斜行。左斜行列相加则处于同斜行。
1
2
3
4
5
6
7
8
9
10
local function checkAttack(table, n, c)
for i = 1, n - 1 do
if (table[i] == c) or
(table[i] - i == c - n) or --行列式
(table[i] + i == c + n) then
return false
end
end
return true
end
递归放置
通过判断是否每一行都放置了棋子来决定是否打印这个棋谱。 在addQueen中，每一个节点都会一直的递归，所有的节点递归结束。 当然在中间不满足条件的后面的节点就不会递归了。
1
2
3
4
5
6
7
8
9
10
11
12
local function addQueen(table, n)
if n > N then
printTable(table)
else
for c = 1, N do
if checkAttack(table, n, c) then
table[n] = c
addQueen(table, n + 1)
end
end
end
end
只打印第一个值
在addQueen前面加一个判断，如果打印了一个可行解就不再进行冗余递归了。
排列的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
---@param t table|number
local function deepCopy(t)
local result = {}
if type(t) == "number" then
table.insert(t, 1, t)
else
for i, v in ipairs(t) do
result[i] = t[i]
end
end
return result
end
—@param table table
—@param n number
—return table
local function insertNumber(t, n)
local result = {}
for i = 1, #t + 1 do
result[i] = deepCopy(t)
table.insert(result[i], i, n)
end
return result
end
—@param t1 table
—@param t2 table
—@return table
local function mergeTable(t1, t2)
local length = #t1
for i = 1, #t2 do
table.insert(t1, length + i, t2[i])
end
end
—@param table table
—@param n number
—@return table
local function arrangement(t, n)
local temp = {}
for i = 1, #t do
local tt = insertNumber(t[i], n)
mergeTable(temp, tt)
end
return temp
end
local function getArrangement()
local table = { { 1, 2 }, { 2, 1 } }
for i = 3, N do
table = arrangement(table, i)
end
return table
end
local tr = getArrangement()
for i, v in ipairs(tr) do
local flag = true
for j, k in ipairs(v) do
if not checkAttack(v, j, k) then
flag = false
break
end
end
if flag then
printTable(v)
end
end
print(“Total number:”, #tr)
print(“Total answer2:” … totalResult)
print(“Method2 time:”, os.clock() - t1)
对比
方法2：排列花费1.604秒，检测花费将近1.1秒，这说明排列还是浪费了很多时间在检测和排列上面的。
<hr style="visibility: hidden;">