Java의 여덟 여왕 문제
Sheeraz Gul
2023년10월12일
이 자습서는 Java의 여덟 여왕 문제를 보여줍니다.
Java의 여덟 여왕 문제
8개의 여왕 문제는 서로 공격하지 않는 방식으로 8x8 체스판에 8개의 여왕을 배치해야 한다는 것입니다. 즉, 여왕은 체스에서 이동할 수 있기 때문에 두 여왕이 같은 행, 열 또는 대각선에 있을 수 없습니다.
역추적은 Java의 Eight Queens 또는 N-Queens 문제를 해결하는 데 사용할 수 있습니다. 먼저 역추적 알고리즘에 대해 논의해 봅시다.
Eight Queens 문제에 대한 역추적 알고리즘 사용
역추적 알고리즘을 사용하여 여덟 여왕 문제를 해결하는 아이디어는 여왕을 가장 왼쪽 열부터 시작하여 서로 다른 열에 개별적으로 배치하는 것입니다. 여왕을 기둥에 놓고 이전에 배치한 다른 여왕과의 충돌을 확인합니다.
그런 다음 열에서 행이 충돌하지 않는 경우 여덟 여왕 문제에 대한 솔루션의 일부로 열과 행을 모두 표시합니다. 충돌이 아닌 상황을 찾지 못한 경우 역추적을 사용하고 false를 반환합니다.
다음은 역추적 알고리즘을 사용하여 Eight Queens 문제를 해결하는 단계별 프로세스입니다.
-
먼저 맨 왼쪽 열부터 시작합니다.
-
모든 여왕이 배치되면 코드가 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();
}
}
위의 코드는 역추적 알고리즘 솔루션을 사용하여 Eight Queens 문제를 구현합니다. 서로 죽일 수 없는 곳에 여왕을 배치할 것입니다.
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)입니다.
작가: Sheeraz Gul
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook