Bài 10: Máy tính giải Sudoku trong tích tắc thế nào? Thuật toán quay lui và cắt nhánh

Một ô Sudoku khó có thể khiến bạn mất cả buổi tối. Máy tính giải nó trong chưa tới một phần nghìn giây – và không phải nhờ "thông minh" hơn, mà nhờ một chiến lược rất có hệ thống: thử, sai thì quay lại. Đó là thuật toán quay lui (backtracking).

Bài thứ mười của chuyên mục "Thuật toán trong đời sống". Quay lui là kỹ thuật nền tảng trong chương trình chuyên Tin – từ bài liệt kê hoán vị, xếp 8 quân hậu đến các bài tìm kiếm trong đề HSG.

1. Sudoku đến từ đâu?

• Theo Đài phát thanh công cộng bang Indiana (Mỹ), câu đố được sáng tạo bởi Howard Garns, một kiến trúc sư ở Indianapolis, và xuất hiện lần đầu năm 1979 trên tạp chí của Dell với tên "Number Place".
• Nhà xuất bản Nikoli của Nhật Bản (do Maki Kaji thành lập năm 1983) đưa câu đố về Nhật và đặt tên rút gọn thành "Sudoku" – nghĩa gốc là "các chữ số phải đứng một mình". Theo NBC News, Sudoku có khoảng 200 triệu người chơi ở 100 quốc gia.
• Theo Đại học Cornell, năm 2005 Bertram Felgenhauer và Frazer Jarvis dùng máy tính đếm được có 6.670.903.752.021.072.936.960 lưới Sudoku hoàn chỉnh khác nhau.

2. Thuật toán quay lui

Ý tưởng giống như đi trong mê cung: gặp ngã rẽ thì chọn một đường; đi tới ngõ cụt thì quay lại ngã rẽ gần nhất và thử đường khác.

1. Tìm một ô trống.
2. Thử lần lượt các số 1 đến 9. Với mỗi số không trùng hàng, cột và khối 3×3, đặt vào rồi đệ quy giải tiếp phần còn lại.
3. Nếu phần còn lại không giải được, xóa số vừa đặt (quay lui) và thử số tiếp theo.
4. Nếu không số nào hợp lệ, báo thất bại cho tầng đệ quy phía trên.

5	3			7
6			1	9	5
	9	8					6
8				6				3
4			8		3			1
7				2				6
	6					2	8
			4	1	9			5
				8			7	9

Đề bài (30 số cho trước)

5	3	4	6	7	8	9	1	2
6	7	2	1	9	5	3	4	8
1	9	8	3	4	2	5	6	7
8	5	9	7	6	1	4	2	3
4	2	6	8	5	3	7	9	1
7	1	3	9	2	4	8	5	6
9	6	1	5	3	7	2	8	4
2	8	7	4	1	9	6	3	5
3	4	5	2	8	6	1	7	9

Lời giải (số màu xanh do máy điền)

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
int a[9][9]; long long calls = 0;
bool ok(int r, int c, int v){
    for(int i = 0; i < 9; i++)
        if(a[r][i] == v || a[i][c] == v || a[r/3*3 + i/3][c/3*3 + i%3] == v) return false;
    return true;
}
bool solve(){
    calls++;
    for(int r = 0; r < 9; r++) for(int c = 0; c < 9; c++) if(a[r][c] == 0){
        for(int v = 1; v <= 9; v++) if(ok(r, c, v)){
            a[r][c] = v;              // thử đặt v
            if(solve()) return true;
            a[r][c] = 0;              // sai thì quay lui
        }
        return false;                 // không số nào hợp lệ -> báo cho tầng trên
    }
    return true;                      // không còn ô trống: đã giải xong
}
int main(){
    string s =
        "530070000" "600195000" "098000060"
        "800060003" "400803001" "700020006"
        "060000280" "000419005" "000080079";
    for(int i = 0; i < 81; i++) a[i/9][i%9] = s[i] - '0';
    if(solve()){
        for(int r = 0; r < 9; r++){ for(int c = 0; c < 9; c++) cout << a[r][c]; cout << "\n"; }
        cout << "So lan goi de quy: " << calls << "\n";
    }
}

grid = [list(map(int, row)) for row in [
    "530070000", "600195000", "098000060",
    "800060003", "400803001", "700020006",
    "060000280", "000419005", "000080079"]]

