NQueens package

概要

N-Queensの問題は、プログラミングインタビューや学術環境でよく遭遇する古典的な課題です。課題は、2人の女王が互いに脅迫しないように、n×nチェスボードにn女王を置くことです。これは、同じ行、列、または対角線を共有できる2人の女王がいないことを意味します。

問題ステートメント

整数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の問題を最適化するために、ソリューションはStreadPoolexecutorと同時性を活用します。

• 各スレッドは、最初の行の別の列の問題の解決を開始します。
• この並列アプローチは、すべてのソリューションを見つける時間を大幅に短縮できます。

私たちの解決策

このソリューションは、無料の金曜日の課題の1つであり、ダウンタイム中にソリューションを作成するためのランダムなインタビューの課題を選択しました。

インストール

 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-QUENSの問題を理解して実装することは、問題解決スキルとアルゴリズム思考を改善するための貴重な演習です。