Tìm hiểu thuật toán Backtracking và ứng dụng giải Sudoku

 Mình để ý là trên blog mình viết khá nhiều thuật toán về AI, viết cả về máy học. Và như các bạn cũng thấy, những thuật toán này giải được những bài toán khá phức tạp, và do đó những thuật toán này cũng phức tạp không kém :)). Nhưng đã bao giờ bạn nghĩ chúng ta có thể giải những bài toán phức tạp bằng sức mạnh lưu trữ và tốc độ tính toán của máy tính chưa? Chúng ta sẽ không phải cất công suy nghĩ quá nhiều về thuật toán nữa. Máy tính sẽ lo hết cho chúng ta. ( Viết tới đây thì mình cũng thấy nó na ná như là máy học thật ^^)
 Hôm nay mình sẽ giới thiệu các bạn 1 thuật toán có tên là Backtracking, một thuật toán siêu đơn giản nhưng sức mạnh của nó thì vô cùng lớn.
Các ứng dụng mình viết trong bài này đều đã được host lên ở đây, các bạn có thể vào xem nhé.

Backtracking là gì?

Backtracking algorithm là kĩ thuật sử dụng các tổ hợp phép thử để giải quyết 1 vấn đề tính toán nào đó

Để dễ hiểu, ta đi vào ví dụ về mở khóa mã pin chẳng hạn. Ta có 1 mã pin có 4 chữ số từ 0-9. Để giải được mã pin này, thì có 1 cách đơn giản đó là phải thử nghiệm từng khả năng để xem có đúng không.

Đầu tiên ta có thể điền vào ô đầu là số 0.

Tiếp tục điền vào các ô tiếp theo.

Giả sử mã pin 0000 là mã pin sai. Vậy bước tiếp theo của backtracking là gì? Câu trả lời là thuật toán này sẽ thử khả năng tiếp theo của ô cuối cùng. Và ta sẽ có mã pin tiếp theo như sau

Và nếu mã pin 0001 cũng là mã pin sai. Chúng ta sẽ từ từ tăng giá trị hàng đơn vị lên 1 đơn vị. Ta sẽ có các mã pin từ 0002 đến 0009.
Vấn đề là các mã pin trên đều sai. Lúc này, backtracking sẽ quay lại ô trước hàng đơn vị. Đây cũng là lí do thuật toán này mang tên backtracking ( truy vết). Ta sẽ có mã pin được nhập như sau.

Lúc này, quá trình thử nghiệm lại tiếp tục với số hàng đơn vị, ta sẽ có các mã pin từ 0010 đến 0019. Và nếu những mã pin này sai, thì backtracking lại tiếp tục để cho ra các số 0020 đến 0029.
Cứ như thế, quá trình chạy sẽ kiểm thử các mã pin từ 0000 đến 9999. Và tất nhiên, khi mã pin đúng thì thuật toán sẽ kết thúc.

Ứng dụng giải sudoku bằng backtracking

Tương tự như việc giải mã pin, backtracking sẽ được chúng ta áp dụng để giải ma trận sudoku.

Chúng ta sẽ áp dụng kiểm thử từng khả năng của mỗi ô. Quá trình này sẽ kết thúc khi ta đạt được ma trận đúng của sudoku.

solve(maze){
        let currentCell = maze.getNextUnsolveCell();
        //already solved maze
        if(currentCell===undefined) {
            return true;
        }
        let availableValues = maze.getAvailableValues(currentCell);
        for(let value of availableValues){
            maze.setValueForCell(currentCell,value);
            if(this.solve(maze)){
                return true;
            }
        }
        maze.setValueForCell(currentCell,0);

        return false;
    }

Đoạn code trên chính là backtracking trong việc giải sudoku. Quá trình backtracking sẽ được thực hiện trong lập trình bởi đệ quy.
Các bước của thuật toán có thể được viết lại như sau:
Bước 1 : lấy ô chưa được giải tiếp theo để thử nghiệm
Bước 2: nếu không có ô nào để giải nữa thì ma trận đã giải xong
Bước 3: tìm những giá trị mà ô hiện tại có thể tồn tại. ( Thực ra bước này không cần thiết, bạn có thể cho các giá trị ứng thử từ 1 đến 9 cũng được. Mình thêm phần này  vào để tăng tốc độ tính toán lên thôi.)
Bước 4: với mỗi giá trị có thể ứng thử, ta ứng thử nó vào ô hiện tại.
Bước 5: thực hiện đệ quy lại từ Bước 1.
Bước 6: nếu đã thử hết tất cả giá trị ứng thử rồi mà không được thì reset lại ô hiện tại về 0
Các bạn để ý, thuật toán của chúng ta chẳng có gì là phức tạp cả. Nhưng nó đã giải quyết được 1 bài toán rất phức tạp là giải sudoku. Cái cốt lõi đằng sau việc này là chúng ta đã lợi dụng khả năng lưu trữ và tốc độ xử lý của máy tính để truy vết các phép thử.

Mình đã viết 1 ứng dụng để giải sudoku bằng javascript ( đoạn code demo ở trên đã thay đổi sau khi mình cập nhật hiệu ứng animation cho ứng dụng). Code các bạn có thể clone về ở github của mình.
Cám ơn các bạn đã ghé thăm và đọc bài trên blog của mình ^^