Lua 学习 chapter2

chapter2

Posted by Jow on April 22, 2019

目录

  1. Eeight Queen
  2. 判断是否可以放置
  3. 递归放置
  4. 只打印第一个值
  5. 排列的方式
  6. 对比

Love is you power, chek your power, and try your best.

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秒,这说明排列还是浪费了很多时间在检测和排列上面的。