lua解决八皇后问题

渴望飞翔的猪

发布于 2022-07-17 10:47:28

2540

发布于 2022-07-17 10:47:28

文章被收录于专栏：葵花宝典007

项目写了一年的游戏逻辑脚本，发现算法知识有待加强，正好今天1024节日，打算练习下算法，于是查看了经典的把皇后问题,思路是不难，只是发现以前的c语言都不会写了，编译出很多问题，才发现用脚本语言开发的效率和快速，感觉算法这东西重在思想，c语言很多编译的细节错误可能找半天发现才是某个i，j写错了（对于初级的我经常犯这错误），可是用脚本语言就很简单，或者说是很方便查找这个问题，对于编译型语言，有时候因为这个低级错误可能出来的报错信息都够你查个半天。。。最后还是用lua写起来快速实现了

local QUEENS_NUM = 8
local queens = {}
for i = 1,QUEENS_NUM do
    queens[i] = {}
    for j = 1,QUEENS_NUM do
        queens[i][j] = 0
    end
end
count = 0

function PrintResult()
    for i=1,QUEENS_NUM do
        for j = 1,QUEENS_NUM do
            io.write(queens[i][j].." ")
        end
            io.write("\n")
    end
    print("====================================")
end
function CheckValid(row,column)
    if row == 1 then
        return true
    end 

    -- 检查列
    for i=1,row-1 do
        if queens[i][column] == 1 then
            return false
        end 
    end 

    local _i = 0 
    -- 斜向 左上角 和右上角
    for i=row-1,1,-1 do
        _i = _i + 1 
        if column - _i >= 1 and queens[i][column-_i] == 1 then
            return false
        end 
        if column + _i <= QUEENS_NUM and queens[i][column+_i] == 1 then
            return false
        end
    end

    return true
end 
function Solve(row)
    if row == QUEENS_NUM+1 then
        PrintResult()
        count = count + 1
        return
    end
    for i=1,QUEENS_NUM do
        if CheckValid(row,i) then
            queens[row][i] = 1
            Solve(row+1)
        end
        queens[row][i] = 0
    end
end

Solve(1)
print("count_result="..count)

总共92种解，感觉到了以前用c学算法的效率低下啊，不过对于学c这种静态语言对于了解程序的底层实现是很有帮助的。所以脚本在性能方面也远不及c,c++等系列语言啦，不过对于实际上的开发效率来说，脚本语言的优势还是大大的

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法