Giới thiệu dự án

Trò chơi trí tuệ Sudoku từ khi xuất hiện trên thế giới (khởi nguồn từ tạp chí Dell năm 1979 với tên "Number Place", sau đó lan rộng toàn cầu từ năm 2004) đã trở thành một chuẩn mực kinh điển để đánh giá tư duy logic và các giải thuật tìm kiếm trong Khoa học Máy tính. Theo các khảo sát từ cộng đồng nghiên cứu Trí tuệ Nhân tạo (AI) và Tối ưu hóa tổ hợp, không gian trạng thái của một bảng Sudoku $9 \times 9$ chưa điền có thể lên đến $9^{81} \approx 1.96 \times 10^{77}$ cấu hình, và với một đề bài tiêu chuẩn có sẵn 20–30 ô gợi ý, số lượng trạng thái cần duyệt vẫn xấp xỉ $9^{50} \sim 10^{47}$.

+---+---+---+---+---+---+---+---+---+
| . | . | 5 | 3 | . | . | . | . | . |  --> Không gian tìm kiếm: 9^(ô trống)
| 8 | . | . | . | . | . | . | 2 | . |  --> Cực đại: ~10^47 trạng thái
| . | 7 | . | . | 1 | . | 5 | . | . |  --> Yêu cầu: Khử đệ quy & Lan truyền ràng buộc
+---+---+---+---+---+---+---+---+---+

1. Vấn đề thực tế (Problem Statement)

Mặc dù Sudoku có luật chơi đơn giản (điền các số từ 1 đến 9 sao cho mỗi hàng, mỗi cột và mỗi khối $3 \times 3$ chứa đủ các chữ số không trùng lặp), việc giải tự động bằng máy tính đối mặt với nhiều thách thức kỹ thuật cốt lõi:

  • Bùng nổ tổ hợp (Combinatorial Explosion): Các thuật toán vét cạn thông thường (Brute-force) rơi vào tình trạng quá tải tính toán do không gian nhánh tìm kiếm quá lớn.
  • Hiện tượng tràn ngăn xếp (Stack Overflow) khi đệ quy: Giải thuật quay lui đệ quy thuần túy (Naive Recursive Backtracking) tạo hàng nghìn frame trên bộ nhớ Stack khi duyệt sâu, làm giảm hiệu năng thực thi và tiêu tốn tài nguyên bộ nhớ cục bộ.
  • Bài toán đa nghiệm và vô nghiệm: Các phần mềm đơn giản thường chỉ dừng lại ở việc tìm một nghiệm đầu tiên, không thể định lượng được tổng số nghiệm khả dĩ (Multiple Solutions) hoặc phát hiện sớm các đề bài mâu thuẫn (Unsolvable Puzzles).

2. Mục tiêu dự án

Đề tài "Nghiên cứu phương pháp quay lui và ứng dụng giải bài toán Sudoku" do tác giả Phạm Thị Thanh Hiền thực hiện tại Trường Đại học Sư phạm – Đại học Đà Nẵng tập trung vào 4 mục tiêu cụ thể:

  1. Nghiên cứu bản chất lý thuyết của kỹ thuật quay lui (Backtracking) và các phương pháp tối ưu hóa không gian trạng thái.
  2. Xây dựng mô hình dữ liệu đa chiều hiệu quả (agree[,,], row[,], column[,], area[,]) để kiểm soát ràng buộc ô nhanh với độ phức tạp $O(1)$.
  3. Thiết kế giải thuật quay lui cải tiến kết hợp khử đệ quy (Non-recursive Backtracking) và tiền xử lý lan truyền ràng buộc (Constraint Propagation / preSolve).
  4. Phát triển ứng dụng Desktop hoàn chỉnh trên nền tảng .NET/C# hỗ trợ giải đa chế độ (tìm nghiệm đầu, nghiệm thứ $k$, đếm tổng số nghiệm đến 10.000) và xuất bản đề thi đa định dạng (RTF, HTML).

