8차시 미로 밖으로 — 8-퍼즐에 같은 A*를 옮겨 붙이기

🤔

여는 장면 — 우리가 배운 것은 A*인가, 미로인가

지난 7차시에 여러분은 astar()를 직접 짜고 세 숫자를 얻었습니다. 배율 w를 0으로 두면 65칸 · 17걸음(다익스트라), 1로 두면 52칸 · 17걸음(A*), 5로 두면 20칸 · 19걸음(부풀린 A*)이었지요. 코드는 한 글자도 안 바뀌고 숫자 하나만 바뀌었는데 결과가 갈렸습니다.

그런데 여기서 한 걸음 물러서 봅시다. 우리가 푼 것은 7행 12열짜리 미로 하나였습니다. 이대로 단원을 끝내면 여러분의 머릿속에 A*는 "미로 푸는 방법"으로 남습니다. 그것은 A*를 배운 것이 아니에요.

나무로 만든 15-퍼즐 실물 — 조각이 1부터 15까지 순서대로 맞춰져 있고 오른쪽 아래 한 칸이 비어 있다 — 완성된 나무 조각 퍼즐. 빈칸이 딱 하나 있고, 조각은 그 빈칸으로만 밀 수 있다. 오늘 우리가 A*에게 맡길 문제는 이것의 3×3판인 **8-퍼즐**이다. 미로에는 길이 그려져 있었지만, 여기에는 지도가 없다. 출처: Arcinides, Wikimedia Commons (CC BY-SA 4.0)

3×3 판에 1부터 8까지 조각이 놓여 있고 한 칸이 비어 있습니다. 조각은 빈칸으로만 밀 수 있어요. 이것을 흐트러뜨렸다가 1 2 3 / 4 5 6 / 7 8 _ 로 되돌리는 것이 8-퍼즐입니다.

여기에는 지도가 없습니다. 미로에서는 "지금 (4, 7)에 있다"고 말할 수 있었고 목표까지의 거리도 자로 잰 듯 셀 수 있었지요. 퍼즐에서 "지금 어디에 있는가"는 좌표가 아니라 조각 아홉 개가 놓인 모양 전체입니다. 그런데도 같은 코드가 통할까요?

💭 오늘의 물음

지도가 아닌 문제에 A*를 옮기려면 무엇을 갈아 끼워야 하는가? 그리고 정말로 astar() 본문은 한 글자도 고치지 않아도 되는가?

오늘 답할 것이 하나 더 있습니다. 미로에서는 어림(휴리스틱)을 맨해튼 거리 하나만 썼습니다. 다른 것을 쓸 생각조차 안 했지요. 그런데 8-퍼즐에는 쓸 만한 어림이 여러 개 있습니다. 어림을 아예 안 쓰는 것과 좋은 어림을 쓰는 것 사이가 171배, 쓸 만한 어림 둘 사이도 13배 갈립니다. 말로는 전해지지 않는 숫자라, 오늘은 직접 재 볼 거예요.

1

갈아 끼우는 자리는 셋뿐이다

7차시의 astar()를 다시 펴 놓고, 이 함수가 미로에 대해 아는 것에 동그라미를 쳐 봅시다. 놀랍게도 세 군데밖에 없습니다.

어디서 시작해서 어디로 가는가 — START와 GOAL
어떤 상태에서 어디로 갈 수 있는가 — neighbors()
남은 비용을 어떻게 어림하는가 — h()

나머지는 전부 문제가 무엇이든 똑같은 일입니다. 대기실(우선순위 큐)에서 f = g + h가 가장 작은 것을 꺼내고, 그 이웃마다 새 비용을 계산해 더 싸면 표를 고치고 다시 넣고, 목표를 꺼내면 부모 표를 거꾸로 되짚어 길을 만듭니다. 이 절차 안에는 '칸'이라는 말도, '벽'이라는 말도 없습니다.

그래서 A*는 미로 알고리즘이 아니라 상태 공간 알고리즘입니다. 3차시에서 물병 붓기를 상태 (a, b)로 적었던 그 문법 — 상태 · 행동 · 목표 — 이 여기서 완성됩니다. 문제를 그 문법으로 적을 수만 있으면 A*가 붙습니다.

A*는 세 자리만 비워 놓은 틀이다. 그 세 자리에 무엇을 꽂느냐가 문제를 정하고, 가운데 상자는 문제가 바뀌어도 그대로 돈다.

⚠️ 정확히 말하면 — 함수 둘, 값 셋

오늘 고쳐 쓴 함수는 둘입니다(neighbors()·h()). 그 밖에 값 셋을 새로 적습니다 — START, GOAL, 그리고 안전장치 상한 LIMIT이에요. 상한을 20,000에서 400,000으로 올리는 까닭은 문제의 크기가 달라졌기 때문입니다. 미로는 격자가 7×12 = 84칸이고 그중 갈 수 있는 칸이 65개였지만, 8-퍼즐은 갈 수 있는 상태가 181,440개입니다. 20,000인 채로 두면 어림 없는 설정이 도중에 '폭주'로 멈춰 버려요. 함수와 값은 구별해서 말합시다. "두 함수만 바꿨다"는 말이 "아무것도 안 적었다"는 뜻은 아닙니다.

7차시 · 미로용 이웃

def neighbors(p):
    r, c = p
    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C \
           and MAZE[nr][nc] != "#":
            yield (nr, nc)

오늘 · 퍼즐용 이웃

def neighbors(s):
    i = s.index(0); r, c = divmod(i, 3)
    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            t = list(s); t[i], t[j] = t[j], t[i]
            yield tuple(t)

두 코드의 보라색 줄이 완전히 같다는 점을 보세요. 아래·위·오른쪽·왼쪽을 도는 네 방향은 그대로입니다. 다른 것은 "움직이는 것이 무엇인가"뿐이에요. 미로에서는 내가 움직였고, 퍼즐에서는 빈칸이 움직입니다.

2

퍼즐을 상태로 적는다 — 왜 하필 튜플인가

먼저 상태입니다. 조각 아홉 개를 왼쪽 위부터 차례로 읽어 늘어놓습니다. 빈칸은 0으로 적어요.

판

  7 2 4
  5 _ 6
  8 3 1

상태

(7, 2, 4,
 5, 0, 6,
 8, 3, 1)

# k 번째 자리의 (행, 열) = divmod(k, 3)

여기서 [7, 2, 4, ...] 같은 리스트가 아니라 튜플을 쓴 것이 중요합니다. A*는 g 표와 부모 표(came)를 사전(dict)으로 들고 있고, 그 사전의 열쇠가 바로 상태예요. 파이썬 사전의 열쇠는 바뀌지 않는 값이어야 합니다. 리스트를 열쇠로 쓰면 TypeError: unhashable type: 'list'가 납니다. 미로에서 (r, c)를 튜플로 쓴 것도 같은 까닭이었어요 — 그때는 아무 생각 없이 지나갔지만, 여기서 그 이유가 드러납니다.

다음은 행동입니다. 사람은 "조각 3을 왼쪽으로 민다"고 말하지만, 코드로는 빈칸과 이웃 조각을 맞바꾸는 것이 훨씬 간단합니다. 빈칸이 어디 있는지는 s.index(0) 한 줄로 찾고, 거기서 상하좌우로 한 칸 간 자리와 값을 바꾸면 끝이에요.

위 표를 그대로 더하면 2×4 + 3×4 + 4×1 = 24, 아홉 자리로 나누어 8-퍼즐의 이웃은 **평균 2.7개**다. 미로에서도 이웃은 벽 때문에 1~4개였고 — 65칸을 세어 보면 막다른 칸이 6곳, 사거리가 13곳 — **평균 2.8개**였다. 갈림길의 수가 이렇게 비슷하다는 것은 **탐색이 퍼지는 속도**가 비슷하다는 뜻이다 — 그런데 결과는 전혀 달랐다. 왜 그럴까?
빈칸의 위치	밀 수 있는 조각	이웃 상태의 개수
네 모서리 (4자리)	2개	2
네 변의 가운데 (4자리)	3개	3
판 한가운데 (1자리)	4개	4

마지막으로 목표입니다. GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0). 미로의 목표가 (6, 11)이라는 한 칸이었듯이, 퍼즐의 목표도 딱 하나의 상태예요. "목표를 판정한다"는 일이 cur == GOAL 한 줄인 것도 그대로입니다.

📌 문제의 크기가 얼마나 커졌나

미로에서 A*가 뒤질 수 있는 칸은 많아야 65개였습니다(벽이 아닌 칸 전부). 8-퍼즐에서 아홉 칸에 아홉 개를 늘어놓는 방법은 9! = 362,880가지, 그중 실제로 오갈 수 있는 것은 그 절반인 181,440가지입니다(왜 절반인지는 개념 5에서).

65에서 181,440으로 — 약 2,791배입니다. 미로에서는 어림이 없어도 65칸만 뒤지면 끝났지만, 여기서는 어림이 없으면 몇만 개를 들춰 봐야 합니다. 어림의 값어치가 여기서 드러나요.

3

같은 문제에 어림이 둘 — h1과 h2

남은 것은 어림 h입니다. 미로에서는 고민할 것이 없었어요. 상하좌우로만 움직이니 맨해튼 거리가 자연스러웠고, 다른 후보를 떠올릴 일도 없었습니다. 그런데 퍼즐에서는 사정이 다릅니다. "여기서 목표까지 몇 수쯤 남았을까"를 재는 방법이 금방 두 가지나 떠올라요.

🔢 h1 — 제자리가 아닌 조각 수

목표에서의 제자리와 다른 곳에 있는 조각을 센다.
빈칸(0)은 세지 않는다.
세기만 하면 되니 계산이 아주 싸다.
원장 배치에서 h1 = 6

vs

📏 h2 — 맨해튼 거리의 합

조각마다 제자리까지 몇 칸 가야 하는지 재어 전부 더한다.
빈칸은 역시 세지 않는다.
미로에서 쓰던 그 맨해튼 거리를 조각 여덟 개에 쓴 셈이다.
원장 배치에서 h2 = 14

한 수는 조각 하나를 한 칸만 옮긴다. 그래서 두 어림 모두 실제 남은 수보다 크지 않다. 어느 쪽을 써도 최단은 지켜진다.

왜 둘 다 '허용 가능'한가

7차시에서 허용 가능성을 배웠습니다 — 어림이 실제보다 크지 않아야 A*가 최단을 지킨다는 것이었지요. 퍼즐의 두 어림도 그것을 만족합니다. 까닭은 규칙 한 줄에서 나와요.

💡 한 수는 조각 하나를 한 칸만 옮긴다

h1이 허용 가능한 까닭 — 제자리가 아닌 조각은 적어도 한 번은 움직여야 합니다. 한 수에 조각 하나만 움직이니, 남은 수는 제자리 아닌 조각의 개수보다 작을 수 없어요.

h2가 허용 가능한 까닭 — 어떤 조각이 집까지 d칸 떨어져 있으면 그 조각만 옮기는 데도 최소 d수가 듭니다. 한 수는 조각 하나를 한 칸만 옮기므로, 모든 조각의 거리를 더한 값보다 적은 수로는 절대 못 맞춥니다.

h2가 h1을 '지배한다'

두 어림을 나란히 놓으면 관계가 하나 보입니다. 제자리가 아닌 조각은 집까지의 거리가 적어도 1이고, 제자리에 있는 조각은 거리가 0입니다. 그러니 거리를 전부 더한 h2는 제자리 아닌 조각을 하나에 1씩만 세어도 이미 h1이 됩니다. 곧 어떤 배치에서도 h2 ≥ h1이에요. 이럴 때 "h2가 h1을 지배한다"고 말합니다.

등호는 언제 성립할까요? 어긋난 조각이 전부 딱 한 칸씩만 어긋났을 때입니다. 예를 들어 (1,2,3,4,5,6,0,7,8)은 7과 8이 각각 한 칸씩 오른쪽으로 밀려 있어서 h1 = 2, h2 = 2로 같습니다(실제 최단도 2수예요). 이 배치는 잠시 뒤 시뮬레이터에서 여러분이 직접 만들어 볼 겁니다.

말로 받아들이지 말고 세어 봅시다. 원장 프로그램은 씨앗을 20250828로 고정하고 무작위 배치 1,000개를 만들어 두 값을 견줍니다. 결과는 반례 0개 · 두 값이 같은 배치 2개 · 가장 크게 벌어진 차 13이었습니다. 1,000개로 못 미더우면 9! = 362,880가지를 전부 돌려도 됩니다 — 반례는 역시 0개였고, 같은 경우가 497개, 가장 크게 벌어진 차가 14였어요.

⚠️ h1에서 빈칸을 세면 어떻게 되나

h1을 짤 때 가장 흔한 실수가 빈칸(0)까지 세는 것입니다. 그러면 어떻게 될까요? 직접 재 보면 이렇습니다 — 오류는 나지 않고, 답도 20회로 그대로입니다. 달라지는 것은 효율이에요. 둘러본 상태가 3,667 → 3,830, 대기실에 넣은 횟수가 5,750 → 5,908로 늘고, 출발 배치의 어림값이 6에서 7로 커집니다.

그러니 "빈칸을 세면 답이 틀린다"고 말하면 거짓입니다. 정확한 표현은 "쓸데없이 더 둘러본다"예요. 빈칸은 조각이 아닙니다. 빈칸을 제자리로 옮기는 것 자체가 목적이 아니라, 빈칸은 조각을 미는 수단일 뿐이니까요.

4

어림 하나가 계산량을 171배 가른다

이제 세 설정을 겨루게 합니다. 코드는 하나이고 h 자리에 무엇을 꽂느냐만 바뀝니다. '어림 없음'은 새로 만들 것도 없어요 — 7차시의 배율 w를 0으로 두면 h가 통째로 지워지고, 그것이 곧 다익스트라입니다.

출발 `(7,2,4,5,0,6,8,3,1)` · 목표 `(1,2,3,4,5,6,7,8,0)` 기준. 배치가 바뀌면 세 숫자는 전부 바뀐다 — 표를 옮겨 적을 때 **어느 배치인지 함께** 적을 것.
어림	출발에서의 h	둘러본 상태	대기실에 넣은 횟수	최소 이동
어림 없음 (w = 0)	0	48,390	66,516	20회
h1 — 자리 틀린 조각 수	6	3,667	5,750	20회
h2 — 맨해튼 거리 합	14	283	451	20회

먼저 맨 오른쪽 칸을 보세요. 셋 다 20회입니다. 답은 같아요. 세 설정 모두 최단을 찾아냈습니다. 다른 것은 오직 답에 닿기까지 들춰 본 상태의 수입니다.

48,390 ÷ 283 = 171.0배 — 어림이 있고 없고의 차이
3,667 ÷ 283 = 13.0배 — 어림이 좋고 나쁘고의 차이

7차시 미로에서 다익스트라 65칸과 A* 52칸의 차이는 겨우 1.25배였습니다. "공짜로 13칸을 아꼈다"고 좋아했지요. 같은 알고리즘, 같은 w = 0과 w = 1인데 여기서는 171배가 됩니다. 무엇이 달라졌을까요?

문제의 크기입니다. 미로는 뒤져 봐야 65칸이라 어림이 없어도 금방 끝났습니다. 어림이 아낄 수 있는 최대치가 애초에 65칸이었어요. 퍼즐은 상태가 181,440개라 어림이 없으면 그중 4분의 1을 넘게 (48,390개) 들춰 봐야 목표에 닿습니다. 문제가 커질수록 어림의 값어치가 커진다 — 이것이 오늘의 가장 실용적인 결론입니다.

왜 지배하는 어림이 덜 둘러보는가

7차시 마지막에 우리는 이렇게 답했습니다. "A*가 꺼내는 칸은 언제나 다익스트라가 꺼내는 칸의 부분집합이다. h는 음수가 아니므로 f = g + h ≥ g이기 때문이다." 같은 논증이 여기서도 한 겹 더 굴러갑니다.

A*는 대기실에서 f가 작은 것부터 꺼냅니다. 최단 비용이 20이니, f가 20보다 작은 상태는 하나도 빼놓지 않고 꺼내게 됩니다. 그런데 f = g + h에서 g는 어림을 바꿔도 그대로예요. 바뀌는 것은 h뿐입니다. h가 커지면 f가 커지고, f가 20을 넘어서는 상태가 많아집니다. 그만큼 꺼낼 후보에서 밀려나요.

그러니 h2 ≥ h1이라는 관계는 곧 "h2로 꺼내는 상태는 h1으로 꺼내는 상태의 부분집합"이라는 뜻입니다. 지배가 성능으로 이어지는 다리가 바로 이것이에요. 숫자로 확인하면 283 ⊂ 3,667 ⊂ 48,390입니다.

흰 바탕 위에 놓인 두 퍼즐 큐브 — 왼쪽은 보통 3×3×3 큐브, 오른쪽은 한 면이 7×7칸인 훨씬 큰 큐브. 둘 다 면마다 한 색으로 맞춰져 있다 — 왼쪽은 보통 3×3×3 큐브, 오른쪽은 한 면이 7×7칸인 큐브다. 둘 다 여섯 면이 한 색씩 맞은 목표 상태다. 큐브도 8-퍼즐과 같은 상태 공간 문제다 — 상태는 색 배치, 행동은 면 돌리기, 목표는 이 배치 하나. 3차시 표에서 본 대로 왼쪽 큐브만 해도 상태가 약 4.3×10¹⁹가지다. 8-퍼즐 181,440 · 15-퍼즐 10,461,394,944,000(약 1.05×10¹³) · 큐브 4.3×10¹⁹ — **어림 없이 전부 뒤진다는 계획은 문제가 조금만 커져도 무너진다.** 칸이 늘어난 오른쪽 큐브는 말할 것도 없다. '적게 보는 법'이 곧 능력인 까닭이다. 출처: Matfald, Wikimedia Commons (CC BY-SA 3.0)

📌 시간이 아니라 '끝날 수 있느냐'의 문제

"48,390개면 좀 느린 정도 아닌가?"라고 생각할 수 있습니다. 실제로 이 배치에서는 브라우저 파이썬(Pyodide)으로 0.28초밖에 안 걸려요. 그런데 안전장치 LIMIT을 7차시 값 20,000으로 되돌려 보면 사정이 달라집니다.

어림 없는 설정만 '폭주'로 멈춥니다 — 대기실에 20,001번을 넣을 때까지 13,594개를 꺼냈는데도 목표를 못 만난 것이지요. h1·h2는 멀쩡히 3,667개·283개로 끝납니다. 어림은 속도를 조금 벌어 주는 장치가 아니라, 끝날 수 있느냐를 가르는 장치입니다.

5

못 푸는 배치가 있다 — 뒤집힌 짝의 홀짝

미로에서는 '닿을 수 없는 목표'를 깊이 걱정하지 않았습니다. 7차시에서 빈칸 63곳에 벽을 하나씩 세워 보았을 때 길이 막힌 경우가 5곳 있었지만, 그것은 우리가 벽을 세워서 막은 것이었어요. 원래 미로는 늘 이어져 있었습니다. 8-퍼즐은 다릅니다. 아무것도 막지 않았는데도 아무리 밀어도 목표에 닿지 못하는 배치가 있습니다. 그것도 절반이나요.

판별하는 방법이 있습니다. 빈칸을 빼고 여덟 조각을 왼쪽 위부터 한 줄로 읽어 늘어놓은 다음, 앞의 수가 뒤의 수보다 큰 짝을 셉니다. 이것을 뒤집힌 짝이라고 해요.

원장 배치 — 풀 수 있다

7 2 4 / 5 _ 6 / 8 3 1
  ↓ 빈칸을 빼고 한 줄로
7 2 4 5 6 8 3 1
  ↓ 앞>뒤 인 짝을 센다
뒤집힌 짝 16개 — 짝수
목표(0개)와 홀짝이 같다 → 닿는다

못 푸는 배치

2 8 1 / 4 6 3 / _ 7 5
  ↓ 빈칸을 빼고 한 줄로
2 8 1 4 6 3 7 5
  ↓ 앞>뒤 인 짝을 센다
뒤집힌 짝 11개 — 홀수
목표(0개)와 홀짝이 다르다 → 영영 못 닿는다

왜 홀짝이 안 바뀔까요? 조각을 미는 방법은 두 가지뿐입니다.

가로로 밀 때 — 조각과 빈칸이 자리만 바꿉니다. 빈칸은 세지 않으므로 한 줄로 읽은 순서가 아예 그대로예요. 뒤집힌 짝이 하나도 안 바뀝니다.
세로로 밀 때 — 조각 하나가 한 줄로 읽은 순서에서 다른 조각 두 개를 건너뜁니다. 그 두 조각과의 앞뒤 관계만 뒤집히므로 뒤집힌 짝은 0개 · 2개 늘거나 · 2개 줍니다.

어느 쪽도 홀짝을 바꾸지 못합니다. 목표 (1,2,3,4,5,6,7,8,0)은 뒤집힌 짝이 0개, 곧 짝수예요. 그러므로 홀수인 배치는 몇 수를 두든 목표에 닿을 수 없습니다.

이 사실이 배치 362,880개를 서로 닿지 못하는 두 덩어리로 정확히 반씩 가릅니다. 각 덩어리가 181,440개예요. 우리가 개념 2에서 본 그 숫자입니다. "9!의 절반"이라는 말의 뜻이 이제 보이지요.

📖 못 푸는 배치를 정말 돌려 보면

홀짝성 검사는 한 줄이면 끝나지만, 그래도 궁금하니 A*에게 시켜 봅니다. 결과는 둘러본 상태 181,440개 · 경로 없음이었습니다. 갈 수 있는 상태를 하나도 남기지 않고 전부 뒤졌는데 목표가 없었다는 뜻이에요.

여기서 어림을 바꿔 봐도 소용없습니다. 어림 없음도 181,440개, h1도 181,440개, h2도 181,440개. 답이 없을 때는 어림이 아무 도움도 되지 않습니다. 어림은 '답 쪽으로 빨리 가는 길잡이'인데 답이 없으니 길잡이도 할 일이 없는 것이지요.

