백트래킹(Backtracking)
: 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다

구현코드

public class NQueens {
    private static final int N = 4; // 체스판의 크기

    public static void solveNQueens() {
        int[][] board = new int[N][N];
        
        if (solveNQueensUtil(board, 0)) {
            printSolution(board);
        } else {
            System.out.println("해결책이 없습니다.");
        }
    }

    private static boolean solveNQueensUtil(int[][] board, int col) {
        if (col >= N) {
            return true;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col)) {
                board[i][col] = 1;

                if (solveNQueensUtil(board, col + 1)) {
                    return true;
                }

                board[i][col] = 0; // 백트래킹
            }
        }

        return false;
    }

    private 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;
    }

    private 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();
        }
    }

    public static void main(String[] args) {
        solveNQueens();
    }
}

이 자바 코드는 4x4 체스판에서 N-Queen 문제를 해결하는 백트래킹 알고리즘을 구현했습니다. 주요 구성 요소는 다음과 같습니다:

solveNQueens(): 메인 함수로, 문제 해결을 시작합니다.
solveNQueensUtil(): 실제 백트래킹 로직이 구현된 재귀 함수입니다.
isSafe(): 현재 위치에 퀸을 놓을 수 있는지 확인하는 함수입니다.
printSolution(): 해결책을 출력하는 함수입니다.

백트래킹의 핵심은 solveNQueensUtil() 함수에 있습니다. 이 함수는 각 열에 대해 가능한 모든 행을 시도하며, 안전한 위치를 찾으면 퀸을 배치하고 다음 열로 넘어갑니다. 만약 현재 배치가 해결책으로 이어지지 않으면, 퀸을 제거하고(백트래킹) 다른 위치를 시도합니다.
이 코드를 실행하면 4x4 체스판에서 N-Queen 문제의 해결책을 찾아 출력합니다. 체스판의 크기를 변경하려면 N 상수의 값을 수정하면 됩니다.
이 예제를 통해 백트래킹의 기본 구조를 이해하실 수 있을 것입니다. 다른 백트래킹 문제에 대해 궁금하신 점이 있다면 말씀해 주세요.