3. Phương pháp giải quyết và Phạm vi

  • Phương pháp tiếp cận: Kết hợp giữa tiền xử lý phân tích logic (Naked Singles/Hidden Singles) nhằm loại bỏ sớm các phương án bất khả thi trước khi kích hoạt bộ duyệt quay lui dạng vòng lặp lùi tiến (add = 1 / add = -1).
  • Kết quả kỳ vọng: Thời gian giải trung bình dưới 5ms cho mỗi câu đố Sudoku $9 \times 9$, tỷ lệ chính xác $100%$, xử lý linh hoạt từ 1 nghiệm đến hàng nghìn nghiệm.
  • Phạm vi & Giới hạn: Trọng tâm áp dụng trên bàn cờ chuẩn $9 \times 9$ (81 ô, 9 vùng). Đề tài chưa mở rộng chuyên sâu cho các biến thể khổng lồ như Giant Sudoku ($25 \times 25$) hay Monster Sudoku ($100 \times 100$).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Tiêu chí so sánh Vét cạn thuần túy (Brute-force) Quay lui đệ quy chuẩn (Standard Backtracking) Giải pháp đề tài (Backtracking khử đệ quy + preSolve)
Cơ chế duyệt Duyệt tất cả các tổ hợp có thể Duyệt theo chiều sâu (DFS) qua hàm đệ quy Vòng lặp chỉ số (index, add) không đệ quy
Kiểm soát bộ nhớ Tốn kém bộ nhớ lưu trữ nhánh Nguy cơ tràn Stack khi độ sâu $\ge 60$ Bộ nhớ cố định, không tạo biến cục bộ mới
Tiền xử lý ràng buộc Không có Rất hạn chế (chỉ kiểm tra tại bước thử) Khử nhánh sớm bằng preSolve() (checkrow, checkcollum, checkarea)
Thời gian giải trung bình Vô cùng lớn ($> 10^{15}\text{ s}$) 50ms – 500ms tùy mức độ khó $\approx 2\text{ms} - 10\text{ms}$
Khả năng đếm đa nghiệm Kém Trung bình (chậm khi số nghiệm lớn) Xuất sắc (xử lý lên tới 10.000 nghiệm)

Phân loại yêu cầu hệ thống theo mô hình MoSCoW

  • Must have (Bắt buộc có): Nhập/xuất bàn cờ 81 ô; kiểm tra tính hợp lệ của dữ liệu đầu vào; giải tìm nghiệm đầu tiên với thuật toán quay lui tối ưu; thông báo đề bài vô nghiệm.
  • Should have (Nên có): Chế độ đếm tổng số nghiệm (ResultCount); giải đến đáp án thứ $k$ (SolveTo); bước tiền xử lý preSolve loại bỏ ô đơn giá trị.
  • Could have (Có thể có): Chức năng xuất bản đề và đáp án ra file RTF (Microsoft Word) và HTML; bộ phím tắt điều hướng nhanh trên lưới 81 ô; thống kê thời gian giải chi tiết.
  • Won't have (Chưa thực hiện đợt này): Nhận diện bàn cờ Sudoku qua camera/ảnh chụp (OCR); giải các biến thể Sudoku kích thước $16 \times 16$ hoặc $25 \times 25$.

Thiết kế hệ thống

+-------------------------------------------------------------+
|               Giao diện người dùng (Windows Forms)          |
|    - Lưới nhập liệu 81 ô (Shortcut keys)                    |
|    - Thanh công cụ (Tập tin, Sudoku, Trợ giúp)              |
|    - Khối xuất bản (RTF, HTML)                              |
+-------------------------------------------------------------+
                              |
                              v
+-------------------------------------------------------------+
|                     Lớp nghiệp vụ: SDK                      |
|  + inputData(): Khởi tạo ma trận & Kiểm tra mâu thuẫn      |
|  + preSolve(): Tiền xử lý & Cắt tỉa nhánh logic            |
|  + Solve(count): Động cơ quay lui không đệ quy              |
|  + SolveFirst() / SolveTo() / ResultCount()                 |
+-------------------------------------------------------------+
                              |
                              v
+-------------------------------------------------------------+
|                     Cấu trúc dữ liệu lõi                    |
|  - agree[10,10,11]: Danh sách ứng viên khả dĩ               |
|  - row[10,10], column[10,10], area[10,10]: Mảng bit mặt nạ|
|  - AREA[10,10]: Bản đồ ánh xạ tọa độ vùng 3x3               |
|  - value[10,10]: Trạng thái giá trị hiện hành               |
+-------------------------------------------------------------+

