C#: Giải trò chơi Sudoku bằng thuật toán quay lui

Sudoku là một loại trò chơi lôgic và cách chơi là điền số từ 1 đến 9 vào những ô trống sao cho mỗi cột dọc, mỗi hàng ngang, mỗi phân vùng nhỏ (ô 3x3) có đủ các số từ 1 đến 9 mà không được lặp lại. Bảng câu đố hình vuông, mỗi chiều có 9 ô nhỏ, hợp thành 9 cột, 9 hàng và được chia thành 9 ô lớn 3x3.
Giả sử có bàn cờ ban đầu như bên dưới:



Một bàn cờ Sudoku

Đáp án cho bàn cờ này như sau:



Sử dụng giải thuật quay lui để giải bài toán này, ta có đoạn mã giả như sau:

function backtrack(position){     if (isEndOfGrid == true){ // Empty cells filled. Solution found. Abort         return true;     }     foreach (x from 1 ... 9){         grid[position] = x;         if (gridIsValid == true){ // Check for collisions             if (backtrack(nextPosition) == true){ // Move to next empty cell                 return true; // Empty cells filled. Solution found. Abort.             }         }     }     grid[position] = NULL; // Empties cell     return false; //Solution not found. Backtrack. }

Thuật toán quay lui thực hiện các bước như sau:



Chương trình Demo Giải trò chơi Sudoku bằng thuật toán quay lui do Vương Huỳnh Long viết: