八皇后问题的Julia实现

问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？

尝试使用Julia实现一个回溯解：

实现

回溯法进行暴力查找：

function find_safe_coord(board::Array{Int}, curr_row, n; trace_back=false)
    start = 1
    if trace_back
        start = board[curr_row] + 1
    end
    for col = start : n
        has_menace = false
        for row = 1 : curr_row - 1
            prev = board[row]
            if prev == col || curr_row - row  == abs(col - prev)
                has_menace = true
            end
        end
        !has_menace && return col
    end
    nothing
end

function n_queens_puzzle(n)
    board = zeros(Int, n)
    curr_row = 1
    while curr_row <= n
        coord = find_safe_coord(board, curr_row, n)
        if coord != nothing
            board[curr_row] = coord
            curr_row == n && produce(copy(board))
        end
        if coord == nothing || curr_row == n
            while true
                curr_row -= 1
                curr_row == 0 && return produce(nothing)
                coord = find_safe_coord(board, curr_row, n, trace_back=true)
                if coord != nothing
                    board[curr_row] = coord
                    break
                end
            end
        end
        curr_row += 1
    end
end

# 逐行输出[x,y]
solutions = @task n_queens_puzzle(8)
for solution in solutions
    if solution != nothing
        for row in eachindex(solution)
            print("[$row,$(solution[row])] ")
        end
        println()
    end
end

function find_safe_coord(board::Array{Int}, curr_row, n; trace_back=false)

start = 1

if trace_back

start = board[curr_row] + 1

end

for col = start : n

has_menace = false

for row = 1 : curr_row - 1

prev = board[row]

if prev == col || curr_row - row == abs(col - prev)

has_menace = true

end

!has_menace && return col

end

nothing

end

function n_queens_puzzle(n)

board = zeros(Int, n)

curr_row = 1

while curr_row <= n

coord = find_safe_coord(board, curr_row, n)

if coord != nothing

board[curr_row] = coord

curr_row == n && produce(copy(board))

end

if coord == nothing || curr_row == n

while true

curr_row -= 1

curr_row == 0 && return produce(nothing)

coord = find_safe_coord(board, curr_row, n, trace_back=true)

if coord != nothing

board[curr_row] = coord

break

end

curr_row += 1

end

# 逐行输出[x,y]

solutions = @task n_queens_puzzle(8)

for solution in solutions

if solution != nothing

for row in eachindex(solution)

print("[$row,$(solution[row])] ")

end

println()

end

很可惜，我的代码高亮插件不支持Julia的语法 🙁

输出