Cấu trúc dữ liệu và Công thức ánh xạ tọa độ

Hệ thống sử dụng các mảng tĩnh đa chiều tối ưu bộ nhớ cache CPU:

  • row[10,10], column[10,10], area[10,10]: Mảng nhị phân đánh dấu trạng thái khả dụng của chữ số $j$ tại hàng/cột/vùng $i$ ($1$ là khả dụng, $0$ là đã bị chiếm).
  • agree[10,10,11]: agree[i,j,0] lưu số lượng giá trị có thể điền vào ô $(i,j)$; agree[i,j,1..k] lưu danh sách các giá trị hợp lệ cụ thể.
  • AREA[10,10]: Bảng ánh xạ tọa độ hàng $i$, cột $j$ sang chỉ số vùng $1..9$.

Chuyển đổi linh hoạt giữa biểu diễn 1 chiều ($1..81$) và 2 chiều ($[1..9, 1..9]$):

// Chuyển từ chỉ số 1D (x) sang chỉ số hàng (i) và cột (j)
int tox(int x) { return (x - 1) / 9 + 1; }
int toj(int x) { return (x - 1) % 9 + 1; }

// Chuyển từ chỉ số 2D [i, j] sang chỉ số 1D
int tou(int i, int j) { return (i - 1) * 9 + j; }

Phương pháp luận (Methodology)

Quy trình phát triển được triển khai theo mô hình V-Model cải tiến, kết hợp chặt chẽ giữa phân tích thuật toán lý thuyết và đo kiểm thực nghiệm qua từng mốc tiến độ:

  • Giai đoạn 1 (Tuần 1–3): Nghiên cứu lý thuyết không gian trạng thái, phân tích độ phức tạp thuật toán quay lui và đệ quy.
  • Giai đoạn 2 (Tuần 4–6): Thiết kế cấu trúc dữ liệu mảng phẳng và xây dựng các hàm ánh xạ tọa độ, viết hàm kiểm tra ràng buộc hàng/cột/vùng.
  • Giai đoạn 3 (Tuần 7–10): Cài đặt giải thuật tiền xử lý preSolve() và động cơ quay lui khử đệ quy Solve(int count).
  • Giai đoạn 4 (Tuần 11–13): Phát triển giao diện GUI Windows Forms, tích hợp cơ chế phím tắt, chức năng thống kê và xuất báo cáo RTF/HTML.
  • Giai đoạn 5 (Tuần 14–15): Kiểm thử hộp trắng (White-box testing), đánh giá hiệu năng với các bộ dữ liệu Sudoku từ dễ đến cực khó (Hardest Sudoku puzzles).

Implementation và kết quả

Quá trình phát triển và Thuật toán then chốt

1. Thuật toán Tiền xử lý & Cắt tỉa nhánh (preSolve)

Trước khi bắt đầu quay lui, hàm preSolve liên tục quét hàng (checkrow), cột (checkcollum) và vùng (checkarea) để tìm các ô duy nhất có thể nhận một giá trị (Single Candidate). Quá trình này được lặp cho đến khi không còn ô nào thỏa mãn:

void preSolve() {
    int k;
    while (top != 0) {
        checkrow();
        checkcollum();
        checkarea();
        k = pop();
        effectFromANumber(tox(k), toj(k));
        if (!HaveResult) return;
    }
}

Hàm kiểm tra hàng và đặt giá trị tự động khi chỉ có 1 ô nhận giá trị:

void checkrow() {
    int i, j, value, o = 0, count = 0;
    for (i = 1; i <= size; i++) {
        for (value = 1; value <= 9; value++) {
            if (row[i, value] == 0) continue;
            for (count = 0, j = 1; j <= size; j++) {
                if (exit(i, j, value)) {
                    o = j;
                    count++;
                }
            }
            if (count == 0) {
                HaveResult = false;
                return;
            }
            if (count == 1) {
                setValue(i, o, value);
                push(tou(i, o));
            }
        }
    }
}

2. Thuật toán Quay lui Khử đệ quy trung tâm (Solve)

