Trang chủ » Blog » Thuật toán » [Mỗi ngày 1 thuật toán] Bài toán Sudoku

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

bởi ngoctran2 | 10:46 | Blog | Thuật toán

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ạ

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

3. Mã nguồn C++

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

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

4. Mã nguồn Java

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

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

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

5. Mã nguồn Python

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

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!

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

8 + 15 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM