PostsSeriesLabsAlgo

백트래킹·구현

N-퀸

서로 못 보게 놓기

퀸은 같은 줄·같은 열·대각선에 있는 칸을 노립니다. 보드에 퀸 4개를 서로 노리지 않게 놓습니다. 첫 줄 맨 왼쪽에 놓으면 끝까지 놓을 수 있을지 먼저 고르고, 위 줄부터 한 줄에 하나씩 놓아 보세요.

4×4 보드에 퀸 4개를 서로 노리지 않게 놓아요. 퀸은 같은 줄·같은 열·대각선에 있는 칸을 노려요. 첫 줄 맨 왼쪽(칸 0)에 놓으면 끝까지 놓을 수 있을까요?

♛ 퀸 놓을 수 있는 칸 퀸이 노리는 칸

놓은 퀸 0개 · 거둔 횟수 0번

내 예상 · 실제 안 된다 → 달랐어요

퀸을 0번 놓고 0번 거둬서 해를 찾았습니다. 첫 줄 맨 왼쪽은 막다른 길이었습니다. 이 보드에서 퀸 4개를 서로 노리지 않게 놓는 방법은 모두 2가지입니다.

  • 놓을 수 있는 칸에 놓았다 — 가장 왼쪽 칸부터 시도했다
  • 다음 줄이 막히면 — 앞 줄 퀸을 거두고 그 줄의 다음 칸으로 갔다

놓다가 막히면 앞 줄로 돌아가 다른 선택을 하는 방법 = 백트래킹(backtracking). 돌아오는 건 재귀가 해 주는 일입니다. 앞 장 순열과 조합 만들기에서도 같은 일을 했습니다.

4×4 보드에 퀸 4개를 놓는 배치는 모두 1,820가지입니다. 백트래킹은 퀸을 8번 놓고 첫 해를 찾았습니다.

8×8 모든 배치를 하나씩4,426,165,368가지
8×8 백트래킹으로 해 92개 모두2,056번
8×8 에서 퀸 8개를 놓는 모든 배치는 약 44억 가지입니다. 하나씩 따지면 Python 으로 약 7분 걸립니다. 막다른 길을 일찍 끊으면 퀸을 2,056번 놓아 해 92개를 모두 찾습니다. 해 하나만 찾으면 113번입니다.

퀸이 노리는 칸은 세 방향이다

  • 같은 열 — 위 줄 퀸과 칸 번호가 같다
  • 대각선 — 줄 − 열이 같거나 줄 + 열이 같다. 줄 0 칸 0 퀸은 줄 1 칸 1, 줄 2 칸 2 를 노린다
  • 같은 줄 — 한 줄에 퀸 하나만 놓아서 따로 볼 필요가 없다

방금 막힌 칸을 눌렀을 때 나온 「같은 열이에요」「대각선으로 노려요」가 이 규칙입니다.

코드는 놓고, 부르고, 안 되면 거둔다

위에서 놓아 본 것과 같은 보드입니다. 줄 번호와 칸 번호는 코드의 row, col 처럼 0부터 셉니다. 다음을 눌러 퀸이 놓이고 거둬지는 걸 보세요.

놓은 퀸 0개

♛ 퀸 놓을 수 있는 칸 퀸이 노리는 칸

다음을 눌러 한 줄씩 넘겨 보세요

row = 0 queens = 0

place.py
  1. 1def place(row, n, cols, d1, d2):
  2. 2 if row == n:
  3. 3 return True
  4. 4 for col in range(n):
  5. 5 diag, anti = row - col, row + col
  6. 6 if col in cols or diag in d1 or anti in d2:
  7. 7 continue
  8. 8 cols.add(col); d1.add(diag); d2.add(anti)
  9. 9 if place(row + 1, n, cols, d1, d2):
  10. 10 return True
  11. 11 cols.remove(col); d1.remove(diag); d2.remove(anti)
  12. 12 return False
0 / 26
  • 칸을 훑는 줄 — 플레이어에서는 한 스텝으로 묶었다
  • cols d1 d2 — 노리는 열, 줄 − 열(diag), 줄 + 열(anti)을 모아 둔 집합. 놓을 때 넣고 거둘 때 뺀다
  • place(row + 1, …) — 다음 줄을 같은 방법으로 풀어 본다. 놓을 곳이 없으면 False 로 돌아온다
  • cols.remove(col) — 돌아와서 퀸을 거두는 줄. 같은 줄의 다음 칸을 이어서 본다

3×3 보드에 퀸 3개를 서로 노리지 않게 놓는 방법은 몇 가지일까요?

N-퀸에서 틀리는 자리

  • 대각선을 한쪽만 검사하면 — 8×8 해가 92가지가 아니라 2,113가지로 나온다. 노리는 배치까지 센다
  • 거두는 줄(remove)을 빼면 — 한 번 놓은 칸의 표시가 남아서 다음 시도가 막힌다. 해가 있는 4×4 에서도 False 가 나왔다
  • N 이 하나 늘면 약 5배 느려진다 — 해를 모두 세는 데 N = 8 이 약 0.001초, 10 이 약 0.02초, 11 이 약 0.1초였다(Python 3.14, 컴퓨터마다 다르다)
  • 퀸 위치는 줄마다 칸 번호 하나로 적는다 — board[row] = col 처럼 리스트 하나면 충분하다. 보드 전체를 2차원으로 들고 다닐 필요가 없다

문제에서 이 말이 보이면

조건을 만족하는 배치를 찾는다놓다가 안 되면 돌아가 다른 선택경우의 수는 많은데 안 되는 경우는 일찍 끊는다

다음 장에서는 시키는 대로 그대로 따라 하는 시뮬레이션을 봅니다.