[1,1] [2,5] [3,8] [4,6] [5,3] [6,7] [7,2] [8,4]
[1,1] [2,6] [3,8] [4,3] [5,7] [6,4] [7,2] [8,5]
[1,1] [2,7] [3,4] [4,6] [5,8] [6,2] [7,5] [8,3]
[1,1] [2,7] [3,5] [4,8] [5,2] [6,4] [7,6] [8,3]
[1,2] [2,4] [3,6] [4,8] [5,3] [6,1] [7,7] [8,5]
[1,2] [2,5] [3,7] [4,1] [5,3] [6,8] [7,6] [8,4]
[1,2] [2,5] [3,7] [4,4] [5,1] [6,8] [7,6] [8,3]
[1,2] [2,6] [3,1] [4,7] [5,4] [6,8] [7,3] [8,5]
[1,2] [2,6] [3,8] [4,3] [5,1] [6,4] [7,7] [8,5]
[1,2] [2,7] [3,3] [4,6] [5,8] [6,5] [7,1] [8,4]
[1,2] [2,7] [3,5] [4,8] [5,1] [6,4] [7,6] [8,3]
[1,2] [2,8] [3,6] [4,1] [5,3] [6,5] [7,7] [8,4]
[1,3] [2,1] [3,7] [4,5] [5,8] [6,2] [7,4] [8,6]
[1,3] [2,5] [3,2] [4,8] [5,1] [6,7] [7,4] [8,6]
[1,3] [2,5] [3,2] [4,8] [5,6] [6,4] [7,7] [8,1]
[1,3] [2,5] [3,7] [4,1] [5,4] [6,2] [7,8] [8,6]
[1,3] [2,5] [3,8] [4,4] [5,1] [6,7] [7,2] [8,6]
[1,3] [2,6] [3,2] [4,5] [5,8] [6,1] [7,7] [8,4]
[1,3] [2,6] [3,2] [4,7] [5,1] [6,4] [7,8] [8,5]
[1,3] [2,6] [3,2] [4,7] [5,5] [6,1] [7,8] [8,4]
[1,3] [2,6] [3,4] [4,1] [5,8] [6,5] [7,7] [8,2]
[1,3] [2,6] [3,4] [4,2] [5,8] [6,5] [7,7] [8,1]
[1,3] [2,6] [3,8] [4,1] [5,4] [6,7] [7,5] [8,2]
[1,3] [2,6] [3,8] [4,1] [5,5] [6,7] [7,2] [8,4]
[1,3] [2,6] [3,8] [4,2] [5,4] [6,1] [7,7] [8,5]
[1,3] [2,7] [3,2] [4,8] [5,5] [6,1] [7,4] [8,6]
[1,3] [2,7] [3,2] [4,8] [5,6] [6,4] [7,1] [8,5]
[1,3] [2,8] [3,4] [4,7] [5,1] [6,6] [7,2] [8,5]
[1,4] [2,1] [3,5] [4,8] [5,2] [6,7] [7,3] [8,6]
[1,4] [2,1] [3,5] [4,8] [5,6] [6,3] [7,7] [8,2]
[1,4] [2,2] [3,5] [4,8] [5,6] [6,1] [7,3] [8,7]
[1,4] [2,2] [3,7] [4,3] [5,6] [6,8] [7,1] [8,5]
[1,4] [2,2] [3,7] [4,3] [5,6] [6,8] [7,5] [8,1]
[1,4] [2,2] [3,7] [4,5] [5,1] [6,8] [7,6] [8,3]
[1,4] [2,2] [3,8] [4,5] [5,7] [6,1] [7,3] [8,6]
[1,4] [2,2] [3,8] [4,6] [5,1] [6,3] [7,5] [8,7]
[1,4] [2,6] [3,1] [4,5] [5,2] [6,8] [7,3] [8,7]
[1,4] [2,6] [3,8] [4,2] [5,7] [6,1] [7,3] [8,5]
[1,4] [2,6] [3,8] [4,3] [5,1] [6,7] [7,5] [8,2]
[1,4] [2,7] [3,1] [4,8] [5,5] [6,2] [7,6] [8,3]
[1,4] [2,7] [3,3] [4,8] [5,2] [6,5] [7,1] [8,6]
[1,4] [2,7] [3,5] [4,2] [5,6] [6,1] [7,3] [8,8]
[1,4] [2,7] [3,5] [4,3] [5,1] [6,6] [7,8] [8,2]
[1,4] [2,8] [3,1] [4,3] [5,6] [6,2] [7,7] [8,5]
[1,4] [2,8] [3,1] [4,5] [5,7] [6,2] [7,6] [8,3]
[1,4] [2,8] [3,5] [4,3] [5,1] [6,7] [7,2] [8,6]
[1,5] [2,1] [3,4] [4,6] [5,8] [6,2] [7,7] [8,3]
[1,5] [2,1] [3,8] [4,4] [5,2] [6,7] [7,3] [8,6]
[1,5] [2,1] [3,8] [4,6] [5,3] [6,7] [7,2] [8,4]
[1,5] [2,2] [3,4] [4,6] [5,8] [6,3] [7,1] [8,7]
[1,5] [2,2] [3,4] [4,7] [5,3] [6,8] [7,6] [8,1]
[1,5] [2,2] [3,6] [4,1] [5,7] [6,4] [7,8] [8,3]
[1,5] [2,2] [3,8] [4,1] [5,4] [6,7] [7,3] [8,6]
[1,5] [2,3] [3,1] [4,6] [5,8] [6,2] [7,4] [8,7]
[1,5] [2,3] [3,1] [4,7] [5,2] [6,8] [7,6] [8,4]
[1,5] [2,3] [3,8] [4,4] [5,7] [6,1] [7,6] [8,2]
[1,5] [2,7] [3,1] [4,3] [5,8] [6,6] [7,4] [8,2]
[1,5] [2,7] [3,1] [4,4] [5,2] [6,8] [7,6] [8,3]
[1,5] [2,7] [3,2] [4,4] [5,8] [6,1] [7,3] [8,6]
[1,5] [2,7] [3,2] [4,6] [5,3] [6,1] [7,4] [8,8]
[1,5] [2,7] [3,2] [4,6] [5,3] [6,1] [7,8] [8,4]
[1,5] [2,7] [3,4] [4,1] [5,3] [6,8] [7,6] [8,2]
[1,5] [2,8] [3,4] [4,1] [5,3] [6,6] [7,2] [8,7]
[1,5] [2,8] [3,4] [4,1] [5,7] [6,2] [7,6] [8,3]
[1,6] [2,1] [3,5] [4,2] [5,8] [6,3] [7,7] [8,4]
[1,6] [2,2] [3,7] [4,1] [5,3] [6,5] [7,8] [8,4]
[1,6] [2,2] [3,7] [4,1] [5,4] [6,8] [7,5] [8,3]
[1,6] [2,3] [3,1] [4,7] [5,5] [6,8] [7,2] [8,4]
[1,6] [2,3] [3,1] [4,8] [5,4] [6,2] [7,7] [8,5]
[1,6] [2,3] [3,1] [4,8] [5,5] [6,2] [7,4] [8,7]
[1,6] [2,3] [3,5] [4,7] [5,1] [6,4] [7,2] [8,8]
[1,6] [2,3] [3,5] [4,8] [5,1] [6,4] [7,2] [8,7]
[1,6] [2,3] [3,7] [4,2] [5,4] [6,8] [7,1] [8,5]
[1,6] [2,3] [3,7] [4,2] [5,8] [6,5] [7,1] [8,4]
[1,6] [2,3] [3,7] [4,4] [5,1] [6,8] [7,2] [8,5]
[1,6] [2,4] [3,1] [4,5] [5,8] [6,2] [7,7] [8,3]
[1,6] [2,4] [3,2] [4,8] [5,5] [6,7] [7,1] [8,3]
[1,6] [2,4] [3,7] [4,1] [5,3] [6,5] [7,2] [8,8]
[1,6] [2,4] [3,7] [4,1] [5,8] [6,2] [7,5] [8,3]
[1,6] [2,8] [3,2] [4,4] [5,1] [6,7] [7,5] [8,3]
[1,7] [2,1] [3,3] [4,8] [5,6] [6,4] [7,2] [8,5]
[1,7] [2,2] [3,4] [4,1] [5,8] [6,5] [7,3] [8,6]
[1,7] [2,2] [3,6] [4,3] [5,1] [6,4] [7,8] [8,5]
[1,7] [2,3] [3,1] [4,6] [5,8] [6,5] [7,2] [8,4]
[1,7] [2,3] [3,8] [4,2] [5,5] [6,1] [7,6] [8,4]
[1,7] [2,4] [3,2] [4,5] [5,8] [6,1] [7,3] [8,6]
[1,7] [2,4] [3,2] [4,8] [5,6] [6,1] [7,3] [8,5]
[1,7] [2,5] [3,3] [4,1] [5,6] [6,8] [7,2] [8,4]
[1,8] [2,2] [3,4] [4,1] [5,7] [6,5] [7,3] [8,6]
[1,8] [2,2] [3,5] [4,3] [5,1] [6,7] [7,4] [8,6]
[1,8] [2,3] [3,1] [4,6] [5,2] [6,5] [7,7] [8,4]
[1,8] [2,4] [3,1] [4,3] [5,6] [6,2] [7,7] [8,5]

