2 小插曲：八皇后问题

在给出的程序的基础上加上了我自己理解的一些注释

--file = io.open("eight_queen_result.txt", "w")
--io.output(file)

N = 8   --棋盘大小

--在a[i] = j 的情况下 i是行号 j是列号 即第i行的棋子被放在第j列
function isplaceok(a, n, c)         --a为棋盘 n为当前要放置的皇后的行号 c为需要判定的列
    for i = 1, n -1 do              --对于每个已经放置的皇后
        if(a[i] == c) or            --有没有皇后在此列上
        (a[i] - i == c - n) or      --该元素的主对角线上有没有其他皇后
        (a[i] + i == c + n) then    --该元素的次对角线上有没有其他皇后
            return false
        end
    end
    return true
end

function printsolution(a)
    for i = 1, N do
        for j = 1, N do
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

function addqueen(a, n)
    if n > N then
        printsolution(a)
        --os.exit()
    else
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c
                addqueen(a, n + 1)
            end
        end
    end
end

addqueen({}, 1)

--io.close(file)

运行结果很长就不在此展示了，由于直接打印在命令行中不易观看，我在开头和结尾保留了部分代码可以输出到文本文件中查看。

2.1 练习

练习 2.1：修改八皇后问题的程序，使其在输出第一个解后即停止运行。

在Lua 语言入门的 1.1 节中，我们提到可以使用os.exit()来快速退出交互模式，在此处的退出程序也依然适用（简书并没有提供锚点的相关功能所以不能在链接中直接定位到相应位置，需要稍微找一下）。
我已在addqueen(a, n)中的相应位置添加了代码并注释掉，不影响运行，需要测试本题结果可以自行去掉注释。

练习 2.2：解决八皇后问题的另一种方式是，先生成1~8之间的所有排列，然后依次遍历这些排列，检查每一个排列是否是八皇后问题的有效解。请使用这种方法修改程序，并对比新程序与旧程序之间的性能差异（提示，比较调用isplaceok()函数的次数）。

生成全排列就是用八个for循环逐一检测每一个棋子是否合适。由于本题目要求判定函数不能改，所以需要修改一下调用方式。代码如下：

N = 8
count = 0
index = {1, 1, 1, 1, 1, 1, 1, 1}    -- 取一个表来存第n行的棋子放在哪一列

function isplaceok(a, n, c)
    count = count + 1
    for i = 1, n -1 do
        if(a[i] == c) or
        (a[i] - i == c - n) or
        (a[i] + i == c + n) then
            return false
        end
    end
    return true
end


function Queen(a)
    repeat
        repeat
            repeat
                repeat
                    repeat
                        repeat
                            repeat
                                repeat
                                    for d = 1, N do     --多一个循环用来赋值
                                        a[d] = index[d]
                                    end
                                    for n = 1, N do     --用来判断每一个棋子位置是否合适
                                        if not isplaceok(a, n, index[n]) then
                                            break
                                        end
                                    end
                                    index[8] = index[8] + 1
                                until(index[8] > N)
                            index[8] = 1
                            index[7] = index[7] + 1
                            until(index[7] > N)
                        index[8] = 1
                        index[7] = 1
                        index[6] = index[6] + 1
                        until(index[6] > N)
                    index[8] = 1
                    index[7] = 1
                    index[6] = 1
                    index[5] = index[5] + 1
                    until(index[5] > N)
                index[8] = 1
                index[7] = 1
                index[6] = 1
                index[5] = 1
                index[4] = index[4] + 1
                until(index[4] > N)
            index[8] = 1
            index[7] = 1
            index[6] = 1
            index[5] = 1
            index[4] = 1
            index[3] = index[3] + 1
            until(index[3] > N)
        index[8] = 1
        index[7] = 1
        index[6] = 1
        index[5] = 1
        index[4] = 1
        index[3] = 1
        index[2] = index[2] + 1
        until(index[2] > N)
    index[8] = 1
    index[7] = 1
    index[6] = 1
    index[5] = 1
    index[4] = 1
    index[3] = 1
    index[2] = 1
    index[1] = index[1] + 1
    until(index[1] > N)
end

Queen({})
print(count)

之所以使用repeat不使用for，是因为index表中下表和for循环起始值的识别存在歧义for index[1] = 1编译器似乎不能识别是哪个数字作为循环起始值，我一时想不到如何解决，只好用笨方法自己做循环赋值。
第一种方法的结果是：15720
第二种方法的结果是：50889536
后者是前者的约3237倍，性能还是差很多的

最后编辑于：2020.07.22 10:49:57