Python是一種流行的編程語言,其有許多優秀的解決問題的算法。其中,N皇后問題指在NxN的棋盤上放置N個皇后,且每個皇后不能在同一行、同一列或同一對角線上。使用Python可以很輕松地解決這個問題。
def is_valid(board, row, col): # 檢查當前位置的列是否已經存在皇后 for i in range(row): if board[i] == col: return False # 檢查當前位置左上方是否存在皇后 i = row - 1 j = col - 1 while i >= 0 and j >= 0: if board[i] == j: return False i -= 1 j -= 1 # 檢查當前位置右上方是否存在皇后 i = row - 1 j = col + 1 while i >= 0 and j< len(board): if board[i] == j: return False i -= 1 j += 1 return True def solve_n_queens(n): result = [] def dfs(row, board): if row == n: result.append(board[:]) return for col in range(n): if is_valid(board, row, col): board[row] = col dfs(row + 1, board) board[row] = -1 dfs(0, [-1] * n) return result solutions = solve_n_queens(4) for solution in solutions: print(solution)
上述代碼中,我們通過構建 is_valid 函數來判斷每個皇后的位置是否合法。通過 dfs 函數不斷遞歸生成每一種解法,最終得到所有的解法。最后我們遍歷所有解法并打印出來。
上一篇oracle 加鎖
下一篇python的qt框架