그리고 이것이 오늘 가장 중요한 문장으로 이어집니다 — '못 찾았다'와 '없다'는 다릅니다. 탐색이 끝까지 돌아서 빈손으로 끝났다면 그것은 '없다'의 증명입니다. 하지만 상한(LIMIT)에 걸려 멈춘 것은 증명이 아니에요. 그건 그냥 '아직 못 찾았다'입니다. 두 결과가 화면에서 비슷해 보여도 뜻이 전혀 다릅니다.

💻

손으로 ① — 판을 밀어 보고, 어림을 재고, A*에게 맡긴다

아래 판은 진짜로 움직입니다. 빈칸 옆의 조각을 누르면 밀립니다. 밀 때마다 h1과 h2가 그 자리에서 다시 계산됩니다. 개념 3의 그림에서 보던 '동그라미 숫자'가 조각 위에 그대로 붙어 있어요 — 그 숫자를 전부 더한 것이 h2, 초록이 아닌 조각의 수가 h1입니다. 공책을 펴 두세요. 아래 세 과제의 답은 확인 문제에서 다시 묻습니다.

🧩 8-퍼즐 판 — 밀어 보고, 재고, 맡긴다 INTERACTIVE

빈칸 옆의 조각을 눌러 밉니다(노란 테두리가 지금 밀 수 있는 조각). 어림을 고르고 ▶ 풀어 줘를 누르면 A*가 답을 찾아 한 수씩 재생하고, 둘러본 상태 수를 보고합니다. 풀 수 없는 배치를 넣으면 뒤집힌 짝을 세어 돌려 보기 전에 알려 줍니다.

내가 둔 수 g0

h1 자리 틀린 조각6

h2 맨해튼 합14

f = g + h214

뒤집힌 짝16

풀 수 있나O

어림

섞는 수 20

아직 A*를 돌리지 않았습니다. 어림을 고르고 ▶ 풀어 줘를 눌러 보세요.

[안내] 원장 배치로 시작합니다 — 7 2 4 / 5 _ 6 / 8 3 1

※ 어림 없이 돌리면 상태를 수만 개 들춥니다. 상한은 200,000개이고, 상한에 걸리면 그 사실을 그대로 알려 줍니다 — 화면이 멈추지는 않습니다.

과제 ① 표를 채운다 — 어림 넷을 겨루게 한다

🔄 초기화를 눌러 원장 배치로 되돌린 뒤, 어림을 바꿔 가며 네 번 돌립니다. 매번 초기화하고 돌려야 같은 배치를 재는 것이 됩니다.

어림	출발에서의 h	둘러본 상태	최소 이동
어림 없음 (w = 0)
h1 자리 틀린 조각 수
h3 행·열 어긋난 수
h2 맨해튼 거리 합

'최소 이동' 칸을 먼저 보세요. 네 줄이 전부 같습니까? 같다면 그것이 오늘의 첫 결론입니다 — 어림은 답을 바꾸지 않고, 답에 닿는 수고만 바꾼다.

💡 h3은 무엇인가

여러분이 직접 만들어 볼 어림입니다. 조각마다 제자리와 행이 다르면 1점, 열이 다르면 1점을 매겨 더합니다. h1보다는 세밀하고 h2보다는 거칩니다. 원장 배치에서 h3 = 9예요 (h1 = 6, h2 = 14 사이). 표를 채워 보면 둘러본 상태 수도 그 사이에 놓입니다. 어림의 값이 클수록 덜 둘러본다는 규칙이 네 줄로 확인돼요.

과제 ② 반례를 만든다 — h1과 h2가 같아지는 배치

개념 3에서 h2 ≥ h1이라고 했습니다. 그런데 등호도 성립할 수 있다고 했지요. 직접 만들어 보세요.

🔄 초기화 뒤, 목표에 가까운 배치를 손으로 만듭니다. 힌트는 개념 3에 있습니다 — 어긋난 조각이 전부 딱 한 칸씩만 어긋나면 됩니다.
숫자 칸의 h1과 h2가 같아지는 순간을 찾습니다. 그때의 배치와 두 값을 공책에 적으세요.
거꾸로도 해 봅니다. 🎲 아무 배치를 여러 번 누르며 h2 − h1이 가장 큰 배치를 찾아보세요. 9! = 362,880가지를 전부 재 보면 최댓값은 14입니다. 몇까지 벌려 봤나요?
h2가 h1보다 작은 배치도 찾아보세요. (찾으면 개념 3이 무너집니다 — 정말 찾을 수 있을까요?)

과제 ③ 못 푸는 배치를 만난다

🎲 아무 배치는 아홉 개를 아무렇게나 늘어놓습니다. 그러니 절반쯤은 풀 수 없는 배치가 나와요. '풀 수 있나' 칸이 X로 바뀌면 시뮬레이터가 그 자리에서 알려 줍니다 — 단 한 수도 두어 보지 않고요.

그때 나타나는 🔎 그래도 끝까지 뒤져 봐 버튼을 눌러 보세요. A*가 갈 수 있는 상태를 전부 뒤진 뒤 빈손으로 끝냅니다. 몇 개를 뒤졌는지 적어 두세요. 개념 5의 숫자와 같은가요? 그리고 왜 어림을 바꿔도 그 숫자가 안 바뀌는지 한 줄로 적어 보세요.

💻

손으로 ② — 코드에서 정말 두 함수만 바뀌었는지 확인한다

시뮬레이터는 누군가 미리 만들어 둔 것입니다. 이제 코드로 갑니다. 아래 프로그램은 7차시에 여러분이 완성한 astar()를 그대로 싣고, 그 아래에서 neighbors()와 h()만 8-퍼즐용으로 갈아 끼웁니다.

맨 위 [확인] 줄을 눈여겨보세요. 퍼즐로 넘어가기 전에 7차시 미로를 한 번 더 풀어 봅니다. 52칸 · 17걸음이 찍히면 astar()가 훼손되지 않았다는 뜻이에요. 같은 함수가 두 문제를 연달아 푸는 장면이 오늘의 핵심입니다.

⚠️ 빈칸은 딱 한 곳입니다

h1() 안의 조건 한 줄(?????)입니다. astar()는 7차시에서 이미 여러분이 완성했으므로 채워진 채로 둡니다. 힌트는 두 가지 — k번째 자리의 조각은 s[k], 거기 놓여야 할 조각은 GOAL[k]이고, 빈칸(0)은 조각이 아니라서 세면 안 된다는 것입니다. 채우지 않고 실행하면 SyntaxError가 납니다 — 정상입니다.

# Ⅰ-8. 미로 밖으로 — 8-퍼즐에 같은 A*를 옮겨 붙인다
#
# 오늘 확인할 것: A* 는 미로 전용이 아니다.
#   상태를 무엇으로 볼지 · 이웃을 어떻게 만들지 · 남은 비용을 어떻게 어림할지
#   이 셋만 갈아 끼우면 전혀 다른 문제에 그대로 붙는다.
#   astar() 본문은 한 글자도 고치지 않는다. 아래에서 직접 확인한다.

import heapq
import random
import time

T0 = time.time()


# ═════════════════════════════════════════════════════════════════
# ───── 7차시에서 가져온 부분 — 고치지 않는다 ─────
# ═════════════════════════════════════════════════════════════════
MAZE = ["S.....#.##.#",
        ".#.........#",
        "##..#.......",
        "#......#....",
        "...#.....#..",
        "..#...#..#.#",
        ".......##..G"]
R, C = len(MAZE), len(MAZE[0])

def find(ch):
    return [(r, c) for r in range(R) for c in range(C) if MAZE[r][c] == ch][0]
START, GOAL = find("S"), find("G")

def neighbors(p):
    r, c = p
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):     # 아래·위·오른쪽·왼쪽 순
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and MAZE[nr][nc] != "#":
            yield (nr, nc)

def h(p):                       # 남은 거리 어림 = 맨해튼 거리
    return abs(p[0] - GOAL[0]) + abs(p[1] - GOAL[1])


LIMIT = 20000        # 대기실에 넣는 횟수 상한 — 넘으면 폭주로 보고 멈춘다

def astar(w, guard=True):
    """7차시에서 완성한 그대로다 — 실행되는 줄은 한 글자도 고치지 않았다.

    guard=False 는 '더 싼 길일 때만 갱신' 조건문을 지운 것과 같다(7차시 실습 ③).
    반환값: (꺼낸 칸 수, 경로 길이, 넣은 횟수)
            경로 길이 자리에 None 이면 폭주, "순환" 이면 부모 표에 고리가 생긴 것.
    """
    openq = [(w * h(START), 0, START)]      # (우선순위, g, 칸)
    g, came = {START: 0}, {START: None}
    seen, push = 0, 0                       # 꺼낸 칸 수 / 넣은 횟수

    while openq:
        f, gc, cur = heapq.heappop(openq)

        if gc > g.get(cur, 10**9):          # 낡은 표를 들고 온 손님은 돌려보낸다
            continue
        seen += 1
        if cur == GOAL:
            break

        for n in neighbors(cur):
            ng = gc + 1                     # 이웃까지의 새 비용

            # 더 싼 길을 찾았을 때만 기록한다
            if (ng < g.get(n, 10**9)) or not guard:
                g[n], came[n] = ng, cur

                # 우선순위 = 지나온 비용 + (배율 × 남은 어림)
                heapq.heappush(openq, (ng + w * h(n), ng, n))
                push += 1
                if push > LIMIT:            # 안전장치 — 7차시 실습 ③에서 쓰인다
                    return seen, None, push

    path, cur, walked = [], GOAL, set()     # 목표에서 거꾸로 되짚어 경로 복원
    while cur is not None:
        if cur in walked:                   # 부모를 따라가다 제자리로 돌아왔다면
            return seen, "순환", push        # 부모 표에 고리가 생긴 것이다
        walked.add(cur)
        path.append(cur)
        cur = came.get(cur)
    return seen, len(path) - 1, push
# ───── 여기까지 그대로 ─────


# 옮겨 붙이기 전에, 7차시 미로가 아직 그대로 풀리는지 한 번 확인한다.
print("[확인] 7차시 미로에 astar() 를 그대로 돌린다")
seen, length, push = astar(1.0)
print(f"        A* (w=1)   둘러본 칸 {seen}개   경로 {length}걸음")
print()


# ═════════════════════════════════════════════════════════════════
#   여기서부터 8-퍼즐이다.
#   astar() 는 위에 있는 것을 그대로 쓴다 — 아래로 내려가도 astar 는 없다.
#   갈아 끼우는 것은 ★ 표시가 붙은 함수 둘, 그리고 출발·목표 값뿐이다.
# ═════════════════════════════════════════════════════════════════

