Swap Game — Visualization-First Editorial (v3)

1. Bài toán, nhìn bằng hình

Mỗi nước đi = hoán đổi 2 ô chia cạnh. 6 cặp ngang + 6 cặp dọc = 12 edge per state.

2. Vì sao brute force không làm nổi

State space bùng nổ theo n!. DFS không cắt = nổ stack. Nhưng 9! vẫn vừa bộ nhớ ⇒ vẫn duyệt được, chỉ cần duyệt đúng cách.

3. Insight

Mỗi swap = 1 edge với trọng số = 1. Trên đồ thị không trọng số, BFS từ start trả về khoảng cách ngắn nhất tới mọi trạng thái — bao gồm target.

4. BFS chạy trên chính input này

5. Đi lại từng bước

Pop 312/456/789 (depth 0). Sinh 12 neighbor. Một trong số đó là 132/456/789.

Pop 132/456/789 (depth 1). Neighbor thứ 2 của nó là 123/456/789 = target. Trả về dist = 2.

Visited set cứu chúng ta khỏi push trùng. Không có nó, queue phình theo 12^depth.

6. Code (click từng dòng để widget seek)

from collections import deque
target = (1,2,3,4,5,6,7,8,9)
EDGES = [(0,1),(1,2),(3,4),(4,5),(6,7),(7,8),
         (0,3),(1,4),(2,5),(3,6),(4,7),(5,8)]
def solve(start):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        s, d = q.popleft()
        if s == target: return d
        for i, j in EDGES:
            t = list(s)
            t[i], t[j] = t[j], t[i]
            t = tuple(t)
            if t not in seen:
                seen.add(t)
                q.append((t, d+1))

7. Biến thể & bẫy

n×n tổng quát. n≤4 còn BFS được (16! ≈ 2·10¹³ — quá lớn, cần A* với Manhattan).
Swap bất kỳ (không cần kề). Đáp án = n² − số chu trình của hoán vị. Công thức đóng, không cần BFS.
Quên visited set. Queue phình mũ, TLE/MLE ngay cả với n=3.