HOWTO · Java
Java のエイト クイーンズ プロブレム
このチュートリアルでは、Java の 8 クイーン問題について説明します。
このチュートリアルでは、Java の 8 クイーン問題について説明します。
Java のエイト クイーンズ プロブレム
エイト クイーンの問題は、8 x 8 のチェス盤に 8つのクイーンを互いに攻撃しないように配置する必要があるということです。 つまり、チェスではクイーンが移動できるため、同じ行、列、または対角線に 2つのクイーンを配置することはできません。
バックトラッキングは、Java のエイト クイーンまたは N クイーンの問題を解決するために使用できます。 まず、バックトラッキング アルゴリズムについて説明します。
エイト クイーン問題にバック トラッキング アルゴリズムを使用する
バックトラッキング アルゴリズムを使用してエイト クイーン問題を解決するという考え方は、クイーンを左端の列から始めて異なる列に個別に配置することです。 列にクイーンを配置し、以前に配置された他のクイーンとの衝突を確認します。
次に列で、行がクラッシュに含まれていない場合、列と行の両方をエイト クイーン問題の解決策の一部としてマークします。 衝突していない状況が見つからない場合はバックトラックが使用され、false が返されます。
以下は、バックトラッキング アルゴリズムを使用してエイト クイーンズ問題を解決する段階的なプロセスです。
-
まずは一番左の列から。
-
すべてのクイーンが配置された場合にコードが true を返す条件を作成します。
-
次に、次の手順を実行して、列のすべての行を試します。
- クイーンが行に安全に配置されている場合、この行と列は、他のソリューションを再帰的にチェックするソリューションの一部としてマークされます。
- クイーンが安全に一列に配置されている場合は、true を返します。
- クイーンが安全に列に配置されていない場合は、行と列のマークを外し、ソリューションをバックトラックして、最初のオプションに戻り、ソリューションを他の行に適用します。
-
すべての行をチェックしても解決策がない場合は、false を返してバックトラッキング アルゴリズムをトリガーする必要があります。
上記の手順に基づいて例を実装してみましょう。
package delftstack;
public class EightQueen {
// Size of the board should be 8x8 for the eight queens problem
public static final int SIZE_OF_BOARD = 8;
boolean[][] BOARD_BOOLEAN;
// For an empty place
public static final boolean EMPTY_PLACE = false;
// For a place that contains a queen
public static final boolean QUEEN_PLACE = true;
// The number of moves
public static final int MOVES_NUMBER = 4;
// The horizontal moves
int[] Horizontal_Moves;
// The Vertical moves
int[] Vertical_Moves;
public int Queens = 0;
public EightQueen() {
// Constructor creates an empty board
BOARD_BOOLEAN = new boolean[SIZE_OF_BOARD][SIZE_OF_BOARD];
for (int row = 0; row < BOARD_BOOLEAN.length; row++) {
for (int col = 0; col < BOARD_BOOLEAN[row].length; col++) {
BOARD_BOOLEAN[row][col] = EMPTY_PLACE;
}
}
Horizontal_Moves = new int[MOVES_NUMBER];
Vertical_Moves = new int[MOVES_NUMBER];
// move up right
Horizontal_Moves[0] = -1;
Vertical_Moves[0] = 1;
// move down left
Horizontal_Moves[1] = 1;
Vertical_Moves[1] = -1;
// move up left
Horizontal_Moves[2] = -1;
Vertical_Moves[2] = -1;
// move down right
Horizontal_Moves[3] = 1;
Vertical_Moves[3] = 1;
}
public boolean Queens_Placing(int Board_Column) {
if (Board_Column >= SIZE_OF_BOARD) {
return true;
} else {
boolean Queen_Placed = false;
int Board_Row = 0;
while (!Queen_Placed && Board_Row < SIZE_OF_BOARD) {
if (Queen_UnderAttack(Board_Row, Board_Column)) {
++Board_Row;
} else {
Set_Queen(Board_Row, Board_Column);
Queen_Placed = Queens_Placing(Board_Column + 1);
if (!Queen_Placed) {
Remove_Queen(Board_Row, Board_Column);
++Board_Row;
}
}
}
return Queen_Placed;
}
}
private void Remove_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = EMPTY_PLACE;
// Remove the comment from the code below to check which place the queen was removed.
// System.out.printf("The queen is REMOVED from [%d][%d]\n", Board_Row, Board_Column);
--Queens;
}
private void Set_Queen(int Board_Row, int Board_Column) {
BOARD_BOOLEAN[Board_Row][Board_Column] = QUEEN_PLACE;
// Remove the comments from the code below to check where the queen was placed
// System.out.printf("The queen is PLACED in [%d][%d]\n", Board_Row, Board_Column);
++Queens;
}
public boolean Queen_UnderAttack(int Board_Row, int Board_Column) {
boolean Queen_Condition = false;
// check the row
for (int Column = 0; Column < SIZE_OF_BOARD; Column++) {
if ((BOARD_BOOLEAN[Board_Row][Column] == true)) {
Queen_Condition = true;
}
}
// check the column
for (int Row = 0; Row < BOARD_BOOLEAN.length; Row++) {
if (BOARD_BOOLEAN[Row][Board_Column] == true) {
Queen_Condition = true;
}
}
// check the diagonal
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column < 8;
Row += Horizontal_Moves[0], Column += Vertical_Moves[0]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column >= 0;
Row += Horizontal_Moves[1], Column += Vertical_Moves[1]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column >= 0;
Row += Horizontal_Moves[2], Column += Vertical_Moves[2]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column < 8;
Row += Horizontal_Moves[3], Column += Vertical_Moves[3]) {
if (BOARD_BOOLEAN[Row][Column] == true) {
Queen_Condition = true;
}
}
return Queen_Condition;
}
public void Display_Board() {
int Count = 0;
for (int Board_Row = 0; Board_Row < BOARD_BOOLEAN.length; Board_Row++) {
for (int Board_Column = 0; Board_Column < BOARD_BOOLEAN[Board_Row].length; Board_Column++) {
if (BOARD_BOOLEAN[Board_Row][Board_Column] == true) {
System.out.printf("|%s| ", " Q ");
Count++;
} else {
System.out.printf("|%s| ", " X ");
}
}
System.out.println();
}
System.out.printf("%d queens problem is solved, the queens are placed.\n", Count);
}
public static void main(String[] arg) {
EightQueen EightQueen_Problem = new EightQueen();
EightQueen_Problem.Queens_Placing(0);
EightQueen_Problem.Display_Board();
}
}
上記のコードは、バックトラッキング アルゴリズム ソリューションを使用してエイト クイーン問題を実装します。 お互いを殺すことができない場所に女王を配置します。
Q がクイーンを表す出力を参照してください。
| Q | | X | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | Q | | X |
| X | | X | | X | | X | | Q | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | X | | Q |
| X | | Q | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | Q | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | Q | | X | | X |
| X | | X | | Q | | X | | X | | X | | X | | X |
8 queens problem is solved, the queens are placed.
上記のアルゴリズムの時間計算量は O(N!) で、補助空間は O(N2) です。