# 상태 = 숫자 아홉 개를 왼쪽 위부터 차례로 늘어놓은 것. 0 이 빈칸이다.
#        (7,2,4, 5,0,6, 8,3,1)  →   7 2 4
#                                   5 _ 6
#                                   8 3 1
GOAL  = (1, 2, 3, 4, 5, 6, 7, 8, 0)      # ← 미로의 GOAL 자리를 덮어쓴다
START = (7, 2, 4, 5, 0, 6, 8, 3, 1)      # ← 미로의 START 자리를 덮어쓴다

LIMIT = 400000   # ★ 상한만 올린다. 미로는 칸이 84개였지만 8-퍼즐은 상태가 181,440개다.
                 #   20000 인 채로 두면 어림 없는 설정이 도중에 '폭주'로 멈춘다.


def show(s):
    """배치를 3줄 그림으로 만든다 (0 은 빈칸이므로 _ 로)."""
    ch = ["_" if v == 0 else str(v) for v in s]
    return " / ".join(" ".join(ch[i:i + 3]) for i in (0, 3, 6))


def pad(s, n):
    """한글은 화면에서 두 칸을 차지한다. 글자 수로 맞추면 표가 어긋나므로 폭으로 맞춘다."""
    width = sum(2 if ord(c) > 0x2000 else 1 for c in s)
    return s + " " * max(0, n - width)


# ★ 갈아 끼우는 함수 ① — neighbors()
#   미로에서는 '벽이 아닌 옆 칸'이었다. 퍼즐에서는 '빈칸을 상하좌우로 민 결과'다.
def neighbors(s):
    i = s.index(0)                       # 빈칸이 몇 번째에 있나
    r, c = divmod(i, 3)                  # 그것을 (행, 열) 로
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:  # 판 밖으로 나가지 않는다
            j = nr * 3 + nc
            t = list(s)
            t[i], t[j] = t[j], t[i]      # 빈칸과 이웃 조각을 맞바꾼다
            yield tuple(t)


# ★ 갈아 끼우는 함수 ② — h()
#   같은 문제에도 어림은 여럿이다. 둘을 만들어 놓고 골라 쓴다.
def h1(s):
    """제자리가 아닌 조각의 수. 빈칸(0)은 세지 않는다."""
    # ★ 빈칸 ① — 제자리가 아닌 조각을 세는 조건을 채운다
    #    힌트 1: k 번째 자리의 조각은 s[k], 거기 놓여야 할 조각은 GOAL[k] 다.
    #    힌트 2: 빈칸(0)은 조각이 아니다. 세지 않고 건너뛰어야 한다.
    #    (이 한 줄만 채우면 나머지는 그대로 돌아간다)
    return sum(1 for k in range(9) if ?????)


def h2(s):
    """각 조각이 제자리까지 가야 하는 맨해튼 거리의 합. 빈칸은 세지 않는다."""
    d = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)                       # v 의 제자리가 몇 번째인가
            d += abs(k // 3 - gi // 3) + abs(k % 3 - gi % 3)
    return d


h = h1          # astar() 가 부르는 이름은 h 하나뿐이다. 여기에 무엇을 꽂느냐가 어림을 정한다.


def run(name, use_h, w):
    """어림을 갈아 끼우고 한 번 돌려서 한 줄로 보고한다."""
    global h
    h = use_h
    t = time.time()
    seen, length, push = astar(w)
    sec = time.time() - t

    if length is None:
        print(f"  {pad(name, 24)} ⚠ 폭주 — 대기실에 {push:,}번 넣고도 못 끝냈다")
    elif length == "순환":
        print(f"  {pad(name, 24)} ⚠ 부모 표에 고리가 생겼다")
    elif length == 0:
        # 되짚기가 목표에서 곧바로 끝났다 = 목표를 한 번도 밟은 적이 없다.
        # 7차시 astar() 는 '목표는 반드시 있다'고 믿고 만든 것이라 이렇게 나온다.
        print(f"  {pad(name, 24)} 둘러본 상태 {seen:>7,}개   경로 없음 — 다 뒤졌다   "
              f"({sec:.2f}초)")
    else:
        print(f"  {pad(name, 24)} 둘러본 상태 {seen:>7,}개   최소 이동 {length:2d}회   "
              f"넣은 횟수 {push:>7,}   ({sec:.2f}초)")
    return seen, length, push


print("[갈아 끼움] neighbors() 와 h() 만 8-퍼즐용으로 바꿨다. astar() 는 그대로다.")
print(f"        출발   {show(START)}")
print(f"        목표   {show(GOAL)}")
print()


# ── ① 어림 셋을 겨룬다 ────────────────────────────────────────────
#    'h 없음'은 새로 만들 것이 없다. 7차시의 w 를 0 으로 두면 h 가 그대로 지워진다.
print("① 어림 셋을 겨룬다   (걸린 시간은 컴퓨터마다 다르다. 상태 수만 옮겨 적을 것)")
run("어림 없음 (w=0)", h1, 0.0)
run("h1 자리 틀린 조각 수", h1, 1.0)
run("h2 맨해튼 거리 합", h2, 1.0)
print()


# ── ② h2 ≥ h1 인가 ───────────────────────────────────────────────
#    h2 가 h1 을 '지배한다(dominance)'는 말은 어떤 배치에서도 h2 ≥ h1 이라는 뜻이다.
#    말로 받아들이지 말고 무작위 배치 1,000개에 대고 반례가 있는지 직접 센다.
print("② h2 ≥ h1 인가 — 무작위 배치 1,000개로 반례를 찾아본다")
random.seed(20250828)           # 씨앗을 고정한다. 누가 돌려도 같은 1,000개가 나온다.
counter, same, gap = 0, 0, 0
for _ in range(1000):
    board = list(range(9))
    random.shuffle(board)
    board = tuple(board)
    a, b = h1(board), h2(board)
    if b < a:
        counter += 1            # 반례 — h2 가 h1 보다 작은 배치
    if b == a:
        same += 1
    gap = max(gap, b - a)
print(f"  반례(h2 < h1) {counter}개 · 두 값이 같은 배치 {same}개 · 가장 크게 벌어진 차 {gap}")
print(f"  견본: (1,2,3,4,5,6,0,7,8) → h1 = {h1((1,2,3,4,5,6,0,7,8))}, "
      f"h2 = {h2((1,2,3,4,5,6,0,7,8))}   (여기서는 같다)")
print()


# ── ③ 어림을 부풀리면 ────────────────────────────────────────────
#    7차시에서는 h 를 5배로 부풀리자 미로의 최단이 깨졌다. 퍼즐에서도 그럴까?
def h2_plus3(s):
    return h2(s) + 3            # 늘 3만큼 더 크게 어림한다


print("③ 어림을 부풀리면 최소 이동 20회가 깨질까")
run("h2 그대로 (w=1)", h2, 1.0)
run("h2 + 3 (w=1)", h2_plus3, 1.0)
run("h2 를 5배 (w=5)", h2, 5.0)
run("h1 을 5배 (w=5)", h1, 5.0)
print()


# ── ④ 못 푸는 배치 ───────────────────────────────────────────────
#    8-퍼즐의 배치 9! = 362,880개 중 정확히 절반은 어떤 수를 두어도 목표에 닿지 못한다.
#    돌려 보기 전에 홀짝성으로 먼저 판별할 수 있다.
def inversions(s):
    """빈칸을 뺀 여덟 조각을 늘어놓았을 때, 앞이 뒤보다 큰 짝의 수."""
    t = [v for v in s if v]
    return sum(1 for a in range(8) for b in range(a + 1, 8) if t[a] > t[b])


def solvable(s):
    """목표 (1..8,0) 은 뒤집힌 짝이 0개(짝수)다. 조각을 미는 수는 이 홀짝을 바꾸지 못한다.
       그래서 뒤집힌 짝이 홀수인 배치는 목표에 절대 닿지 못한다."""
    return inversions(s) % 2 == 0


print("④ 못 푸는 배치 — 전수 탐색 없이 먼저 판별한다")
for board in [(7, 2, 4, 5, 0, 6, 8, 3, 1), (2, 8, 1, 4, 6, 3, 0, 7, 5)]:
    verdict = "풀 수 있다" if solvable(board) else "풀 수 없다"
    print(f"  {pad(show(board), 24)} 뒤집힌 짝 {inversions(board):2d}개 → {verdict}")
print()

print("  그래도 (2,8,1,4,6,3,0,7,5) 를 정말 넣어 돌려 본다:")
START = (2, 8, 1, 4, 6, 3, 0, 7, 5)
run("h2 (w=1)", h2, 1.0)
print("  → 181,440은 이 배치에서 갈 수 있는 상태 전부다. 하나도 남기지 않고 뒤졌는데 목표가 없었다.")
print("     '아직 못 찾았다'가 아니라 '없다'가 증명된 것이다. 홀짝성 검사와 답이 같다.")
print()

print(f"(이 프로그램 전체가 {time.time() - T0:.1f}초 걸렸다 — 컴퓨터마다 다르다)")

# Ⅰ-8. 미로 밖으로 — 8-퍼즐에 같은 A*를 옮겨 붙인다
#
# 오늘 확인할 것: A* 는 미로 전용이 아니다.
#   상태를 무엇으로 볼지 · 이웃을 어떻게 만들지 · 남은 비용을 어떻게 어림할지
#   이 셋만 갈아 끼우면 전혀 다른 문제에 그대로 붙는다.
#   astar() 본문은 한 글자도 고치지 않는다. 아래에서 직접 확인한다.

import heapq
import random
import time

T0 = time.time()


# ═════════════════════════════════════════════════════════════════
# ───── 7차시에서 가져온 부분 — 고치지 않는다 ─────
# ═════════════════════════════════════════════════════════════════
MAZE = ["S.....#.##.#",
        ".#.........#",
        "##..#.......",
        "#......#....",
        "...#.....#..",
        "..#...#..#.#",
        ".......##..G"]
R, C = len(MAZE), len(MAZE[0])

def find(ch):
    return [(r, c) for r in range(R) for c in range(C) if MAZE[r][c] == ch][0]
START, GOAL = find("S"), find("G")

def neighbors(p):
    r, c = p
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):     # 아래·위·오른쪽·왼쪽 순
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and MAZE[nr][nc] != "#":
            yield (nr, nc)

def h(p):                       # 남은 거리 어림 = 맨해튼 거리
    return abs(p[0] - GOAL[0]) + abs(p[1] - GOAL[1])


LIMIT = 20000        # 대기실에 넣는 횟수 상한 — 넘으면 폭주로 보고 멈춘다

