Java/C++에서 역추적을 사용하는 N-Queens 문제
체스 두는 것을 좋아한다면 N-queens 문제에 대해 배우는 것을 좋아할 것입니다. 역추적을 이해하는 것은 좋은 문제입니다.
역추적이란 무엇입니까?
역추적에서는 사용 가능한 여러 이동 중 하나의 가능한 이동으로 시작합니다. 그런 다음 문제를 해결하려고 합니다.
선택한 이동으로 문제를 해결할 수 있으면 솔루션을 인쇄합니다. 그렇지 않으면 역추적하여 다른 동작을 선택하고 해결하려고 합니다.
어떤 조치도 제대로 이루어지지 않으면 문제에 대한 해결책이 없다고 주장합니다.
N-Queens 문제는 무엇입니까?
How can N queens be placed on an NxN chessboard so that no two of them attack each other?
이 문제는 일반적으로 N=4 및 N=8에서 나타납니다.
N=4인 예를 살펴보겠습니다.
문제를 해결하기 전에 체스에서 여왕의 움직임에 대해 알아야 합니다.
퀸은 어느 방향으로든 여러 단계를 이동할 수 있습니다. 유일한 제약은 움직이는 동안 방향을 변경할 수 없다는 것입니다.
여왕의 움직임을 보면 한 가지 분명한 사실은 두 여왕이 같은 행이나 열에 있을 수 없다는 것입니다.
이를 통해 각 행과 각 열에 하나의 퀸만 배치할 수 있습니다.
N=4일 때 솔루션은 다음과 같습니다.
하지만 이 배열을 어떻게 얻을 수 있습니까?
N-Queens 문제에 대한 해결책
이 문제를 해결하려는 방법은 위치에 여왕을 배치하고 공격을 받을 가능성을 배제하는 것입니다. 우리는 각 행/열에 하나의 여왕을 배치합니다.
여왕이 선택한 위치에서 공격을 받고 있는 것을 확인하면 다음 위치를 시도합니다.
여왕이 연속된 모든 위치에서 공격을 받고 있는 경우 현재 위치 이전에 배치된 여왕의 위치를 되돌려 변경합니다.
모든 N개의 여왕이 성공적으로 배치될 때까지 여왕을 배치하고 역추적하는 과정을 반복합니다.
단계별 역추적은 다음과 같이 표시됩니다.
적십자는 여왕의 공격을 받고 있는 위치를 표시합니다. 배치할 여왕이 있지만 행의 모든 위치가 공격을 받는 상태에 도달할 때마다 우리는 역추적합니다.
이것이 문제에 대한 유일한 해결책은 아닙니다. 각 퀸을 시계 방향으로 한 단계 앞으로 이동하면 다른 솔루션을 얻습니다.
이 예에서는 행에 따라 여왕을 배치했으며 열 방향으로도 동일한 작업을 수행할 수 있습니다. 이 경우 각 여왕은 열에 속합니다.
C++ 및 Java에서 N-Queens 문제 구현
C++에서 N-Queens 문제 구현:
#define N 4
#include <stdbool.h>
#include <stdio.h>
//function to print the solution
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}
// function to check whether the position is safe or not
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
// The function that solves the problem using backtracking
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
// driver program to test above function
int main()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return 0;
}
printSolution(board);
return true;
return 0;
}
Java에서 N-queens 문제 구현:
package com.JournalDev;
public class Main {
static final int N = 4;
// print the final solution matrix
static void printSolution(int board[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
}
}
// function to check whether the position is safe or not
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
// The function that solves the problem using backtracking
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
public static void main(String args[])
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (!solveNQueen(board, 0)) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
}
Output :
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
N=8의 경우 출력은 다음과 같습니다.
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
코드 구현 이해
위치가 공격을 받고 있는지 여부를 확인하기 위해 isSafe라는 함수를 만들었습니다.
이 함수는 위치가 공격으로부터 안전한 경우 true를 반환합니다.
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
첫 번째 for 루프는 열을 따라 검사하고 두 번째 및 세 번째 for 루프는 두 대각선을 따라 검사합니다.
다음 코드는 퀸을 해당 위치에 배치하고 역추적하는 역할을 합니다. 여왕의 위치를 표시하기 위해 행렬에서 해당 셀을 1로 설정합니다. 퀸을 배치하기 전에 isSafe를 호출하여 위치가 안전한지 확인합니다.
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
재귀 호출은 보드를 통과하고 열을 col+1로 설정합니다. 재귀 호출이 false를 반환하면 항목을 0으로 재설정하여 역추적합니다.
결론
역추적을 사용하여 N-Queen 문제를 해결하는 방법입니다. 역추적에 대해 자세히 알아보려면 스도쿠 문제를 해결해 보십시오.