Swap Game — bài giảng BFS cho người mới

Đề bài

Bạn có 1 bảng $3 \times 3$ chứa các số từ 1 đến 9, sắp xếp lộn xộn. Mỗi lần bạn được phép đổi chỗ 2 ô kề nhau (kề ngang hoặc kề dọc). Hỏi ít nhất bao nhiêu lần swap để về bảng đã sắp xếp:

Sample đề ra: start swap 4 lần là về target. Nhưng mà — làm sao biết chắc 4 là nhỏ nhất? Không phải 3? Không phải 5? Đó là câu hỏi cả bài này sẽ trả lời.

"Một bước" là gì? — mỗi bảng có đúng 12 neighbors

Trước khi nghĩ đến thuật toán, ta phải hiểu rõ 1 bước làm được gì. Từ 1 bảng bất kỳ, bạn swap 2 ô kề nhau → ra 1 bảng mới. Có bao nhiêu cách?

Đếm các cặp kề nhau, không phải các ô: bảng $3 \times 3$ có 2 cặp ngang × 3 hàng = 6 swap ngang, và 2 cặp dọc × 3 cột = 6 swap dọc. Tổng = 12 neighbors. Dưới đây là 12 bảng bạn có thể đến trong đúng 1 swap từ start. Hover/tap vào bất kỳ bảng nhỏ nào để thấy cặp ô đã swap.

Mỗi bảng trong 12 bảng này lại có 12 neighbors của riêng nó. Cứ thế mở rộng ra, bạn được 1 đồ thị khổng lồ với các bảng là đỉnh (node) và các swap là cạnh (edge). Đó chính là đồ thị mà BFS sẽ chạy trên.

Đồ thị lớn cỡ nào? — $9! = 362{,}880$

Mỗi state (trạng thái) là 1 cách sắp xếp các số 1..9 vào 9 ô. Số cách = $9! = 362{,}880$. Không quá lớn — máy tính chạy trong milligiây.

Tưởng tượng thế này: hãy hình dung $362{,}880$ chấm điểm trên tường. Mỗi chấm là 1 bảng khác nhau. Giữa 2 chấm có 1 đường kẻ nếu chúng khác nhau đúng 1 swap kề. Chấm bên trái là start của bạn, chấm bên phải là target $[1..9]$. Nhiệm vụ: tìm dãy đường kẻ ngắn nhất nối start đến target.

Đó chính là bài toán đường đi ngắn nhất trên đồ thị không trọng số. Và có đúng 1 thuật toán cực kỳ đơn giản giải được: BFS.

Tại sao không dùng các thứ khác?

Ý tưởng BFS: "nở ra" từng lớp đồng tâm

Từ start, hãy đánh dấu mọi node bằng khoảng cách ngắn nhất tới nó. BFS xây dần các lớp này theo thứ tự $0, 1, 2, 3, \ldots$:

• Lớp 0: chỉ có start (1 node).
• Lớp 1: tất cả node cách start đúng 1 bước ⇒ 12 bảng (từ §2).
• Lớp 2: tất cả node cách đúng 2 bước (không kể các node đã thuộc lớp 0, 1).
• Cứ thế…

Câu then chốt: target thuộc lớp $k$ nào thì $k$ chính là đáp án. Không có đường nào ngắn hơn vì BFS đã quét hết các lớp $0, 1, \ldots, k-1$ mà không thấy target. Đây là invariant của BFS: lần đầu gặp 1 node = khoảng cách nhỏ nhất.

Với sample đề ra, target nằm ở lớp 4 → đáp án = 4. Lớp 0 có 1 state, lớp 1 có 12, lớp 2 có ~100, lớp 3 có ~1000, lớp 4 có ~9000 — tổng < 11,000 state cần duyệt trước khi ra đáp án. Rất rẻ so với $362{,}880$.

BFS chạy thực tế trên 1 đồ thị nhỏ

Trước khi quay lại bài swap game (với $9!$ node), hãy xem BFS chạy trên 1 đồ thị chỉ 5 node cho dễ hiểu. Ta có các node A, B, C, D, E, start = A, target = E. BFS dùng 2 thứ:

• Queue (hàng đợi) — danh sách các node chờ duyệt, kiểu FIFO (ai vào trước ra trước).
• Visited set — đánh dấu node nào đã gặp rồi, để không lặp lại.

Vòng lặp chính của BFS:

queue.push(start); visited.add(start)
while queue not empty:
    cur = queue.pop_front()      // lấy node đầu queue
    if cur == target: return dist[cur]
    for each neighbor n of cur:
        if n not in visited:
            visited.add(n)
            dist[n] = dist[cur] + 1
            queue.push_back(n)

Bấm Next ▶ để thấy từng bước. Chú ý 3 thứ thay đổi mỗi bước: (1) node nào là current, (2) queue thay đổi, (3) visited set lớn dần. Đặc biệt để ý bước 4: ta thử thêm node D vào queue nhưng D đã trong visited → đó chính là lúc "visited set" cứu BFS khỏi vòng lặp vô tận.

Quay lại Swap Game — đáp án là 4

Bây giờ bạn đã hiểu BFS. Thay cụm "nhỏ 5-node graph" bằng "đồ thị 362,880 node với mỗi node là 1 bảng 3×3", mọi thứ còn lại y hệt. BFS chạy, quét lớp 0, 1, 2, 3, rồi đến lớp 4 mới gặp target. Đáp án = 4.

Dưới đây là 1 trong các dãy swap tối ưu BFS có thể trả về. Bấm Next ▶ hoặc Play để xem 4 move:

Code thực tế

Bây giờ đọc lại đoạn code "kinh điển" ở đầu chương, bạn sẽ thấy nó chỉ là vòng lặp BFS ở §6, với state = bảng 3×3 được mã hóa thành số nguyên base-9 cho nhanh.

#include <bits/stdc++.h>
using namespace std;

int powers[10];
int move(int grid, int i, int j) {  // swap cell i và j, trả grid mới
    int a = grid % powers[i+1] / powers[i];
    int b = grid % powers[j+1] / powers[j];
    return grid - a*powers[i] - b*powers[j] + b*powers[i] + a*powers[j];
}

int main() {
    powers[0] = 1;
    for (int i = 1; i < 10; i++) powers[i] = 9 * powers[i-1];
    vector<bool> vis(powers[9], false);

    int target = 0;                  // bảng 1..9
    for (int i = 8; i >= 0; i--) target += (8-i) * powers[i];

    int grid = 0, num;               // đọc input
    for (int i = 8; i >= 0; i--) { cin >> num; grid += (num-1)*powers[i]; }

    queue<pair<int,int>> q;          // {state, distance}
    q.push({grid, 0});
    vis[grid] = true;
    while (!q.empty()) {
        auto [g, dist] = q.front(); q.pop();
        if (g == target) { cout << dist; return 0; }

        for (int i = 0; i < 8; i++) {        // 6 swap ngang
            if (i % 3 == 2) continue;
            int g2 = move(g, 8-i, 8-(i+1));
            if (!vis[g2]) { vis[g2] = true; q.push({g2, dist+1}); }
        }
        for (int i = 0; i < 6; i++) {        // 6 swap dọc
            int g2 = move(g, 8-i, 8-(i+3));
            if (!vis[g2]) { vis[g2] = true; q.push({g2, dist+1}); }
        }
    }
}

Hai vòng for kia chính là chỗ sinh ra 12 neighbors (6 ngang + 6 dọc) bạn đã thấy ở §2. vis[] là visited set. q là queue. Không có gì bí ẩn.

Nhớ những gì