def astar(w, guard=True):
    """7차시에서 완성한 그대로다 — 실행되는 줄은 한 글자도 고치지 않았다.

    guard=False 는 '더 싼 길일 때만 갱신' 조건문을 지운 것과 같다(7차시 실습 ③).
    반환값: (꺼낸 칸 수, 경로 길이, 넣은 횟수)
            경로 길이 자리에 None 이면 폭주, "순환" 이면 부모 표에 고리가 생긴 것.
    """
    openq = [(w * h(START), 0, START)]      # (우선순위, g, 칸)
    g, came = {START: 0}, {START: None}
    seen, push = 0, 0                       # 꺼낸 칸 수 / 넣은 횟수

    while openq:
        f, gc, cur = heapq.heappop(openq)

        if gc > g.get(cur, 10**9):          # 낡은 표를 들고 온 손님은 돌려보낸다
            continue
        seen += 1
        if cur == GOAL:
            break

        for n in neighbors(cur):
            ng = gc + 1                     # 이웃까지의 새 비용

            # 더 싼 길을 찾았을 때만 기록한다
            if (ng < g.get(n, 10**9)) or not guard:
                g[n], came[n] = ng, cur

                # 우선순위 = 지나온 비용 + (배율 × 남은 어림)
                heapq.heappush(openq, (ng + w * h(n), ng, n))
                push += 1
                if push > LIMIT:            # 안전장치 — 7차시 실습 ③에서 쓰인다
                    return seen, None, push

    path, cur, walked = [], GOAL, set()     # 목표에서 거꾸로 되짚어 경로 복원
    while cur is not None:
        if cur in walked:                   # 부모를 따라가다 제자리로 돌아왔다면
            return seen, "순환", push        # 부모 표에 고리가 생긴 것이다
        walked.add(cur)
        path.append(cur)
        cur = came.get(cur)
    return seen, len(path) - 1, push
# ───── 여기까지 그대로 ─────


# 옮겨 붙이기 전에, 7차시 미로가 아직 그대로 풀리는지 한 번 확인한다.
print("[확인] 7차시 미로에 astar() 를 그대로 돌린다")
seen, length, push = astar(1.0)
print(f"        A* (w=1)   둘러본 칸 {seen}개   경로 {length}걸음")
print()


# ═════════════════════════════════════════════════════════════════
#   여기서부터 8-퍼즐이다.
#   astar() 는 위에 있는 것을 그대로 쓴다 — 아래로 내려가도 astar 는 없다.
#   갈아 끼우는 것은 ★ 표시가 붙은 함수 둘, 그리고 출발·목표 값뿐이다.
# ═════════════════════════════════════════════════════════════════

# 상태 = 숫자 아홉 개를 왼쪽 위부터 차례로 늘어놓은 것. 0 이 빈칸이다.
#        (7,2,4, 5,0,6, 8,3,1)  →   7 2 4
#                                   5 _ 6
#                                   8 3 1
GOAL  = (1, 2, 3, 4, 5, 6, 7, 8, 0)      # ← 미로의 GOAL 자리를 덮어쓴다
START = (7, 2, 4, 5, 0, 6, 8, 3, 1)      # ← 미로의 START 자리를 덮어쓴다

LIMIT = 400000   # ★ 상한만 올린다. 미로는 칸이 84개였지만 8-퍼즐은 상태가 181,440개다.
                 #   20000 인 채로 두면 어림 없는 설정이 도중에 '폭주'로 멈춘다.


def show(s):
    """배치를 3줄 그림으로 만든다 (0 은 빈칸이므로 _ 로)."""
    ch = ["_" if v == 0 else str(v) for v in s]
    return " / ".join(" ".join(ch[i:i + 3]) for i in (0, 3, 6))


def pad(s, n):
    """한글은 화면에서 두 칸을 차지한다. 글자 수로 맞추면 표가 어긋나므로 폭으로 맞춘다."""
    width = sum(2 if ord(c) > 0x2000 else 1 for c in s)
    return s + " " * max(0, n - width)


# ★ 갈아 끼우는 함수 ① — neighbors()
#   미로에서는 '벽이 아닌 옆 칸'이었다. 퍼즐에서는 '빈칸을 상하좌우로 민 결과'다.
def neighbors(s):
    i = s.index(0)                       # 빈칸이 몇 번째에 있나
    r, c = divmod(i, 3)                  # 그것을 (행, 열) 로
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:  # 판 밖으로 나가지 않는다
            j = nr * 3 + nc
            t = list(s)
            t[i], t[j] = t[j], t[i]      # 빈칸과 이웃 조각을 맞바꾼다
            yield tuple(t)


# ★ 갈아 끼우는 함수 ② — h()
#   같은 문제에도 어림은 여럿이다. 둘을 만들어 놓고 골라 쓴다.
def h1(s):
    """제자리가 아닌 조각의 수. 빈칸(0)은 세지 않는다."""
    # ★ 빈칸 ① — 제자리가 아닌 조각을 세는 조건을 채운다
    #    힌트 1: k 번째 자리의 조각은 s[k], 거기 놓여야 할 조각은 GOAL[k] 다.
    #    힌트 2: 빈칸(0)은 조각이 아니다. 세지 않고 건너뛰어야 한다.
    #    (이 한 줄만 채우면 나머지는 그대로 돌아간다)
    return sum(1 for k in range(9) if s[k] and s[k] != GOAL[k])


def h2(s):
    """각 조각이 제자리까지 가야 하는 맨해튼 거리의 합. 빈칸은 세지 않는다."""
    d = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)                       # v 의 제자리가 몇 번째인가
            d += abs(k // 3 - gi // 3) + abs(k % 3 - gi % 3)
    return d


h = h1          # astar() 가 부르는 이름은 h 하나뿐이다. 여기에 무엇을 꽂느냐가 어림을 정한다.


def run(name, use_h, w):
    """어림을 갈아 끼우고 한 번 돌려서 한 줄로 보고한다."""
    global h
    h = use_h
    t = time.time()
    seen, length, push = astar(w)
    sec = time.time() - t

    if length is None:
        print(f"  {pad(name, 24)} ⚠ 폭주 — 대기실에 {push:,}번 넣고도 못 끝냈다")
    elif length == "순환":
        print(f"  {pad(name, 24)} ⚠ 부모 표에 고리가 생겼다")
    elif length == 0:
        # 되짚기가 목표에서 곧바로 끝났다 = 목표를 한 번도 밟은 적이 없다.
        # 7차시 astar() 는 '목표는 반드시 있다'고 믿고 만든 것이라 이렇게 나온다.
        print(f"  {pad(name, 24)} 둘러본 상태 {seen:>7,}개   경로 없음 — 다 뒤졌다   "
              f"({sec:.2f}초)")
    else:
        print(f"  {pad(name, 24)} 둘러본 상태 {seen:>7,}개   최소 이동 {length:2d}회   "
              f"넣은 횟수 {push:>7,}   ({sec:.2f}초)")
    return seen, length, push


print("[갈아 끼움] neighbors() 와 h() 만 8-퍼즐용으로 바꿨다. astar() 는 그대로다.")
print(f"        출발   {show(START)}")
print(f"        목표   {show(GOAL)}")
print()


# ── ① 어림 셋을 겨룬다 ────────────────────────────────────────────
#    'h 없음'은 새로 만들 것이 없다. 7차시의 w 를 0 으로 두면 h 가 그대로 지워진다.
print("① 어림 셋을 겨룬다   (걸린 시간은 컴퓨터마다 다르다. 상태 수만 옮겨 적을 것)")
run("어림 없음 (w=0)", h1, 0.0)
run("h1 자리 틀린 조각 수", h1, 1.0)
run("h2 맨해튼 거리 합", h2, 1.0)
print()


# ── ② h2 ≥ h1 인가 ───────────────────────────────────────────────
#    h2 가 h1 을 '지배한다(dominance)'는 말은 어떤 배치에서도 h2 ≥ h1 이라는 뜻이다.
#    말로 받아들이지 말고 무작위 배치 1,000개에 대고 반례가 있는지 직접 센다.
print("② h2 ≥ h1 인가 — 무작위 배치 1,000개로 반례를 찾아본다")
random.seed(20250828)           # 씨앗을 고정한다. 누가 돌려도 같은 1,000개가 나온다.
counter, same, gap = 0, 0, 0
for _ in range(1000):
    board = list(range(9))
    random.shuffle(board)
    board = tuple(board)
    a, b = h1(board), h2(board)
    if b < a:
        counter += 1            # 반례 — h2 가 h1 보다 작은 배치
    if b == a:
        same += 1
    gap = max(gap, b - a)
print(f"  반례(h2 < h1) {counter}개 · 두 값이 같은 배치 {same}개 · 가장 크게 벌어진 차 {gap}")
print(f"  견본: (1,2,3,4,5,6,0,7,8) → h1 = {h1((1,2,3,4,5,6,0,7,8))}, "
      f"h2 = {h2((1,2,3,4,5,6,0,7,8))}   (여기서는 같다)")
print()


# ── ③ 어림을 부풀리면 ────────────────────────────────────────────
#    7차시에서는 h 를 5배로 부풀리자 미로의 최단이 깨졌다. 퍼즐에서도 그럴까?
def h2_plus3(s):
    return h2(s) + 3            # 늘 3만큼 더 크게 어림한다


print("③ 어림을 부풀리면 최소 이동 20회가 깨질까")
run("h2 그대로 (w=1)", h2, 1.0)
run("h2 + 3 (w=1)", h2_plus3, 1.0)
run("h2 를 5배 (w=5)", h2, 5.0)
run("h1 을 5배 (w=5)", h1, 5.0)
print()


# ── ④ 못 푸는 배치 ───────────────────────────────────────────────
#    8-퍼즐의 배치 9! = 362,880개 중 정확히 절반은 어떤 수를 두어도 목표에 닿지 못한다.
#    돌려 보기 전에 홀짝성으로 먼저 판별할 수 있다.
def inversions(s):
    """빈칸을 뺀 여덟 조각을 늘어놓았을 때, 앞이 뒤보다 큰 짝의 수."""
    t = [v for v in s if v]
    return sum(1 for a in range(8) for b in range(a + 1, 8) if t[a] > t[b])


def solvable(s):
    """목표 (1..8,0) 은 뒤집힌 짝이 0개(짝수)다. 조각을 미는 수는 이 홀짝을 바꾸지 못한다.
       그래서 뒤집힌 짝이 홀수인 배치는 목표에 절대 닿지 못한다."""
    return inversions(s) % 2 == 0


print("④ 못 푸는 배치 — 전수 탐색 없이 먼저 판별한다")
for board in [(7, 2, 4, 5, 0, 6, 8, 3, 1), (2, 8, 1, 4, 6, 3, 0, 7, 5)]:
    verdict = "풀 수 있다" if solvable(board) else "풀 수 없다"
    print(f"  {pad(show(board), 24)} 뒤집힌 짝 {inversions(board):2d}개 → {verdict}")
print()

print("  그래도 (2,8,1,4,6,3,0,7,5) 를 정말 넣어 돌려 본다:")
START = (2, 8, 1, 4, 6, 3, 0, 7, 5)
run("h2 (w=1)", h2, 1.0)
print("  → 181,440은 이 배치에서 갈 수 있는 상태 전부다. 하나도 남기지 않고 뒤졌는데 목표가 없었다.")
print("     '아직 못 찾았다'가 아니라 '없다'가 증명된 것이다. 홀짝성 검사와 답이 같다.")
print()

print(f"(이 프로그램 전체가 {time.time() - T0:.1f}초 걸렸다 — 컴퓨터마다 다르다)")

빈칸을 채우고 실행합니다. 맨 위에 52칸 · 17걸음, 이어서 48,390 / 3,667 / 283이 나오면 성공입니다.
시뮬레이터에서 적은 표와 대조합니다. 같은가요? 다르다면 둘 중 하나가 틀린 것입니다. (같아야 정상입니다 — 같은 알고리즘을 같은 배치에 돌렸으니까요.)
일부러 부숩니다 ⓐ. 아래쪽 LIMIT = 400000을 7차시 값인 20000으로 되돌려 보세요. 세 설정 중 어느 것이 죽나요? 그리고 왜 하필 그것일까요?
일부러 부숩니다 ⓑ. 여러분이 채운 조건에서 s[k] and를 빼서 빈칸까지 세는 h1을 만들어 보세요. 답(20회)이 틀리나요, 아니면 다른 것이 달라지나요?
더 어려운 배치로. START를 (6, 4, 7, 8, 5, 0, 3, 2, 1)로 바꿔 보세요. 이 배치의 최적해는 31수입니다. h2가 벌어 주는 이득이 몇 배로 줄어드나요?

① 어림 셋 — 48,390개 / 3,667개 / 283개, 전부 최소 이동 20회. 대기실에 넣은 횟수는 66,516 / 5,750 / 451.

② h2 ≥ h1 — 무작위 1,000개에서 반례 0개, 같은 배치 2개, 최대 차 13.

③ 부풀리기 — h2 + 3은 283개·451회·20회로 h2와 완전히 같습니다(6번 확인 문제에서 다룹니다). h2를 5배 하면 59개·20회로 최단이 지켜지고, h1을 5배 하면 925개·22회로 최단이 깨집니다.

④ 못 푸는 배치 — 뒤집힌 짝 16개(짝수) vs 11개(홀수). 홀수 배치를 정말 돌리면 181,440개를 다 뒤지고 '경로 없음'.

부수기 ⓐ — LIMIT을 20000으로: 어림 없는 설정만 죽습니다. ⚠ 폭주 — 대기실에 20,001번 넣고도 못 끝냈다가 찍힙니다. (화면에 뜨는 것은 이 한 줄뿐이에요. 그때까지 꺼낸 상태가 13,594개라는 것은 따로 세어 본 값입니다.) h1·h2는 멀쩡히 3,667개·283개로 20회를 찾습니다. 어림은 '조금 빠르게'가 아니라 '끝날 수 있느냐'의 문제라는 것이 이 한 번의 실험으로 보입니다.

부수기 ⓑ — 빈칸까지 세기: 오류도 안 나고 답도 20회 그대로입니다. 달라지는 것은 둘러본 상태 3,667 → 3,830, 넣은 횟수 5,750 → 5,908, 출발 배치의 어림값 6 → 7. "틀린다"가 아니라 "쓸데없이 더 본다"가 정확한 관찰입니다.

확장 — 31수 배치: 어림 없음 181,439개 / h1 143,849개 / h2 21,198개 (전부 31회). h2의 이득이 171배에서 8.6배로 줄어듭니다. 문제가 어려워질수록 좋은 어림조차 벅차진다는 뜻이에요. 그래서 실제 현장에서는 어림을 더 세게 만드는 연구를 계속합니다.

💡 run()에 elif length == 0:이 왜 있나

7차시 astar()는 "목표는 반드시 있다"고 믿고 만든 함수입니다. 못 푸는 배치를 넣으면 목표가 부모 표에 없어 되짚기가 곧바로 끝나고, 경로 길이가 0으로 돌아옵니다. 그대로 찍으면 화면에 "최소 이동 0회"라는 거짓말이 뜹니다. 그래서 run()이 그 경우를 따로 잡아 '경로 없음 — 다 뒤졌다'로 적어요. 코드를 줄이겠다고 이 분기를 지우지 마세요. 프로그램은 망가지더라도 말은 하고 망가져야 합니다.

💻

손으로 ③ — 어림을 내가 만들어 h2와 겨룬다

여기까지는 남이 만든 어림 둘을 써 봤습니다. 이제 하나 만들어 봅시다. 시뮬레이터에서 골라 쓴 h3이 그것이에요 — 조각마다 행이 어긋나면 1점, 열이 어긋나면 1점을 매겨 더합니다.

이 어림이 왜 말이 되는지 잠깐 생각해 보세요. 어떤 조각이 제자리와 행도 다르고 열도 다르면, 그 조각을 집에 넣으려면 세로로도 한 번, 가로로도 한 번은 움직여야 합니다. 그러니 2점을 매겨도 실제 남은 수를 넘지 않아요. 허용 가능합니다.

그리고 h1과의 관계도 보입니다. 제자리가 아닌 조각은 행이나 열 중 적어도 하나가 어긋나 있으니 최소 1점을 받습니다. 곧 h3 ≥ h1이에요. 반대로 맨해튼 거리와 견주면, 한 축으로 두 칸 떨어진 조각에게 h2는 2점을 주는데 h3은 '어긋났다'는 사실만 보고 1점만 줍니다 (3×3 판이라 한 축으로 벌어질 수 있는 최대 거리가 2칸이에요). 그러므로 h2 ≥ h3입니다. h1 ≤ h3 ≤ h2 — 어림 셋이 한 줄에 세워집니다.

# 손으로 ③ — 내가 만든 어림 h3 을 h1·h2 와 겨루게 한다
#
# 이 칸은 앞의 코드와 따로 돌아간다. 필요한 것만 다시 싣는다.
# (Pyodide 는 페이지 안에서만 살기 때문에 "위에서 정의했다"에 기대면 안 된다.)

import heapq
import random

GOAL  = (1, 2, 3, 4, 5, 6, 7, 8, 0)
START = (7, 2, 4, 5, 0, 6, 8, 3, 1)
LIMIT = 400000        # 대기실에 넣는 횟수 상한 — 안전장치다. 빼지 말 것


def neighbors(s):
    i = s.index(0)
    r, c = divmod(i, 3)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):     # 아래·위·오른쪽·왼쪽 순
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            t = list(s)
            t[i], t[j] = t[j], t[i]
            yield tuple(t)


