N-Queen

# ------------------------------------------
# 🧠 N-Queen 문제 (Backtracking 방식)
# ------------------------------------------
# N×N 체스판 위에 N개의 퀸을 서로 공격하지 않게 배치하는 문제.
# 같은 행(row), 같은 열(column), 대각선(diagonal)에
# 두 개 이상의 퀸이 있을 수 없음.
# ------------------------------------------

def is_safe(board, row, col, n):
    """
    현재 (row, col)에 퀸을 놓을 수 있는지 검사하는 함수
    board[i] = i번째 행(row)에 놓인 퀸의 열(column) 인덱스
    """

    # 이미 놓인 이전 행들의 퀸 위치를 모두 확인
    for i in range(row):
        # 1️⃣ 같은 열(col)에 퀸이 존재하는지 검사
        if board[i] == col:
            return False

        # 2️⃣ 대각선 공격 검사
        # 두 퀸의 행 차(row - i) == 열 차(col - board[i])이면 같은 대각선
        if abs(board[i] - col) == abs(i - row):
            return False

    # 위의 두 조건에 모두 해당되지 않으면 안전한 위치
    return True

def solve_n_queen(board, row, n, solutions):
    """
    백트래킹으로 N-Queen 해를 찾는 재귀 함수
    row: 현재 퀸을 배치하려는 행 인덱스
    """

    # 종료 조건: 모든 행에 퀸을 배치한 경우 → 해답 1개 완성
    if row == n:
        # board 리스트를 복사해서 저장 (참조 문제 방지)
        solutions.append(board[:])
        return

    # 현재 행(row)에 대해, 가능한 모든 열(col)을 시도
    for col in range(n):
        # (row, col)이 안전한지 검사
        if is_safe(board, row, col, n):
            # 안전하다면 퀸을 배치
            board[row] = col

            # 다음 행(row + 1)에 대해 재귀적으로 배치 시도
            solve_n_queen(board, row + 1, n, solutions)

            # 백트래킹 단계: 방금 놓은 퀸을 제거(-1로 초기화)
            board[row] = -1

def n_queen(n):
    """
    N-Queen 문제의 전체 해를 반환하는 함수
    """
    board = [-1] * n       # board[i] = i번째 행의 퀸이 위치한 열 (초기엔 모두 -1)
    solutions = []          # 모든 가능한 해를 저장할 리스트

    # 0번째 행부터 시작
    solve_n_queen(board, 0, n, solutions)

    return solutions

# ------------------------------------------
# 실행 예시
# ------------------------------------------
if __name__ == "__main__":
    N = 4                                # 체스판 크기 (4×4)
    result = n_queen(N)                  # N-Queen 해 탐색

    print(f"{N}-Queen 문제 해답 개수: {len(result)}\\n")

    # 각 해답 출력
    for sol in result:
        print(sol)                       # [1, 3, 0, 2] 형태로 표시 (각 행의 열 위치)

TSP