NQueens package

概述

N-Queens問題是在編程訪談和學術環境中經常遇到的經典挑戰。面臨的挑戰是將N皇后放在N×N棋盤上，以至於沒有兩個皇后互相威脅。這意味著沒有兩個皇后可以共享同一行，列或對角線。

問題陳述

給定整數n，將所有不同的解決方案返回到N-Queens難題。您可以按任何順序返回答案。

每個解決方案都包含N-Queens的位置的獨特板配置，其中'q表示女王和'。指示一個空白空間。

例子

對於n = 4，可能的解決方案是：

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

方法和算法

回溯算法

解決N-Queens問題的最常見方法是使用回溯。回溯算法會逐步構建解決方案的候選者，並在確定候選人不可能導致有效解決方案的情況下立即放棄候選人。

步驟：

1. Initialize the Board ：以空的n×n板開始。
2. Place the Queen ：嘗試將女王放在第一行中，然後繼續放置後來的皇后。
3. Check Validity ：對於每個女王安置，請檢查它是否與已經位置的皇后相衝突。
4. Backtrack if Necessary ：如果放置女王沒有解決方案，請卸下女王（回溯），然後嘗試下一個位置。
5. Store the Solution ：如果找到有效的配置（放置n Queens），請存儲板配置。
6. Repeat ：繼續此過程，直到嘗試所有可能的配置為止。

挑戰

董事會代表

可以使用每個單元格為“ Q”或“。”的2D列表來表示板。

檢查衝突

有效檢查衝突至關重要：

1. Row Check ：確保沒有其他皇后在同一行中。
2. Column Check ：確保沒有其他皇后在同一列中。
3. Diagonal Check ：確保沒有其他皇后在同一對角上。

最佳化

使用集合跟踪被佔用的列和對角線可以加快衝突檢查過程。

與ThreadPoolExecutor的並發

為了優化為較大n的問題解決問題，解決方案利用與ThreadPoolExecutor的並發：

• 每個線程開始解決第一行中不同列的問題。
• 這種平行方法可以大大減少找到所有解決方案的時間。

我們的解決方案

該解決方案是弗羅姆（Frome）的一個免費星期五挑戰之一，我們在停機期間選擇隨機面試挑戰來編寫解決方案。

安裝

 pip install wolfsoftware.NQueens

用法

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

概括

N-Queens問題是一個引人入勝且複雜的挑戰，需要對遞歸，回溯和優化技術有深入的了解。通過利用多線程，此實施有效地找到了給定板尺寸的所有可能解決方案。理解和實施N-Queens問題是提高解決問題的技能和算法思維的寶貴練習。