[1,1] [2,5] [3,8] [4,6] [5,3] [6,7] [7,2] [8,4]

[1,1] [2,6] [3,8] [4,3] [5,7] [6,4] [7,2] [8,5]

[1,1] [2,7] [3,4] [4,6] [5,8] [6,2] [7,5] [8,3]

[1,1] [2,7] [3,5] [4,8] [5,2] [6,4] [7,6] [8,3]

[1,2] [2,4] [3,6] [4,8] [5,3] [6,1] [7,7] [8,5]

[1,2] [2,5] [3,7] [4,1] [5,3] [6,8] [7,6] [8,4]

[1,2] [2,5] [3,7] [4,4] [5,1] [6,8] [7,6] [8,3]

[1,2] [2,6] [3,1] [4,7] [5,4] [6,8] [7,3] [8,5]

[1,2] [2,6] [3,8] [4,3] [5,1] [6,4] [7,7] [8,5]

[1,2] [2,7] [3,3] [4,6] [5,8] [6,5] [7,1] [8,4]

[1,2] [2,7] [3,5] [4,8] [5,1] [6,4] [7,6] [8,3]

[1,2] [2,8] [3,6] [4,1] [5,3] [6,5] [7,7] [8,4]

[1,3] [2,1] [3,7] [4,5] [5,8] [6,2] [7,4] [8,6]