def h1(s):
    """제자리가 아닌 조각의 수."""
    return sum(1 for k in range(9) if s[k] and s[k] != GOAL[k])


def h2(s):
    """맨해튼 거리의 합."""
    d = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)
            d += abs(k // 3 - gi // 3) + abs(k % 3 - gi % 3)
    return d


def h3(s):
    """내가 만드는 어림 — 행이 어긋나면 1점, 열이 어긋나면 1점."""
    n = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)
            # ★ 빈칸 ① — k 번 자리의 '행'과 제자리 gi 의 '행'이 다른가?
            #    힌트: 몇 번째 행인지는 k // 3 으로 안다.
            if ?????:
                n += 1
            # ★ 빈칸 ② — 이번에는 '열'이다.
            #    힌트: 몇 번째 열인지는 k % 3 으로 안다.
            if ?????:
                n += 1
    return n


def astar(hf):
    """7차시 뼈대 그대로. 우선순위만 g + hf 로 준다."""
    openq = [(hf(START), 0, START)]
    g, came = {START: 0}, {START: None}
    seen, push = 0, 0

    while openq:
        f, gc, cur = heapq.heappop(openq)
        if gc > g.get(cur, 10**9):
            continue
        seen += 1
        if cur == GOAL:
            break
        for n in neighbors(cur):
            ng = gc + 1
            if ng < g.get(n, 10**9):
                g[n], came[n] = ng, cur
                heapq.heappush(openq, (ng + hf(n), ng, n))
                push += 1
                if push > LIMIT:               # 안전장치 — 폭주하면 여기서 멈춘다
                    return seen, None, push

    path, cur, walked = [], GOAL, set()
    while cur is not None:
        if cur in walked:                      # 부모 표에 고리가 생겼다면
            return seen, "순환", push
        walked.add(cur)
        path.append(cur)
        cur = came.get(cur)
    return seen, len(path) - 1, push


print("출발 배치에서의 어림값")
print(f"  h1 = {h1(START)}   h3 = {h3(START)}   h2 = {h2(START)}")
print()

print("셋을 겨룬다  (배치는 7 2 4 / 5 _ 6 / 8 3 1)")
for name, hf in [("h1", h1), ("h3", h3), ("h2", h2)]:
    seen, length, push = astar(hf)
    print(f"  {name}   둘러본 상태 {seen:6d}개   최소 이동 {length}회   넣은 횟수 {push:6d}")
print()

print("h1 <= h3 <= h2 인가 — 무작위 배치 2,000개로 반례를 찾는다")
random.seed(20250828)
low, high = 0, 0
for _ in range(2000):
    b = list(range(9))
    random.shuffle(b)
    b = tuple(b)
    if h3(b) < h1(b):
        low += 1
    if h2(b) < h3(b):
        high += 1
print(f"  h3 이 h1 보다 작은 배치 {low}개 · h2 가 h3 보다 작은 배치 {high}개")

# 손으로 ③ — 내가 만든 어림 h3 을 h1·h2 와 겨루게 한다
#
# 이 칸은 앞의 코드와 따로 돌아간다. 필요한 것만 다시 싣는다.
# (Pyodide 는 페이지 안에서만 살기 때문에 "위에서 정의했다"에 기대면 안 된다.)

import heapq
import random

GOAL  = (1, 2, 3, 4, 5, 6, 7, 8, 0)
START = (7, 2, 4, 5, 0, 6, 8, 3, 1)
LIMIT = 400000        # 대기실에 넣는 횟수 상한 — 안전장치다. 빼지 말 것


def neighbors(s):
    i = s.index(0)
    r, c = divmod(i, 3)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):     # 아래·위·오른쪽·왼쪽 순
        nr, nc = r + dr, c + dc
        if 0 <= nr < 3 and 0 <= nc < 3:
            j = nr * 3 + nc
            t = list(s)
            t[i], t[j] = t[j], t[i]
            yield tuple(t)


def h1(s):
    """제자리가 아닌 조각의 수."""
    return sum(1 for k in range(9) if s[k] and s[k] != GOAL[k])


