8 つのクイーンの問題は、2 人のクイーンが互いに攻撃できないように、チェス盤の各列にクイーンを配置する解決策を見つけることです。この問題は再帰を使用して解決できます。このセクションでは、この問題を解決するための バックトラッキング と呼ばれる一般的なアルゴリズム設計手法を紹介します。バックトラッキング アプローチでは、候補となる解決策を段階的に検索し、
が問題であると判断するとすぐにそのオプションを放棄します。 候補は有効な解決策である可能性が低いため、新しい候補を探します。

2 次元配列を使用してチェス盤を表すことができます。ただし、各行に含めることができるクイーンは 1 つだけであるため、行内のクイーンの位置を示すには 1 次元配列を使用するだけで十分です。したがって、queens 配列を次のように定義できます。

int[] クイーン = 新しい int[8];

j を queens[i] に代入して、クイーンが行 i と列 j に配置されることを示します。下の図 (a) は、下の図 (b) のチェス盤の queens 配列の内容を示しています。

検索は、

k = 0 の最初の行から開始されます。ここで、k は、考慮されている現在の行のインデックスです。このアルゴリズムは、_j = 0, 1, ... , 7 の行の j_ 番目の列にクイーンを配置できる可能性があるかどうかをこの順序でチェックします。検索は次のように実装されます:

成功すると、次の行のクイーンの配置の検索が続行されます。現在の行が最後の行の場合、解決策が見つかります。
成功しない場合は、前の行に戻り、前の行の次の列で新しいプレースメントの検索を続けます。
アルゴリズムが最初の行に戻り、この行でクイーンの新しい配置が見つからない場合、解決策は見つかりません。

以下のコードは、エイト クイーン問題の解決策を表示するプログラムを示します。

パッケージアプリケーション; インポートjavafx.application.Application; インポートjavafx.geometry.Pos; インポートjavafx.stage.Stage; インポートjavafx.scene.Scene; インポートjavafx.scene.control.Label; javafx.scene.image.Imageをインポートします。 インポートjavafx.scene.image.ImageView; インポートjavafx.scene.layout.GridPane; public class EightQueens extends Application { パブリック静的最終整数サイズ = 8; // チェス盤のサイズ // クイーンは (i, queens[i]) に配置されます // -1 は、i 番目の行に現在クイーンが配置されていないことを示します // 最初に、0 行目の (0, 0) にクイーンを配置します。 private int[] クイーン = {-1, -1, -1, -1, -1, -1, -1, -1}; @Override // Application クラスの start メソッドをオーバーライドします public void start(ステージprimaryStage) { 検索（）; // 解決策を探す // チェス盤を表示する GridPane chessBoard = new GridPane(); chessBoard.setAlignment(Pos.CENTER); ラベル[][] ラベル = 新しいラベル[サイズ][サイズ]; for(int i = 0; i = 0 && k package application; import javafx.application.Application; import javafx.geometry.Pos; import javafx.stage.Stage; import javafx.scene.Scene; import javafx.scene.control.Label; import javafx.scene.image.Image; import javafx.scene.image.ImageView; import javafx.scene.layout.GridPane; public class EightQueens extends Application { public static final int SIZE = 8; // The size of the chess board // queens are placed at (i, queens[i]) // -1 indicates that no queen is currently placed in the ith row // Initially, place a queen at (0, 0) in the 0th row private int[] queens = {-1, -1, -1, -1, -1, -1, -1, -1}; @Override // Override the start method in the Application class public void start(Stage primaryStage) { search(); // Search for a solution // Display chess board GridPane chessBoard = new GridPane(); chessBoard.setAlignment(Pos.CENTER); Label[][] labels = new Label[SIZE][SIZE]; for(int i = 0; i = 0 && k プログラムは、

search() (行 20) を呼び出して解決策を検索します。最初は、どの行にもクイーンは配置されていません (16 行目)。検索は k = 0 の最初の行から開始され (53 行目)、クイーンの場所を見つけます (56 行目)。成功した場合は、それを行 (行 61) に配置し、次の行 (行 62) を検討します。成功しなかった場合は、前の行 (58 ～ 59 行目) に戻ります。

findPosition(k) メソッドは、queen[k] 1 から開始して行 k にクイーンを配置できる位置を検索します (73 行目) 。 start、start 1、 にクイーンを配置できるかどうかをチェックします。 。 。 、 7 の順に記述します (75 ～ 78 行目)。可能であれば、列インデックスを返します (77 行目)。それ以外の場合は、-1 を返します (80 行目)。

isValid(row, column) メソッドが呼び出され、指定された位置にクイーンを配置することで、以前に配置されたクイーンと競合するかどうかがチェックされます (76 行目)。以下の図に示すように、同じ列 (86 行目)、左上の対角線 (87 行目)、または右上の対角線 (88 行目) にクイーンが配置されないようにします。