Colin's Blog
[파이썬] 백트래킹 알고리즘의 응용 (스도쿠, N-퀸 문제 등)

백트래킹 알고리즘은 주어진 문제의 해를 찾기 위해 가능한 모든 경우의 수를 탐색하는 방법 중 하나입니다. 이 알고리즘은 상태 공간 트리를 탐색하여 해를 찾아내는데, 이때 일부 불필요한 탐색을 줄이기 위해 백트래킹이라는 방법을 사용합니다.

이번 포스트에서는 백트래킹 알고리즘을 스도쿠와 N-퀸 문제에 응용해보겠습니다. 이러한 문제들은 간단하면서도 백트래킹 알고리즘의 활용을 통해 효과적으로 해결될 수 있는 대표적인 예시입니다.

스도쿠 문제

스도쿠는 9x9 크기의 격자에 1부터 9까지의 숫자를 채워 넣는 논리 퍼즐입니다. 스도쿠 문제를 해결하기 위해 백트래킹 알고리즘을 사용할 수 있습니다.

스도쿠 문제의 백트래킹 알고리즘 해결 과정은 다음과 같습니다.

  1. 빈칸을 찾습니다.
  2. 해당 빈칸에 1부터 9까지의 숫자를 순서대로 넣을 수 있는지 확인합니다.
  3. 가능한 숫자를 넣고 다음 빈칸으로 이동합니다.
  4. 모든 빈칸이 채워질 때까지 이를 반복합니다.
  5. 답을 찾았으면 출력하고 종료합니다.
  6. 마지막에 도달한 빈칸에서 가능한 숫자를 모두 넣어보았지만 답을 찾지 못했으면 이전 빈칸으로 돌아가서 다른 숫자를 넣어봅니다.

아래는 스도쿠 문제를 백트래킹 알고리즘으로 해결하는 예시 코드입니다. 코드는 Python으로 작성되었습니다.

def solve_sudoku(board):
    if not find_empty(board):
        return True
    
    row, col = find_empty(board)
    
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            
            if solve_sudoku(board):
                return True
            
            board[row][col] = 0
    
    return False

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

def is_valid(board, row, col, num):
    for i in range(9):
        if board[i][col] == num:
            return False
        
        if board[row][i] == num:
            return False
        
        if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
            return False
    
    return True

위의 코드에서 solve_sudoku() 함수는 스도쿠 문제를 해결하는 함수입니다. find_empty() 함수는 빈칸을 찾는 함수이고, is_valid() 함수는 숫자가 스도쿠 규칙에 맞게 입력되었는지 확인하는 함수입니다. solve_sudoku() 함수에서는 백트래킹 알고리즘을 이용하여 가능한 숫자를 찾고 규칙에 맞게 채워나갑니다.

N-퀸 문제

N-퀸 문제는 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제입니다. 여기서 백트래킹 알고리즘을 활용하여 퀸을 배치해보겠습니다.

N-퀸 문제의 백트래킹 알고리즘 해결 과정은 다음과 같습니다.

  1. 첫 번째 행부터 시작하여 각 열마다 퀸을 놓을 수 있는지 확인합니다.
  2. 퀸을 놓을 수 있으면 해당 위치에 퀸을 놓고 다음 행으로 이동합니다.
  3. 모든 행에 퀸을 놓을 수 있을 때까지 이를 반복합니다.
  4. 답을 찾았으면 출력하고 종료합니다.
  5. 마지막 행까지 모든 열에 퀸을 놓을 수 없으면 이전 행으로 돌아가서 다른 열에 퀸을 놓습니다.

아래는 N-퀸 문제를 백트래킹 알고리즘으로 해결하는 예시 코드입니다. 코드는 Python으로 작성되었습니다.

def solve_n_queens(n):
    board = [[0] * n for _ in range(n)]
    
    if solve(board, 0, n):
        print_solution(board, n)
    else:
        print("No solution found.")

def solve(board, row, n):
    if row >= n:
        return True
    
    for col in range(n):
        if is_valid(board, row, col, n):
            board[row][col] = 1
            
            if solve(board, row + 1, n):
                return True
            
            board[row][col] = 0
    
    return False

def is_valid(board, row, col, n):
    for i in range(row):
        if board[i][col] == 1:
            return False
    
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    
    i, j = row, col
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    
    return True

def print_solution(board, n):
    for i in range(n):
        for j in range(n):
            print(board[i][j], end=" ")
        print()

위의 코드에서 solve_n_queens() 함수는 N-퀸 문제를 해결하는 함수입니다. solve() 함수는 백트래킹 알고리즘을 이용하여 가능한 퀸의 위치를 찾습니다. is_valid() 함수는 퀸이 다른 퀸들과 충돌하지 않는지 검사하는 함수입니다. print_solution() 함수는 답을 출력하는 함수입니다.

스도쿠와 N-퀸 문제는 백트래킹 알고리즘을 활용하여 쉽게 해결할 수 있는 문제입니다. 이러한 알고리즘을 사용하면 더 복잡한 문제에도 유용하게 적용할 수 있을 것입니다. 위의 예시 코드를 통해 백트래킹 알고리즘의 응용을 이해하고 필요한 경우에 적용해서 문제를 효과적으로 해결해보세요!

© 2018 Colin. All rights reserved.