N-Queens는 N×N 크기의 체스판 위에 N개의 퀸을 배치해야 하는 매력적인 코딩 챌린지입니다.
실제 모습은 다음과 같습니다:
퀸은 체스에서 가장 강력한 기물로, 다음과 같은 모든 방향으로 움직일 수 있습니다:
- 세로 방향
- 가로 방향
- 대각선 방향
따라서 올바른 해답(여러 개가 존재할 수 있습니다)은 모든 퀸을 보드 위에 배치하면서, 어떤 퀸도 다른 퀸의 공격 범위 안에 들어가지 않도록 만들어야 합니다.
이 글에서는 제가 어떤 사고 과정을 거쳐 해결책을 도출했는지 소개해 드리겠습니다.
문제 해결 계획 세우기
이런 유형의 코딩 챌린지를 풀 때 좋은 출발점은 일상 언어(평문)로 계획을 먼저 적어 보는 것입니다.
계획을 글로 정리하면 문제가 정확히 무엇인지, 그리고 해결하기 위해 어떤 단계를 밟아야 하는지 명확하게 파악할 수 있습니다.
만약 계획을 세우는 데 어려움을 겪고 있다면, 문제를 100% 이해하고 있는지부터 점검하세요.
제가 N-Queens 해결을 위해 세운 계획은 다음과 같습니다:
- (0, 0) 위치에서 시작한다
- 유효한 위치라면: 퀸을 놓고, 열을 하나 전진(+ 1)시키며, 행을 0으로 초기화한다
- 위, 아래, 좌, 우, 대각선 방향을 검사한다
- 유효하지 않다면: 한 칸 앞으로 진행한다
- 현재 위치가 n이 아니라면 위로 이동한다(행 + 1)
- 현재 열에 퀸을 놓을 수 없을 때는 백트래킹(backtracking)한다
- 마지막에 놓았던 퀸을 제거한다
- 마지막 퀸의 열과, 해당 퀸의 행+1 위치로 되돌아간다
이 계획은 처음 적어둔 내용을 더 깔끔하게 다듬은 버전입니다.
구현 전에 추가적인 분석이 필요한 단계들은 집중적으로 파고들었습니다.
중요한 점:
처음 세운 계획이 완벽하지 않아도 괜찮습니다(저 역시 그랬습니다). 계획은 목표 지점을 잡아주는 나침반 역할을 할 뿐입니다.
만약 탄탄한 계획을 세우기 어렵다면 솔루션을 찾아보는 것도 전혀 잘못된 것이 아닙니다…
…다만 솔루션의 동작 원리를 충분히 이해한 후, 반드시 자신만의 코드로 직접 작성해 보세요.
유효한 위치 검증하기
특정 위치가 유효한지 확인하려면 여러 방향을 살펴봐야 합니다.
2차원 배열 형태의 보드를 직접 다루는 대신, 저는 보드 위에 놓인 퀸들의 배열과 각 퀸의 좌표를 관리하는 방식을 선택했습니다.
그런 다음 검증하고 싶은 위치와 이 퀸 배열을 비교하면 됩니다.
예를 들어, 같은 행에 있는 퀸을 검사하는 코드는 다음과 같습니다:
def queen_in_row(row)
@queens_in_board.find { |r, c| r == row }
end
해당 행에 퀸이 이미 있다면 그 퀸을 반환하고, 비어 있다면 nil을 반환합니다.
열(column)은 별도로 검사할 필요가 없는데, 퀸을 놓은 직후 항상 다음 열로 이동하기 때문입니다.
대각선 검사는 방향이 총 4개라 조금 더 작업이 필요합니다.
오른쪽 위 대각선을 검사하는 코드는 다음과 같습니다:
def right_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == n
diagonals << [row += 1, column += 1]
end
diagonals
end
나머지 대각선도 로직은 동일하며, 루프의 종료 조건과 이동 방향(행 + 1 / 행 - 1)만 다릅니다.
이 부분은 시행착오를 조금 거쳤지만, 그것은 자연스러운 과정입니다.
이런 메서드들을 개별적으로 테스트하여 정확히 동작하는지 확인하는 것이 중요합니다. 검증된 메서드들이 모이면 이를 조합해 완성된 솔루션을 만들 수 있습니다.
네 개의 대각선을 모두 계산해 보드 위의 모든 퀸과 비교하는 메서드는 다음과 같습니다:
def queen_in_diagonal(row, column, n)
diagonals =
right_upper_diagonal_for(row, column, n) +
left_upper_diagonal_for(row, column, n) +
left_lower_diagonal_for(row, column, n) +
right_lower_diagonal_for(row, column, n)
diagonals.any? { |r, c| r == row && c == column } ||
diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end
백트래킹 구현 방법
이렇게 간단하지 않은 챌린지를 해결하려면 핵심 통찰, 기법 또는 알고리즘에 대한 이해가 필요합니다.
N-Queens의 경우 그 핵심 기법은 바로 백트래킹(backtracking)입니다.
백트래킹이란 이전의 행동(예: 보드에 퀸을 놓는 것)을 취소하고, 다른 구성으로 다시 시도하는 것을 의미합니다.
저는 이 부분이 가장 어려울 것이라 예상했지만, 막상 구현해 보니 생각보다 훨씬 쉬웠습니다.
이 개념을 파악하기 위해 저는 간단한 시뮬레이션을 진행했습니다.
종이에 보드와 퀸을 나타내는 상자를 그려 넣었습니다:
그리고 마우스로 상자들을 보드 위에서 직접 옮겨 가며 알고리즘의 흐름을 시뮬레이션했습니다.
백트래킹 코드는 다음과 같습니다:
while row >= n
row = @queens_in_board[-1][0] + 1
column = @queens_in_board[-1][1]
puts "Backtracking, deleted: #{@queens_in_board.pop}"
end
코딩 중 막힐 때는 이런 방식을 다른 문제에도 활용할 수 있습니다. 드로잉 프로그램이나 종이에 그려 보며 자유롭게 실험해 보세요.
동작 원리의 핵심은 다음과 같습니다:
- 보드 위로 계속 이동하다가, 보드 끝(행 >= n)에 도달하면 현재 열에는 퀸을 배치할 수 없다는 의미입니다
- 마지막 퀸의 위치로 되돌아간 뒤 그 퀸을 제거하는 방식으로 백트래킹합니다
- 그 위치에서도 퀸을 놓을 수 없다면 다시 한 번 백트래킹합니다
행 위치의 + 1은 마지막 퀸을 한 칸 아래로 이동시켜 새로운 배치 구성을 열어주는 장치입니다.
n = 4일 때 이 코드를 실행한 결과입니다(n = 2와 n = 3에는 해가 존재하지 않습니다):
"placing at 0 0" "placing at 2 1" Backtracking, deleted: [2, 1] "placing at 3 1" "placing at 1 2" Backtracking, deleted: [1, 2] Backtracking, deleted: [3, 1] Backtracking, deleted: [0, 0] "placing at 1 0" "placing at 3 1" "placing at 0 2" "placing at 2 3"
아래 GIF는 알고리즘의 동작을 보여주는 시각적 예시입니다:
전체 코드
def solve_n_queens(n)
@queens_in_board = []
row = 0
column = 0
until @queens_in_board.size == n
if queen_in_row(row) || queen_in_diagonal(row, column, n)
row += 1
while row >= n
row = @queens_in_board[-1][0] + 1
column = @queens_in_board[-1][1]
puts "Backtracking, deleted: #{@queens_in_board.pop}"
end
else
place_queen(row, column)
p "placing at #{row} #{column}"
row = 0
column += 1
end
end
@queens_in_board
end
def queen_in_row(row)
@queens_in_board.find { |r, c| r == row }
end
def queen_in_diagonal(row, column, n)
diagonals =
right_upper_diagonal_for(row, column, n) +
left_upper_diagonal_for(row, column, n) +
left_lower_diagonal_for(row, column, n) +
right_lower_diagonal_for(row, column, n)
diagonals.any? { |r, c| r == row && c == column } ||
diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end
def top_row?(row, n)
row == n
end
def place_queen(row, column)
@queens_in_board << [row, column]
end
def right_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == n
diagonals << [row += 1, column += 1]
end
diagonals
end
def left_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == 0
diagonals << [row += 1, column -= 1]
end
diagonals
end
def right_lower_diagonal_for(row, column, n)
diagonals = []
until row == 0 || column == n
diagonals << [row -= 1, column += 1]
end
diagonals
end
def left_lower_diagonal_for(row, column, n)
diagonals = []
until row == 0 || column == 0
diagonals << [row -= 1, column -= 1]
end
diagonals
end
def print_board(n)
board = Array.new(n) { Array.new(n) { "." } }
@queens_in_board.each { |queen| board[queen[0]][queen[1]] = "Q" }
board.map { |n| n.join("|") }.reverse
end
p solve_n_queens(4)
p solve_n_queens(5)
puts print_board(5)
재귀 버전
다음은 가능한 모든 해답을 찾아내는 대안적인 버전입니다.
def solve_n_queens(n, column = 0, queens_in_board = [])
@queens_in_board = queens_in_board
n.times do |row|
unless queen_in_row(row) || queen_in_diagonal(row, column, n)
place_queen(row, column)
solve_n_queens(n, column + 1, @queens_in_board)
remove_last_queen
end
end
puts print_board(n) if @queens_in_board.size == n
end
달라진 부분은 solve_n_queens 메서드뿐입니다.
이 버전은 재귀(recursion, 자기 자신을 호출하는 메서드)를 사용해 모든 부분 해답을 깊이 우선으로 탐색합니다.
완전한 해답을 찾으면 print_board 메서드를 통해 결과를 출력합니다.
마무리
이번 글에서는 N-Queens 코딩 챌린지가 무엇인지, 그리고 Ruby로 이를 어떻게 해결하는지 배웠습니다. 아울러 평문으로 계획을 세우고, 개별 메서드를 격리해서 테스트하며, 시각화를 통해 알고리즘을 이해하는 등 문제 해결 능력을 향상시키는 실질적인 방법도 함께 익혔습니다.
이 글이 도움이 되었다면 주변에 도움이 될 만한 사람들에게 공유해 주세요.
읽어주셔서 감사합니다!