Động cơ chính loại bỏ hoàn toàn đệ quy bằng cách sử dụng hai biến điều khiển: index (chỉ số ô từ 1 đến 81) và add ($+1$ là duyệt tiến, $-1$ là quay lui). Cơ chế này quản lý quá trình duyệt cây tìm kiếm một cách hoàn hảo:

int Solve(int count) {
    int ResultCount = 0;
    do {
        index += add;
        if (index == size * size + 1) {
            ResultCount++;
            add = -1;
            if (count == -1) { // Chế độ đếm tất cả số nghiệm
                if (ResultCount > MaxIndexResultCanFind) return -1;
                continue;
            } else {
                if (ResultCount >= count) { // Tìm thấy nghiệm chỉ định
                    for (int ii = 1; ii <= 9; ii++)
                        for (int jj = 1; jj <= 9; jj++)
                            Result[tou(ii, jj)] = agree[ii, jj, value[ii, jj]];
                    return 1;
                }
            }
            continue;
        }

        i = tox(index);
        j = toj(index);

        if (agree[i, j, 0] == 1) {
            value[i, j] = 1;
            continue;
        }

        if (value[i, j] != 0) {
            row[i, agree[i, j, value[i, j]]] = 1;
            collum[j, agree[i, j, value[i, j]]] = 1;
            area[AREA[i, j], agree[i, j, value[i, j]]] = 1;
        }

        if ((add < 0) && (value[i, j] == agree[i, j, 0])) {
            value[i, j] = 0;
            continue;
        }

        for (value[i, j]++; value[i, j] <= agree[i, j, 0]; value[i, j]++) {
            if ((row[i, agree[i, j, value[i, j]]] != 0) &&
                (collum[j, agree[i, j, value[i, j]]] != 0) &&
                (area[AREA[i, j], agree[i, j, value[i, j]]] != 0)) {
                
                // Thiết lập ràng buộc mới
                row[i, agree[i, j, value[i, j]]] = 0;
                collum[j, agree[i, j, value[i, j]]] = 0;
                area[AREA[i, j], agree[i, j, value[i, j]]] = 0;
                add = 1;
                break;
            }
        }

        if (value[i, j] > agree[i, j, 0]) {
            value[i, j] = 0;
            add = -1; // Quay lui
        }
    } while (index + add > 0);

    return (count == -1) ? ResultCount : 0;
}

Đánh giá hiệu năng và Kiểm thử

Chương trình được thử nghiệm trên môi trường máy tính tiêu chuẩn chạy Windows OS với nhiều cấp độ đề bài khác nhau:

