<h3 id="目录">目录</h3>
  1. Eeight Queen
  2. 判断是否可以放置
  3. 递归放置
  4. 只打印第一个值
  5. 排列的方式
  6. 对比

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;">