Đồ Án Cấu trúc dữ liệu và giải thuật : Sudoku

Giới thiệu về thuật toán
Thuật toán quay lui
Thuật toán quay lui là một thuật toán điển hình để giải các bài toán ứng dụng trong tin học. Bằng việc liệt kê các tình huống, thử các khả năng có thể cho đến khi tìm thấy một lời giải đúng, thuật toán quay lui chia nhỏ bài toán, lời giải của bài toán lớn sẻ là kết quả của việc tìm kiếm theo chiều sâu của tập hợp các bài toán phần tử. Trong suốt quá trình tìm kiếm nếu gặp phải một hướng nào đó mà biết chắc không thể tìm thấy đáp án thì quay lại bước trước đó và tìm hướng khác kế tiếp hướng vừa tìm kiếm đó. Trong trường hợp không còn một hướng nào khác nửa thì thuật toán kết thúc.
Khác với thuật toán tham lam (cũng là điểm mạnh), thuật toán quay lui có điểm khác là nó không cần phải duyệt hết tất cả các khả năng, nhờ đó tránh được các khả năng không đúng nên có thể giảm được thời gian giải.
Thuật toán quay lui thường được cài đặt theo lối đệ quy, mỗi lần gọi hàm đệ quy, hàm đệ quy được truyền một tham số (trong các tham số) là chỉ số của bài toán con, trong hàm sẻ cố gắng tìm lời giải cho bài toán con đó, nếu tìm thấy thì gọi hàm đệ quy để giải bài toán con tiếp theo hoặc là đưa ra đáp án bài toán lớn nếu đã đầy đủ lời giải, nếu không tìm thấy thì chương trình sẻ trở về điểm gọi hàm đó. Mục đích của việc sử dụng hàm đệ quy là để thuật toán được rỏ ràng, dễ viết, dễ hiểu hơn và cũng để bảo toàn các biến, các trạng thái lúc giải bài toán con.
Thuật toán quay lui có thể được thể hiện theo sơ đồ cây tìm kiếm theo chiều sâu như bên. Từ hình vẽ, ta dễ dàng nhận thấy rằng :
- Ở 1 bài toán hiện tại (mỗi nốt), ta đi tìm lời giải cho bài toán đó. Ứng với lời giải, ta đi giải bài toán kế tiếp cho đến lúc bài toán trở gốc nên đầy đủ.
- Lời giải của bài toán gốc thường là một lối đi từ gốc đến nốt cuối cùng (không có nốt con)