def ok(r, c, v):
    br, bc = r // 3 * 3, c // 3 * 3
    return all(grid[r][i] != v and grid[i][c] != v and
               grid[br + i // 3][bc + i % 3] != v for i in range(9))

def solve():
    for r in range(9):
        for c in range(9):
            if grid[r][c] == 0:
                for v in range(1, 10):
                    if ok(r, c, v):
                        grid[r][c] = v        # thử
                        if solve(): return True
                        grid[r][c] = 0        # quay lui
                return False
    return True

solve()
print("\n".join("".join(map(str, row)) for row in grid))

Với đề bài trên (51 ô trống), chương trình gọi đệ quy 4.209 lần – vẫn xong ngay lập tức.

3. Cắt nhánh: chọn ô "khó" nhất trước

Thay vì điền ô trống theo thứ tự từ trái sang phải, ta chọn ô có ít khả năng nhất (heuristic MRV – Minimum Remaining Values). Ô chỉ còn một số hợp lệ thì điền ngay, không phải đoán.

Cách chọn ô	Số lần gọi đệ quy
Lần lượt từ trái sang phải	4.209
Ô ít khả năng nhất trước (MRV)	52

Với MRV, chương trình gần như không phải quay lui lần nào: 51 ô trống, 52 lần gọi. Đây chính là cách người chơi giỏi làm – tìm ô "chắc chắn" trước.

Bài học: cùng một thuật toán quay lui, thứ tự thử khác nhau có thể làm số trạng thái chênh lệch hàng trăm lần. Trong đề thi, kỹ thuật cắt nhánh thường là ranh giới giữa "chạy kịp" và "quá thời gian".

4. Dancing Links của Donald Knuth

Sudoku là một trường hợp của bài toán phủ chính xác (exact cover): chọn các "lựa chọn" (đặt số v vào ô (r, c)) sao cho mỗi ràng buộc – mỗi ô có một số, mỗi hàng/cột/khối có đủ 1–9 – được thỏa đúng một lần.

Năm 2000, Donald Knuth công bố bài báo "Dancing Links". Ông viết rằng Algorithm X "đơn giản là cách thử–sai hiển nhiên", và mẹo nằm ở cấu trúc dữ liệu: dùng danh sách liên kết đôi, một phần tử bị gỡ ra có thể được gắn lại chỉ cần biết chính nó – giúp thao tác quay lui cực nhanh.

5. Sudoku có "khó" thật không?

• Năm 2003, Takayuki Yato và Takahiro Seta chứng minh phiên bản tổng quát n²×n² của Sudoku (Number Place) là NP-đầy đủ. Với lưới 9×9 thì máy tính vẫn giải dễ dàng, nhưng khi lưới lớn dần, chưa ai biết thuật toán nhanh.
• Năm 2012, Gary McGuire và cộng sự dùng máy tính chứng minh không tồn tại Sudoku chỉ có 16 số cho trước mà có lời giải duy nhất – vậy con số tối thiểu là 17. Họ ghi rằng thuật toán quay lui tiêu chuẩn không đủ nhanh, phải thiết kế thuật toán mới.

6. Bạn học được gì từ đây?

• Quay lui = đệ quy + hoàn tác. Đây là "vũ khí" cho mọi bài liệt kê, tìm kiếm cấu hình.
• Cắt nhánh và thứ tự thử quyết định tốc độ.
• Quay lui cũng dùng trong lập lịch, giải mạch logic, kiểm chứng phần mềm và trí tuệ nhân tạo.

Bài tập luyện tập

• CSES – Chessboard and Queens (xếp 8 quân hậu)
• CSES – Grid Paths (quay lui với cắt nhánh rất mạnh)
• LeetCode 37 – Sudoku Solver

Thử thách: hãy thêm bộ đếm vào code Python và thử với một đề Sudoku "siêu khó" bạn tìm được trên mạng. Chương trình cần bao nhiêu lần gọi đệ quy? Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 11: Chơi Wordle tối ưu bằng lý thuyết thông tin: entropy và thuật toán tìm kiếm

Đọc tiếp: Wordle & entropy →

← Bài trước: xếp lịch thi & tô màu đồ thịXem tất cả 27 bài →

Nguồn tham khảo

• Indiana Public Media – Hoosier Puzzlemaster (Howard Garns)
• NBC News (2021) – Sudoku maker Maki Kaji
• Cornell University – Counting Sudokus
• Donald Knuth (2000) – Dancing Links
• Yato & Seta (2003) – Complexity and Completeness of Finding Another Solution
• McGuire, Tugemann, Civario (2012) – There is no 16-Clue Sudoku