def h2(s):
    """맨해튼 거리의 합."""
    d = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)
            d += abs(k // 3 - gi // 3) + abs(k % 3 - gi % 3)
    return d


def h3(s):
    """내가 만드는 어림 — 행이 어긋나면 1점, 열이 어긋나면 1점."""
    n = 0
    for k in range(9):
        v = s[k]
        if v:
            gi = GOAL.index(v)
            # ★ 빈칸 ① — k 번 자리의 '행'과 제자리 gi 의 '행'이 다른가?
            #    힌트: 몇 번째 행인지는 k // 3 으로 안다.
            if k // 3 != gi // 3:
                n += 1
            # ★ 빈칸 ② — 이번에는 '열'이다.
            #    힌트: 몇 번째 열인지는 k % 3 으로 안다.
            if k % 3 != gi % 3:
                n += 1
    return n


def astar(hf):
    """7차시 뼈대 그대로. 우선순위만 g + hf 로 준다."""
    openq = [(hf(START), 0, START)]
    g, came = {START: 0}, {START: None}
    seen, push = 0, 0

    while openq:
        f, gc, cur = heapq.heappop(openq)
        if gc > g.get(cur, 10**9):
            continue
        seen += 1
        if cur == GOAL:
            break
        for n in neighbors(cur):
            ng = gc + 1
            if ng < g.get(n, 10**9):
                g[n], came[n] = ng, cur
                heapq.heappush(openq, (ng + hf(n), ng, n))
                push += 1
                if push > LIMIT:               # 안전장치 — 폭주하면 여기서 멈춘다
                    return seen, None, push

    path, cur, walked = [], GOAL, set()
    while cur is not None:
        if cur in walked:                      # 부모 표에 고리가 생겼다면
            return seen, "순환", push
        walked.add(cur)
        path.append(cur)
        cur = came.get(cur)
    return seen, len(path) - 1, push


print("출발 배치에서의 어림값")
print(f"  h1 = {h1(START)}   h3 = {h3(START)}   h2 = {h2(START)}")
print()

print("셋을 겨룬다  (배치는 7 2 4 / 5 _ 6 / 8 3 1)")
for name, hf in [("h1", h1), ("h3", h3), ("h2", h2)]:
    seen, length, push = astar(hf)
    print(f"  {name}   둘러본 상태 {seen:6d}개   최소 이동 {length}회   넣은 횟수 {push:6d}")
print()

print("h1 <= h3 <= h2 인가 — 무작위 배치 2,000개로 반례를 찾는다")
random.seed(20250828)
low, high = 0, 0
for _ in range(2000):
    b = list(range(9))
    random.shuffle(b)
    b = tuple(b)
    if h3(b) < h1(b):
        low += 1
    if h2(b) < h3(b):
        high += 1
print(f"  h3 이 h1 보다 작은 배치 {low}개 · h2 가 h3 보다 작은 배치 {high}개")

출발 배치에서 h1 = 6, h3 = 9, h2 = 14. 예상대로 h3이 가운데에 놓입니다.

둘러본 상태는 h1 3,667개 · h3 891개 · h2 283개이고 셋 다 최소 이동 20회입니다. 대기실에 넣은 횟수는 5,750 / 1,427 / 451. 어림값의 순서가 성능의 순서와 그대로 맞아떨어집니다.

무작위 2,000개 검사에서 h3 < h1도 h2 < h3도 0개입니다. 9! = 362,880가지를 전부 재 봐도 마찬가지예요 — h3 < h1 0개, h2 < h3 0개, 두 값이 같아지는 경우는 각각 4,480개와 6,204개, 가장 크게 벌어진 차는 8과 10이었습니다.

그런데 h3을 만들었다고 h2를 버릴 이유는 없습니다. h2가 여전히 셋 중 가장 좋아요. 오늘 배운 규칙대로라면 허용 가능하면서 값이 더 큰 어림을 찾아야 이깁니다. 그것이 8-퍼즐에서도 아직 연구 주제입니다(맨 끝 '더 알아보기'의 두 번째 카드를 보세요).

📖

정리 — 옮겨 붙이며 실제로 손댄 곳

7차시 미로와 오늘 8-퍼즐을 나란히 놓으면 이렇습니다.

부분	7차시 · 미로	오늘 · 8-퍼즐	손댔나
`astar()` 본문	그대로	그대로	—
대기실 · f = g + h · 경로 복원	그대로	그대로	—
안전장치(순환 감지 · 상한 검사)	그대로	그대로	—
`neighbors()`	벽 아닌 옆 칸	빈칸을 민 결과	함수를 고침
`h()`	맨해튼 거리	h1 · h2 · h3	함수를 고침
`START` · `GOAL`	(0,0) · (6,11)	아홉 수 튜플	값을 새로 적음
`LIMIT`	20,000	400,000	값을 새로 적음
상태의 수	65	181,440	—
최적해	17걸음	20회	—
A*가 둘러본 것	52칸	283개 (h2)	—

오늘 얻은 것을 세 줄로 줄이면 이렇습니다.

1

A*는 문제를 가리지 않는다

상태 · 이웃 · 어림 세 자리만 갈아 끼우면 전혀 다른 문제에 붙는다. astar() 본문은 한 글자도 안 고쳤다.

2

어림의 질이 계산량을 가른다

48,390 → 3,667 → 283. 답은 셋 다 20회로 같다. 허용 가능하면서 값이 더 큰 어림이 이긴다.

3

'못 찾았다'와 '없다'는 다르다

끝까지 뒤져 빈손이면 '없다'의 증명이고, 상한에 걸려 멈춘 것은 증명이 아니다. 홀짝성은 뒤지기 전에 답한다.

다음 9차시에는 또 한 번 갈아 끼웁니다. 이번에는 neighbors()도 h()도 아니라 한 걸음의 비용이에요. 잔디는 1, 모래는 3, 물은 5 — 코드에서 바뀌는 것은 ng = gc + 1의 1 한 글자인데, '가장 짧은 길'이라는 말의 뜻이 바뀝니다. 오늘은 문제를 갈아 끼웠고, 다음 시간에는 비용을 갈아 끼웁니다. 오늘 이 감각을 손에 익혀 두면 그때가 훨씬 수월해요.

🔁 되돌아보기 — 한 줄로

오늘 어림 하나를 바꿔 둘러본 상태가 48,390에서 283으로 줄어드는 것을 직접 재 보았습니다. 그중 가장 이해가 덜 된 대목 하나를 골라 한 줄로 적어 보세요. (예: "h2가 h1보다 크면 왜 덜 둘러보게 되는지가 아직 어렴풋하다") 다음 시간에는 비용이 다른 지도에서 같은 astar()를 또 한 번 굴립니다.

✅

확인 문제

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.

1. 미로용 A*를 8-퍼즐용으로 옮기며 실제로 고쳐 쓴 함수 두 개를 쓰고, 그 밖에 새로 적은 값 세 개를 쓰시오. 그리고 고치지 않아도 됐던 부분을 셋 이상 드시오.

📖 모범 답안

고친 함수 둘 — neighbors()(벽 아닌 옆 칸 → 빈칸을 민 결과)와 h()(맨해튼 거리 → h1 또는 h2).

새로 적은 값 셋 — START, GOAL, 그리고 안전장치 상한 LIMIT(20,000 → 400,000). 상한을 올린 까닭은 갈 수 있는 칸 65개짜리 미로에서 갈 수 있는 상태 181,440개짜리 퍼즐로 옮겨 왔기 때문이다.

고치지 않은 부분 — ① 대기실(우선순위 큐)에서 f가 가장 작은 것을 꺼내는 규칙, ② g 표와 '더 싼 길일 때만 갱신' 조건, ③ 부모 표를 거꾸로 되짚는 경로 복원, ④ 순환 감지와 상한 검사 같은 안전장치. 이 부분들은 '칸'이나 '벽'을 전혀 모른다 — 그래서 문제가 바뀌어도 그대로 돈다.

2. h1과 h2를 각각 한 문장으로 정의하고, 배치 (1, 2, 3, 4, 5, 6, 0, 7, 8)에 대해 두 값을 계산하시오. 이 배치에서 두 값이 왜 같아지는지도 쓰시오.

📖 모범 답안

h1 = 목표에서의 제자리와 다른 곳에 있는 조각의 수(빈칸은 세지 않는다).
h2 = 조각마다 제자리까지 가야 하는 칸 수(맨해튼 거리)를 모두 더한 값.

판으로 그리면 1 2 3 / 4 5 6 / _ 7 8이다. 제자리가 아닌 조각은 7과 8 둘뿐이므로 h1 = 2. 7은 제자리에서 오른쪽으로 한 칸, 8도 오른쪽으로 한 칸 밀려 있으므로 h2 = 1 + 1 = 2.

두 값이 같은 까닭은 어긋난 조각이 전부 딱 한 칸씩만 어긋나 있기 때문이다. h2는 어긋난 조각마다 '거리'를 더하는데 그 거리가 모두 1이면 결국 '어긋난 조각의 개수'와 같아진다. (실제 최단도 2수다.)

3. 오늘 직접 돌려 얻은 결과다. 원장 배치 (7,2,4,5,0,6,8,3,1)에서 어림 넷을 겨루게 했을 때 둘러본 상태 수와 최소 이동을 표로 적고, h2가 '어림 없음'과 h1에 대해 각각 몇 배 이득인지 계산하시오. 그리고 이 표로 '좋은 어림'의 값어치를 한 문장으로 평가하시오.

📖 모범 답안

어림 없음 48,390개 / h1 3,667개 / h3 891개 / h2 283개 — 최소 이동은 넷 다 20회.

배율은 48,390 ÷ 283 = 171.0배, 3,667 ÷ 283 = 13.0배.

평가 예시 — "어림은 답을 바꾸지 않는다. 답에 닿기까지 들춰 보는 상태의 수만 바꾼다. 그런데 그 수가 171배 차이 나므로, 어림을 고르는 일은 알고리즘을 바꾸는 일만큼 크다."

⚠️ 표를 옮겨 적을 때는 어느 배치인지를 반드시 함께 적을 것. 배치가 바뀌면 네 숫자가 전부 바뀐다 — 최적해가 31수인 배치 (6,4,7,8,5,0,3,2,1)에서는 181,439 / 143,849 / 65,822 / 21,198이었다(넷 다 31회).

4. 오늘 시뮬레이터에서 만든 것이다. h1과 h2가 같아지는 배치를 하나 적고, 왜 같아졌는지 설명하시오. 또 🎲 아무 배치를 눌러 가며 찾은 h2 − h1의 가장 큰 값은 얼마였는지 적고, h2 < h1인 배치를 찾을 수 있었는지 쓰시오.

📖 모범 답안

같아지는 배치의 조건은 하나다 — 제자리가 아닌 조각이 전부 딱 한 칸씩만 어긋나 있을 것. 견본은 (1,2,3,4,5,6,0,7,8)로 h1 = h2 = 2. 조각 두 개를 서로 이웃한 자리에서 맞바꾼 배치는 대체로 이 조건을 만족한다.

h2 − h1의 최댓값은 9! = 362,880가지를 전부 재면 14다. 무작위로 눌러서는 13쯤까지 나오는 것이 보통이다.

h2 < h1인 배치는 없다. 무작위 1,000개에서도 0개, 362,880가지 전부에서도 0개였다. 까닭은 계산이 아니라 정의에서 나온다 — 제자리가 아닌 조각은 거리가 적어도 1이고 제자리 조각은 0이므로, 거리를 다 더한 h2는 '제자리 아닌 조각의 개수'인 h1보다 작아질 수가 없다. 실험은 이 논증을 확인해 줄 뿐, 논증을 대신하지는 못한다.

5. 못 푸는 배치 (2,8,1,4,6,3,0,7,5)를 넣었을 때 프로그램의 출력이 무엇이었는지 쓰고, '답을 못 찾았다'와 '답이 없다'를 구별해 설명하시오. 또 이 배치에서 어림을 h1이나 '어림 없음'으로 바꾸면 결과가 달라지는지 쓰시오.

📖 모범 답안

출력은 둘러본 상태 181,440개 · 경로 없음 — 다 뒤졌다였다. 181,440은 이 배치에서 갈 수 있는 상태 전부다.

구별 — 탐색이 끝까지 돌아 대기실이 비었는데도 목표를 못 만났다면, 그것은 '아직 못 찾았다'가 아니라 '없다'가 증명된 것이다. 반면 상한(LIMIT)에 걸려 멈추거나 시간이 다 되어 중단한 것은 아무것도 증명하지 못한다 — 더 뒤졌으면 나왔을 수도 있다. 화면에 뜬 글자가 비슷해 보여도 두 결과의 뜻은 완전히 다르다.

어림을 바꿔도 181,440개로 똑같다. 어림 없음도, h1도, h2도 전부. 어림은 '답 쪽으로 먼저 가 보게 하는' 장치인데 답이 없으니 할 일이 없기 때문이다. 그리고 이 사실을 한 수도 두어 보기 전에 알려 주는 것은 A*가 아니라 뒤집힌 짝을 세는 홀짝성 검사 한 줄이다.

6. 어림을 통째로 3만큼 부풀린 h2 + 3을 쓰면 최소 이동 20회가 유지될지, 둘러본 상태 수는 늘어날지 줄어들지 먼저 예측한 뒤 실행해 확인하시오. 그리고 그 결과가 7차시에서 h에 w를 곱했을 때와 왜 다른지 설명하시오.

📖 모범 답안

283개 · 451회 · 20회 — h2와 완전히 같다. 늘지도 줄지도 않는다. 많은 학생이 "조금 더 둘러볼 것"이라고 예측하는데 그렇지 않다.

까닭 — A*가 보는 것은 f의 크기가 아니라 순서다. 모든 상태의 f에 똑같이 3을 더하면 순서가 하나도 안 바뀐다. 대기실에서 꺼내는 차례가 같으니 둘러보는 상태도 똑같다.

7차시의 곱하기와 다른 점 — w × h는 상태마다 다르게 커진다. 목표에서 먼 상태(h가 큰)는 많이 커지고 가까운 상태(h가 작은)는 조금 커지므로 순서가 바뀐다. 그래서 미로에서 w를 1.1로만 올려도 둘러본 칸이 52 → 21로 뚝 떨어졌던 것이다. (그때도 경로는 17걸음 그대로였다 — 미로에서 최단이 처음 깨지는 값은 w = 3.1이다. 덜 둘러보는 것과 최단이 깨지는 것은 서로 다른 문턱이다.)

덧붙여 — 8-퍼즐에서 h2를 5배로 부풀려도 최소 이동은 20회 그대로(59개)다. 미로에서는 5배가 곧바로 17 → 19걸음으로 깨졌는데도. "부풀리면 최단이 깨진다"는 문제마다 다르다. 반면 h1은 5배에서 22회로 깨진다 — 같은 5배인데 어림에 따라 결과가 갈린다.

🔎

더 알아보기

홀짝성이 닫아 버린 옛 도전, h2보다 센 어림, 그리고 판이 커질 때 A*가 모양을 바꾸는 법

흑백 삽화 — 말과 쟁기를 세워 둔 밭고랑에 농부가 무릎을 꿇고 머리를 싸매고 있고, 그 앞에 1부터 12까지는 차례대로지만 맨 아랫줄이 13·15·14인 15-퍼즐 판이 놓여 있다. 위에 'THE 14-15 PUZZLE IN PUZZLELAND'라는 제목이 있다

역사

풀 수 없는 퍼즐에 걸린 상금 — 14-15 퍼즐

1880년 무렵 4×4짜리 15-퍼즐이 미국과 유럽에서 크게 유행했습니다. 그 열풍 속에서 가장 유명해진 도전이 그림 속 배치예요 — 맨 아랫줄의 14와 15만 서로 바뀐 판을 원래대로 맞추는 것. 그림은 퍼즐 작가 샘 로이드가 1914년에 펴낸 퍼즐 모음집에 실린 삽화로, 밭을 갈다 말고 퍼즐 앞에 무릎을 꿇은 채 머리를 싸맨 농부를 그렸습니다.

로이드는 훗날 자기가 이 퍼즐을 만들었고 이 배치에 1,000달러의 상금을 걸었다고 적었지만, 퍼즐 역사가들은 그 주장을 뒷받침할 기록을 찾지 못했습니다. 퍼즐을 처음 만든 사람은 뉴욕주의 우체국장 노이스 채프먼으로 알려져 있어요. 확실한 것은 하나, 이 배치를 맞춘 사람은 아무도 없었다는 것입니다. 유행이 번지기 직전인 1879년에 이미 수학자 존슨과 스토리가 배치의 절반은 결코 풀 수 없다는 증명을 학술지에 실었거든요.

오늘 배운 잣대로 보면 까닭은 한 줄입니다. 목표와 견주어 뒤집힌 짝이 딱 하나 늘어난 배치이기 때문이에요. 판이 4×4이면 빈칸이 있는 줄까지 함께 따져야 하지만, 이 경우는 빈칸이 제자리에 그대로 있어서 뒤집힌 짝 하나만으로 판정이 끝납니다. 많은 사람이 매달렸던 문제를, 세는 법을 아는 사람은 1분 만에 닫습니다 — 탐색을 잘하는 것과 탐색이 필요 없음을 아는 것은 다른 능력이에요.

사진: 샘 로이드의 삽화 「The 14-15 Puzzle in Puzzleland」(1914) · 출처: Sam Loyd, scanned by Ed Pegg Jr, 2005, Wikimedia Commons (Public domain)

원리 더 깊이

h2보다 센 어림은 없을까 — 선형 충돌과 패턴 데이터베이스

있습니다. 하나만 맛보면 선형 충돌(linear conflict)입니다. 그림처럼 같은 줄에 있어야 할 조각 둘이 이미 그 줄에 있는데 순서가 서로 뒤바뀐 경우를 보세요. 맨해튼 거리는 둘이 좌우로 비켜 앉은 칸 수만 세어 1 + 1 = 2라고 말합니다. 그런데 한 줄 안에서는 두 조각이 서로를 지나갈 수 없어서, 한 조각이 줄 밖으로 비켜 줬다가 돌아와야 하지요. 맨해튼 거리가 세지 못한 2수가 더 듭니다. 그만큼을 h2에 더해도 여전히 참값을 넘지 않아요.

더 나아가면 패턴 데이터베이스가 있습니다. 1990년대 후반 컬버슨과 섀퍼가 제안한 방법으로, 조각을 몇 개씩 묶어 '이 조각들만 제자리로 보내는 데 최소 몇 수인가'를 미리 전부 계산해 표로 저장해 두고, 탐색할 때는 표를 찾아보기만 합니다. 계산은 한 번 크게 해 두고, 어림은 표 한 칸을 읽는 값으로 싸게 얻는 것이지요.

두 방법의 공통점을 보세요. 새 어림을 만드는 일은 언제나 같은 물음입니다 — "참값을 넘지 않으면서 값을 더 크게 만들 수 있는가?" 오늘 여러분이 h3을 만들며 던진 물음과 똑같고, 오늘 표에서 본 대로 그 답이 '예'일수록 둘러보는 상태가 줄어듭니다.

현장

15-퍼즐에서는 왜 A로도 벅찰까 — 기억하지 않고 다시 뒤지는 IDA

8-퍼즐은 갈 수 있는 상태가 181,440개였습니다. 4×4짜리 15-퍼즐은 10,461,394,944,000개(16! ÷ 2, 약 1.05×10¹³)로, 8-퍼즐의 정확히 57,657,600배입니다(16! ÷ 9!). 여기서 A*의 약점이 드러나요. A*는 대기실과 g 표에 둘러본 상태를 전부 기억합니다. 오늘 어림 없이 돌렸을 때 48,390개를 꺼내 보며 그 이웃까지 표에 적어 두었지요. 15-퍼즐에서 그런 식으로 뒤지면 시간보다 메모리가 먼저 바닥납니다.

1985년 리처드 코프가 내놓은 IDA*(반복 깊이증가 A*)는 이 문제를 비켜 갑니다. "f가 문턱 이하인 길만 깊이 우선으로 따라가 본다 → 목표가 없으면 문턱을 올려 처음부터 다시"를 되풀이해요. 그림은 오늘의 출발 배치에 h2를 붙여 실제로 돌린 결과입니다(바로 전 상태로 되돌아가는 수만 막은 구현). h2가 14에서 시작하니 첫 문턱은 14이고, 목표가 없을 때마다 16, 18로 올라가 20에서 최단 20수를 찾습니다. 같은 곳을 여러 번 뒤지는 손해를 보는 대신, 기억하는 것은 지금 걷는 길 하나뿐이에요.

코프는 이 방법으로 무작위 15-퍼즐 배치들의 최단 해를 처음으로 구했고, 1997년에는 IDA*에 패턴 데이터베이스 어림을 붙여 본문 사진의 루빅스 큐브에서도 최단 해를 찾아냈습니다. 무엇이 부족한 자원인가 — 시간인가, 메모리인가 — 에 따라 알고리즘의 모양이 바뀐다는 것이 탐색을 배우며 마지막에 남는 감각입니다.

미로 밖으로8-퍼즐에 같은 A*를 옮겨 붙이기

여는 장면 — 우리가 배운 것은 A*인가, 미로인가

갈아 끼우는 자리는 셋뿐이다

7차시 · 미로용 이웃

오늘 · 퍼즐용 이웃

퍼즐을 상태로 적는다 — 왜 하필 튜플인가

판

상태

같은 문제에 어림이 둘 — h1과 h2

🔢 h1 — 제자리가 아닌 조각 수

📏 h2 — 맨해튼 거리의 합

왜 둘 다 '허용 가능'한가

h2가 h1을 '지배한다'

어림 하나가 계산량을 171배 가른다

왜 지배하는 어림이 덜 둘러보는가

못 푸는 배치가 있다 — 뒤집힌 짝의 홀짝

원장 배치 — 풀 수 있다

못 푸는 배치

손으로 ① — 판을 밀어 보고, 어림을 재고, A*에게 맡긴다

과제 ① 표를 채운다 — 어림 넷을 겨루게 한다

과제 ② 반례를 만든다 — h1과 h2가 같아지는 배치

과제 ③ 못 푸는 배치를 만난다

손으로 ② — 코드에서 정말 두 함수만 바뀌었는지 확인한다

손으로 ③ — 어림을 내가 만들어 h2와 겨룬다

정리 — 옮겨 붙이며 실제로 손댄 곳

A*는 문제를 가리지 않는다

어림의 질이 계산량을 가른다

'못 찾았다'와 '없다'는 다르다

확인 문제

더 알아보기

풀 수 없는 퍼즐에 걸린 상금 — 14-15 퍼즐

h2보다 센 어림은 없을까 — 선형 충돌과 패턴 데이터베이스

15-퍼즐에서는 왜 A*로도 벅찰까 — 기억하지 않고 다시 뒤지는 IDA*

미로 밖으로
8-퍼즐에 같은 A*를 옮겨 붙이기

15-퍼즐에서는 왜 A로도 벅찰까 — 기억하지 않고 다시 뒤지는 IDA