Thời gian xử lý trung bình theo cấu hình đề bài:
+------------------------+-------------------+-----------------+
| Loại đề bài            | Số ô gợi ý sẵn    | Thời gian xử lý |
+------------------------+-------------------+-----------------+
| Đơn giản (Easy)        | 36 - 45 ô         | 1 - 2 ms        |
| Trung bình (Medium)    | 30 - 35 ô         | 2 - 4 ms        |
| Cực khó (Hard/Evil)    | 22 - 28 ô         | 3 - 8 ms        |
| Vô nghiệm (Conflict)   | Sai ràng buộc     | < 1 ms (tức thì)|
| Đa nghiệm (> 500 n'm)  | 17 - 20 ô         | 15 - 45 ms      |
+------------------------+-------------------+-----------------+
  • Độ bao phủ kiểm thử (Test Coverage): Đạt $100%$ đối với các ca kiểm thử biên (bàn cờ trống, bàn cờ mâu thuẫn 2 số cùng hàng, bàn cờ có duy nhất 1 nghiệm và bàn cờ có nhiều nghiệm).
  • Phản hồi người dùng: Giao diện trực quan, bảng điều hướng 10 tổ hợp phím tắt (Tab, Shift+Tab, Arrow keys, PageUp/Down, Home/End) giúp tăng tốc độ nhập đề bài lên $300%$ so với thao tác chuột truyền thống.

Đổi mới và đóng góp

  1. Khử hoàn toàn đệ quy bằng cơ chế trạng thái hai chiều: Thay vì dựa vào cơ chế đệ quy tự nhiên của trình biên dịch gây tốn bộ nhớ Stack frame, thuật toán sử dụng bước nhảy trạng thái index += add kết hợp với mảng agree[,,] được tối ưu sẵn. Cải tiến này giúp tiết kiệm bộ nhớ lên đến $70%$ và loại bỏ triệt để rủi ro tràn bộ nhớ.
  2. Kỹ thuật thu hẹp không gian tìm kiếm (preSolve Constraint Propagation): Bằng cách áp dụng quy tắc quét đơn độc vị trí trước khi gọi hàm tìm kiếm, chương trình cắt giảm trung bình $85% - 95%$ số lần quay lui so với thuật toán Backtracking cơ bản.
  3. Thuật toán đa chức năng thống nhất: Một hàm Solve(int count) duy nhất có khả năng phục vụ linh hoạt 3 kịch bản:
    • count = 0: Tìm nghiệm đầu tiên cực nhanh.
    • count > 0: Dừng chính xác tại nghiệm thứ $k$.
    • count = -1: Đếm toàn bộ số lượng nghiệm (giới hạn bảo vệ 10.000 nghiệm tránh lặp vô tận).
  4. Đóng góp học thuật: Đồ án là tài liệu tham khảo thực tế cho sinh viên ngành CNTT về kỹ thuật khử đệ quy trong các bài toán tối ưu tổ hợp NP-Complete.

Ứng dụng thực tế và triển khai

Kịch bản sử dụng thực tế (Use Cases)

  • Công cụ giải và kiểm định chất lượng tòa soạn: Ứng dụng cho các nhà xuất bản báo, tạp chí (như Hoa Học Trò, Thanh Niên) tự động kiểm tra xem một đề Sudoku tự tạo có đảm bảo duy nhất 1 nghiệm (Unique Solution) hay không trước khi in ấn.
  • Hệ thống tạo đề và học tập trực tuyến: Sử dụng lõi giải thuật preSolve và Solve làm Backend cho các game Sudoku di động, hỗ trợ tính năng gợi ý thông minh (Hint system) từng bước theo tư duy logic của con người.
  • Công cụ xuất bản đề thi tự động: Hỗ trợ xuất dữ liệu ra file .rtf và .html có sẵn định dạng bảng biểu đẹp mắt, sẵn sàng in ấn không cần căn chỉnh thủ công.
[Bàn cờ Sudoku (GUI / File)] 
            |
            v
   [Lõi giải thuật C#] ---> [Thống kê số nghiệm & ms]
            |
            v
   [Mô-đun Xuất bản] -----> Xuất file RTF (Microsoft Word)
                     -----> Xuất file HTML (Trình duyệt Web)

Yêu cầu triển khai hệ thống

  • Hệ điều hành: Microsoft Windows 7 / 8 / 10 / 11 hoặc Windows Server.
  • Môi trường thực thi: .NET Framework 2.0 / 3.5 / 4.x trở lên.
  • Phần cứng tối thiểu: CPU Pentium 4 1.5GHz, 512MB RAM, dung lượng đĩa trống 20MB.

Hạn chế và hướng phát triển

  • Hạn chế kỹ thuật hiện tại:
    • Thuật toán preSolve mới chỉ tích hợp mức độ suy luận cơ bản (Single Candidate). Các kỹ thuật nâng cao như X-Wing, Swordfish, Naked Pairs chưa được mô đun hóa riêng biệt để đưa ra lời giải thích giải thuật từng bước cho người chơi.
    • Giao diện được xây dựng trên Windows Forms truyền thống, chưa tích hợp giao diện hiện đại WPF hoặc nền tảng Web đa thiết bị.
  • Hướng phát triển tương lai:
    • Nâng cấp thuật toán sang cấu trúc Dancing Links (DLX) của Donald Knuth (thuật toán X) để tăng tốc độ giải cho các ma trận cực lớn kích thước $16 \times 16$ hoặc $25 \times 25$.
    • Tích hợp mạng nơ-ron tích chập (CNN) để quét và nhận dạng đề bài Sudoku trực tiếp từ hình ảnh camera trên ứng dụng di động.

Đối tượng hưởng lợi

  • Sinh viên ngành CNTT & Khoa học Máy tính: Nắm vững phương pháp chuyển đổi giải thuật đệ quy sang vòng lặp không đệ quy, kỹ thuật quản lý mảng đa chiều tối ưu bộ nhớ.
  • Lập trình viên phần mềm: Tiếp cận mẫu thiết kế giải bài toán thỏa mãn ràng buộc (CSP - Constraint Satisfaction Problem) ứng dụng trong bài toán xếp lịch (Timetabling), định tuyến giao vận.
  • Nhà phát triển game & Tòa soạn: Sở hữu bộ công cụ kiểm thử đề bài Sudoku tự động với tốc độ tính bằng miligiây, đảm bảo tính chuẩn xác tuyệt đối của câu đố.

Câu hỏi thường gặp

1. Ứng dụng yêu cầu cấu hình phần cứng và phần mềm như thế nào để vận hành?

Hệ thống được viết bằng C# trên nền tảng .NET Framework tiêu chuẩn, do đó chỉ yêu cầu hệ điều hành Windows có cài đặt .NET Framework 2.0 trở lên, chiếm dụng RAM dưới 20MB và hoạt động mượt mà trên mọi máy tính văn phòng.

2. Sự khác biệt giữa đệ quy và khử đệ quy trong bài toán này là gì?

Giải thuật đệ quy gọi lại chính hàm thông qua ngăn xếp hệ thống (Call Stack), dễ dẫn đến tràn bộ nhớ khi gặp đề bài có độ sâu nhánh lớn. Giải pháp khử đệ quy sử dụng biến chạy index và hướng di chuyển add kết hợp mảng lưu trạng thái, giúp kiểm soát bộ nhớ cố định và tăng tốc độ xử lý do không tốn chi phí gọi hàm (Function Call Overhead).

3. Chương trình xử lý như thế nào khi gặp đề bài Sudoku có nhiều hơn một đáp án?

Hàm Solve(-1) kích hoạt chế độ duyệt toàn bộ không gian nghiệm và ghi nhận biến đếm ResultCount. Người dùng có thể xem đáp án đầu tiên, đáp án tiếp theo (Đáp án sau), đáp án trước đó (Đáp án trước) hoặc chuyển thẳng đến nghiệm thứ $k$ thông qua hàm SolveTo(k).

4. Tại sao thời gian giải có thể đạt mức 2ms đối với hầu hết các đề bài?

Tốc độ vượt trội đạt được nhờ giai đoạn tiền xử lý preSolve(). Bằng cách phân tích các ràng buộc duy nhất trên hàng, cột và khối $3 \times 3$, hệ thống đã tự động điền đúng phần lớn các ô trống trước khi kích hoạt thuật toán quay lui, làm giảm độ sâu của cây tìm kiếm đi hàng chục lần.

5. Dự án có thể mở rộng để giải các bàn cờ kích thước $16 \times 16$ hay không?

Hoàn toàn có thể mở rộng. Cấu trúc ánh xạ tọa độ tox, toj, tou và mảng ràng buộc có thể cấu hình lại kích thước tham số size = 16. Tuy nhiên, với kích thước lớn, nên kết hợp thêm cấu trúc Dancing Links (DLX) để tối ưu hóa việc tìm kiếm ma trận thưa.

Kết luận

Đề tài "Nghiên cứu phương pháp quay lui và ứng dụng giải bài toán Sudoku" của tác giả Phạm Thị Thanh Hiền đã giải quyết trọn vẹn bài toán tối ưu tổ hợp kinh điển bằng cách kết hợp nhuần nhuyễn giữa cơ sở lý thuyết khoa học máy tính và kỹ thuật lập trình ứng dụng. Việc loại bỏ thành công cấu trúc đệ quy, kết hợp cơ chế lan truyền ràng buộc đa chiều (agree[,,]) đã mang lại bước nhảy vọt về hiệu năng giải Sudoku với thời gian thực thi chỉ $\approx 2\text{ms}$. Ứng dụng không chỉ chứng minh tính đúng đắn trên phương diện học thuật mà còn mang giá trị thực tiễn cao trong giáo dục tư duy thuật toán và tự động hóa xuất bản trò chơi trí tuệ.