HOWTO · Java

Java의 여덟 여왕 문제

이 자습서는 Java의 여덟 여왕 문제를 보여줍니다.

이 페이지의 내용

이 자습서에서는 역추적을 사용해 Java에서 여덟 여왕 문제를 푸는 방법을 설명합니다. 목표는 8 × 8 체스판에 여왕 여덟 개를 배치해 어떤 두 여왕도 같은 행, 열 또는 대각선에 놓이지 않게 하는 것입니다. 아래 솔버는 배치 하나를 찾으면 멈춥니다. 모든 해를 열거하거나 임의 크기의 보드를 구현하지는 않습니다.

역추적으로 여덟 여왕 문제 풀기

왼쪽 열부터 오른쪽으로 이동하며 각 열에 여왕을 하나씩 배치합니다. 재귀 호출마다 새로운 열을 처리하므로 두 여왕이 같은 열에 있는지 검사할 필요가 없습니다. 각 열에서는 행을 차례로 시도하고, 후보 위치를 이전 열에 이미 놓인 여왕들과 비교합니다.

이전 여왕과 행이 다르고 행 사이의 거리가 열 사이의 거리와 다르면 후보 위치는 안전합니다. 행 사이의 거리가 같으면 같은 행이고, 행과 열 사이의 절댓값 차이가 같으면 같은 대각선입니다. 두 조건을 모두 통과한 후보의 행을 기록한 다음 다음 열을 재귀적으로 풉니다.

재귀 호출은 보드를 완성하거나 모든 행이 충돌하는 열에 도달합니다. 후자의 경우 false를 반환합니다. 호출한 쪽은 기록해 둔 행을 지우고 다음 후보를 시도합니다. 이 되돌리기 단계는 중요합니다. 실패한 분기의 여왕을 그대로 두면 이후 검사에 잘못 영향을 줍니다. 여덟 번째 열까지 도달했다는 것은 여덟 열 모두에 안전한 여왕을 놓았다는 뜻이므로 탐색을 성공으로 끝낼 수 있습니다.

Java로 솔버 구현하기

queenRow 배열은 열마다 행 인덱스 하나를 저장합니다. 값이 -1이면 해당 열에 아직 행을 지정하지 않은 상태입니다. solve 메서드는 행을 차례로 확인하고, 안전한 선택을 기록한 뒤 재귀 호출을 합니다. 그 선택으로 해를 찾지 못하면 미지정 표시를 복원합니다. 불리언 반환값은 재귀 호출을 거슬러 올라가며 성공 여부를 전달합니다.

다음 예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

public class EightQueens {
    private static final int SIZE = 8;
    private static final int[] queenRow = new int[SIZE];

    private static boolean isSafe(int row, int column) {
        for (int previousColumn = 0; previousColumn < column; previousColumn++) {
            int previousRow = queenRow[previousColumn];
            if (previousRow == row
                    || Math.abs(previousRow - row)
                       == Math.abs(previousColumn - column)) {
                return false;
            }
        }
        return true;
    }

    private static boolean solve(int column) {
        if (column == SIZE) {
            return true;
        }

        for (int row = 0; row < SIZE; row++) {
            if (isSafe(row, column)) {
                queenRow[column] = row;
                if (solve(column + 1)) {
                    return true;
                }
                queenRow[column] = -1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        for (int column = 0; column < SIZE; column++) {
            queenRow[column] = -1;
        }

        if (!solve(0)) {
            System.out.println("No arrangement found.");
            return;
        }

        for (int row = 0; row < SIZE; row++) {
            for (int column = 0; column < SIZE; column++) {
                System.out.print(queenRow[column] == row ? "Q " : ". ");
            }
            System.out.println();
        }
    }
}

이 코드는 Java의 표준 라이브러리만 사용합니다. isSafe는 여왕이 이미 놓인 열을 확인하므로 현재까지의 배치를 기준으로 각 후보를 검사합니다. 재귀 호출이 성공하면 각 호출자는 자신의 선택을 되돌리지 않고 즉시 true를 반환합니다. 기록된 행들이 main에서 출력할 해를 나타냅니다.

프로그램 실행 및 출력 읽기

코드를 EightQueens.java라는 파일로 저장합니다. Java Development Kit을 설치한 뒤 해당 디렉터리에서 javac EightQueens.java로 컴파일하고 java EightQueens로 실행합니다. 성공하면 프로그램은 8 × 8 텍스트 보드만 출력합니다. 각 Q는 여왕을, 각 마침표는 빈 칸을 나타냅니다. 행과 열을 살펴보면 각각 여왕이 하나씩 있고, 대각선 안전성 검사로 어떤 두 여왕도 대각선을 공유하지 않게 했음을 확인할 수 있습니다. 솔버가 해를 찾지 못하는 실패 경로에서는 영어 메시지 No arrangement found.가 출력됩니다.

선택되는 배치는 반복문에서 행을 시도하는 순서에 따라 달라집니다. 프로그램은 첫 번째 완성된 배치를 찾으면 반환하므로 탐색 순서를 바꾸면 다른 유효한 보드가 나올 수 있습니다. 출력 보드는 선택 가능한 텍스트이며, 예제는 스크린샷이나 별도 이미지에 의존하지 않습니다.

복잡도와 한계

첫 번째 열에는 선택지가 최대 여덟 개 있고, 다음 열에는 사용하지 않은 행이 최대 일곱 개 남는 식으로 선택지가 줄어듭니다. 열마다 여왕 하나를 배치하는 N × N 보드에서는 탐색 대상 후보 배치 수가 O(N!)로 제한됩니다. 각 후보마다 isSafe가 이전 열을 최대 N개까지 살펴보므로 검사에 O(N)이 추가됩니다. 따라서 이 구현의 유용한 시간 상한은 O(N · N!)입니다. 안전하지 않은 부분 배치를 가지치기하면 보통 많은 후보를 살펴보지 않아도 되지만, 이 넓은 상한 자체는 달라지지 않습니다.

일반화된 형태에서 행 배열은 O(N) 공간을 사용하며, 재귀 호출 스택도 최대 O(N) 공간을 사용합니다. 이 구현은 8 × 8 보드를 불리언 행렬로 저장하는 대신 여덟 개의 행 인덱스만 저장하므로 탐색 상태 공간은 O(N²)가 아니라 O(N)입니다. 이 예제는 작은 고정 크기 시연으로 보드 크기는 8이며, 모든 해를 세거나 나열하지 않고 첫 번째 배치만 반환합니다.