[1,3] [2,5] [3,2] [4,8] [5,1] [6,7] [7,4] [8,6]

[1,3] [2,5] [3,2] [4,8] [5,6] [6,4] [7,7] [8,1]

[1,3] [2,5] [3,7] [4,1] [5,4] [6,2] [7,8] [8,6]

[1,3] [2,5] [3,8] [4,4] [5,1] [6,7] [7,2] [8,6]

[1,3] [2,6] [3,2] [4,5] [5,8] [6,1] [7,7] [8,4]

[1,3] [2,6] [3,2] [4,7] [5,1] [6,4] [7,8] [8,5]

[1,3] [2,6] [3,2] [4,7] [5,5] [6,1] [7,8] [8,4]

[1,3] [2,6] [3,4] [4,1] [5,8] [6,5] [7,7] [8,2]

[1,3] [2,6] [3,4] [4,2] [5,8] [6,5] [7,7] [8,1]

[1,3] [2,6] [3,8] [4,1] [5,4] [6,7] [7,5] [8,2]

[1,3] [2,6] [3,8] [4,1] [5,5] [6,7] [7,2] [8,4]

[1,3] [2,6] [3,8] [4,2] [5,4] [6,1] [7,7] [8,5]

[1,3] [2,7] [3,2] [4,8] [5,5] [6,1] [7,4] [8,6]

[1,3] [2,7] [3,2] [4,8] [5,6] [6,4] [7,1] [8,5]

[1,3] [2,8] [3,4] [4,7] [5,1] [6,6] [7,2] [8,5]

[1,4] [2,1] [3,5] [4,8] [5,2] [6,7] [7,3] [8,6]

[1,4] [2,1] [3,5] [4,8] [5,6] [6,3] [7,7] [8,2]

[1,4] [2,2] [3,5] [4,8] [5,6] [6,1] [7,3] [8,7]

[1,4] [2,2] [3,7] [4,3] [5,6] [6,8] [7,1] [8,5]

[1,4] [2,2] [3,7] [4,3] [5,6] [6,8] [7,5] [8,1]

[1,4] [2,2] [3,7] [4,5] [5,1] [6,8] [7,6] [8,3]

[1,4] [2,2] [3,8] [4,5] [5,7] [6,1] [7,3] [8,6]

[1,4] [2,2] [3,8] [4,6] [5,1] [6,3] [7,5] [8,7]

[1,4] [2,6] [3,1] [4,5] [5,2] [6,8] [7,3] [8,7]

[1,4] [2,6] [3,8] [4,2] [5,7] [6,1] [7,3] [8,5]

[1,4] [2,6] [3,8] [4,3] [5,1] [6,7] [7,5] [8,2]

[1,4] [2,7] [3,1] [4,8] [5,5] [6,2] [7,6] [8,3]

[1,4] [2,7] [3,3] [4,8] [5,2] [6,5] [7,1] [8,6]

[1,4] [2,7] [3,5] [4,2] [5,6] [6,1] [7,3] [8,8]

[1,4] [2,7] [3,5] [4,3] [5,1] [6,6] [7,8] [8,2]

[1,4] [2,8] [3,1] [4,3] [5,6] [6,2] [7,7] [8,5]

[1,4] [2,8] [3,1] [4,5] [5,7] [6,2] [7,6] [8,3]

[1,4] [2,8] [3,5] [4,3] [5,1] [6,7] [7,2] [8,6]

[1,5] [2,1] [3,4] [4,6] [5,8] [6,2] [7,7] [8,3]

[1,5] [2,1] [3,8] [4,4] [5,2] [6,7] [7,3] [8,6]

[1,5] [2,1] [3,8] [4,6] [5,3] [6,7] [7,2] [8,4]

[1,5] [2,2] [3,4] [4,6] [5,8] [6,3] [7,1] [8,7]

[1,5] [2,2] [3,4] [4,7] [5,3] [6,8] [7,6] [8,1]

[1,5] [2,2] [3,6] [4,1] [5,7] [6,4] [7,8] [8,3]

[1,5] [2,2] [3,8] [4,1] [5,4] [6,7] [7,3] [8,6]

[1,5] [2,3] [3,1] [4,6] [5,8] [6,2] [7,4] [8,7]

[1,5] [2,3] [3,1] [4,7] [5,2] [6,8] [7,6] [8,4]

[1,5] [2,3] [3,8] [4,4] [5,7] [6,1] [7,6] [8,2]

[1,5] [2,7] [3,1] [4,3] [5,8] [6,6] [7,4] [8,2]

[1,5] [2,7] [3,1] [4,4] [5,2] [6,8] [7,6] [8,3]

[1,5] [2,7] [3,2] [4,4] [5,8] [6,1] [7,3] [8,6]

[1,5] [2,7] [3,2] [4,6] [5,3] [6,1] [7,4] [8,8]

[1,5] [2,7] [3,2] [4,6] [5,3] [6,1] [7,8] [8,4]

[1,5] [2,7] [3,4] [4,1] [5,3] [6,8] [7,6] [8,2]

[1,5] [2,8] [3,4] [4,1] [5,3] [6,6] [7,2] [8,7]

[1,5] [2,8] [3,4] [4,1] [5,7] [6,2] [7,6] [8,3]

[1,6] [2,1] [3,5] [4,2] [5,8] [6,3] [7,7] [8,4]

[1,6] [2,2] [3,7] [4,1] [5,3] [6,5] [7,8] [8,4]

[1,6] [2,2] [3,7] [4,1] [5,4] [6,8] [7,5] [8,3]

[1,6] [2,3] [3,1] [4,7] [5,5] [6,8] [7,2] [8,4]

[1,6] [2,3] [3,1] [4,8] [5,4] [6,2] [7,7] [8,5]

[1,6] [2,3] [3,1] [4,8] [5,5] [6,2] [7,4] [8,7]

[1,6] [2,3] [3,5] [4,7] [5,1] [6,4] [7,2] [8,8]

[1,6] [2,3] [3,5] [4,8] [5,1] [6,4] [7,2] [8,7]

[1,6] [2,3] [3,7] [4,2] [5,4] [6,8] [7,1] [8,5]

[1,6] [2,3] [3,7] [4,2] [5,8] [6,5] [7,1] [8,4]

[1,6] [2,3] [3,7] [4,4] [5,1] [6,8] [7,2] [8,5]

[1,6] [2,4] [3,1] [4,5] [5,8] [6,2] [7,7] [8,3]

[1,6] [2,4] [3,2] [4,8] [5,5] [6,7] [7,1] [8,3]

[1,6] [2,4] [3,7] [4,1] [5,3] [6,5] [7,2] [8,8]

[1,6] [2,4] [3,7] [4,1] [5,8] [6,2] [7,5] [8,3]

[1,6] [2,8] [3,2] [4,4] [5,1] [6,7] [7,5] [8,3]

[1,7] [2,1] [3,3] [4,8] [5,6] [6,4] [7,2] [8,5]

[1,7] [2,2] [3,4] [4,1] [5,8] [6,5] [7,3] [8,6]

[1,7] [2,2] [3,6] [4,3] [5,1] [6,4] [7,8] [8,5]

[1,7] [2,3] [3,1] [4,6] [5,8] [6,5] [7,2] [8,4]

[1,7] [2,3] [3,8] [4,2] [5,5] [6,1] [7,6] [8,4]

[1,7] [2,4] [3,2] [4,5] [5,8] [6,1] [7,3] [8,6]

[1,7] [2,4] [3,2] [4,8] [5,6] [6,1] [7,3] [8,5]

[1,7] [2,5] [3,3] [4,1] [5,6] [6,8] [7,2] [8,4]

[1,8] [2,2] [3,4] [4,1] [5,7] [6,5] [7,3] [8,6]

[1,8] [2,2] [3,5] [4,3] [5,1] [6,7] [7,4] [8,6]

[1,8] [2,3] [3,1] [4,6] [5,2] [6,5] [7,7] [8,4]

[1,8] [2,4] [3,1] [4,3] [5,6] [6,2] [7,7] [8,5]

打赏作者

您的支持将激励我继续创作！

去打赏

Mo Ye

A Conservative

Published

December 25, 2016

Mo Ye in Algorithm | December 25, 2016

八皇后问题的Julia实现

问题

实现

输出

Mo Ye

A Conservative

Published

December 25, 2016

Cancel Reply

Write a Comment