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问题是提高解决问题的技能和算法思维的宝贵练习。