问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？
尝试使用Julia实现一个回溯解：
实现
回溯法进行暴力查找：
|
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 |
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 |
很可惜，我[……]
RSS Feed