[Mỗi ngày 1 thuật toán] Bài toán Sudoku

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Sudoku. Để giải bài toán này, CodeGym sẽ cung cấp cho bạn ba đoạn mã nguồn quan trọng, bao gồm: C++, Java, và Python. 

1. Ý tưởng chính của bài toán

Sudoku là một trò chơi đố số dựa trên việc điền các số từ 1 đến 9 vào một bảng vuông 9×9, chia thành 9 ô vuông con 3×3, sao cho mỗi hàng, mỗi cột và mỗi ô vuông con chỉ chứa một số từ 1 đến 9 duy nhất.

Thuật toán giải Sudoku thường sử dụng kỹ thuật quay lui (backtracking) để tìm kiếm tất cả các khả năng điền số vào các ô trống.

• Khởi tạo: Bắt đầu từ ô trống đầu tiên.
• Thử điền số: Thử điền lần lượt các số từ 1 đến 9 vào ô đó.
• Kiểm tra hợp lệ: Kiểm tra xem số vừa điền có vi phạm quy tắc của Sudoku hay không (tức là có xuất hiện trong hàng, cột hoặc ô vuông con tương ứng hay không).
• Đệ quy: Nếu số vừa điền hợp lệ, gọi đệ quy để điền số cho ô tiếp theo.
• Quay lui: Nếu không tìm thấy số nào hợp lệ cho ô hiện tại, quay lại ô trước đó và thử điền số khác.

2. Ví dụ minh hoạ

3. Mã nguồn C++

4. Mã nguồn Java

5. Mã nguồn Python

6. Giải thích

• Hàm isSafe: Kiểm tra xem việc điền số num vào ô tại hàng row và cột col có hợp lệ hay không.
• Hàm solveSudoku:
  • Tìm ô trống đầu tiên.
  • Thử điền lần lượt các số từ 1 đến 9 vào ô đó.
  • Nếu số hợp lệ, gọi đệ quy để giải tiếp.
  • Nếu không tìm thấy số nào hợp lệ, quay lui và thử số khác.

7. Lưu ý

• Hiệu suất: Thuật toán này có thể rất chậm đối với các bàn cờ khó. Có thể sử dụng các kỹ thuật tối ưu hóa như heuristic để cải thiện hiệu suất.
• Nhiều giải pháp: Một số bàn cờ Sudoku có nhiều hơn một lời giải.
• Bàn cờ không có lời giải: Nếu không tìm thấy lời giải nào, có nghĩa là bàn cờ đã cho không hợp lệ.

Xem thêm các bài viết thú vị về Thuật toán tại đây!