Trình giải Sudoku one-liner của Arthur Whitney (2011)

Thuật toán giải bài toán Sudoku

• Mô tả bài toán Sudoku

  • Câu đố Sudoku gồm các ô 3×3 tạo thành một lưới 3×3, mỗi ô либо để trống hoặc chứa một số từ 1 đến 9.
  • Mỗi khối 3×3, 9 hàng và 9 cột phải chứa đủ 9 chữ số mà không bị trùng lặp.
  • Có cung cấp ví dụ bài toán và cách giải.

• Tổng quan thuật toán

  • Xử lý ma trận như một vector và biểu diễn hàng, cột, vùng Sudoku bằng các vector chỉ mục.
  • Thực hiện kiểm tra cơ bản cho câu đố và lọc các phần tử có thể để tìm lời giải.
  • Nếu ô đang trống thì chuyển sang danh sách tiếp theo; nếu ô chứa nhiều số khả dĩ thì chọn từ nhóm hẹp nhất để thêm vào danh sách.
  • Khi mọi ô đều chỉ chứa một chữ số thì đã tìm được lời giải.

• Ghi chú kỹ thuật

  • Đây là lời giải do Veli-Matti Jantunen cung cấp, có thể dùng ⍺ để biểu diễn hình chữ nhật Sudoku.
  • Kết quả trả về một vector của mọi lời giải, là ⍬ nếu không có, và '' nếu có lỗi.
  • Thuật toán đơn giản: xử lý ma trận như một vector và lọc các phần tử có thể để tìm lời giải.

• Các cách tiếp cận khác

  • Có cung cấp cách mã hóa thay thế của David Crossley và Arthur Whitney.
  • Mô tả nhiều phong cách lập trình và cách tiếp cận khác nhau.

• Ví dụ và ứng dụng

  • Có cung cấp nhiều ví dụ khác nhau để giải bài toán Sudoku.
  • Cũng có một hàm để tách các khối bên trong nhằm giúp bài toán Sudoku dễ đọc hơn.

Tóm tắt của GN⁺

• Giới thiệu nhiều thuật toán và phong cách lập trình khác nhau để giải bài toán Sudoku.
• Câu đố Sudoku hữu ích trong việc nâng cao tư duy logic và khả năng giải quyết vấn đề.
• Nhiều cách tiếp cận giúp tăng tính linh hoạt khi giải quyết bài toán.
• Những câu đố có chức năng tương tự Sudoku như Kakuro, KenKen cũng được khuyến nghị.

[GN⁺]

Ý kiến trên Hacker News

• K là ngôn ngữ do Arthur Whitney tạo ra dựa trên APL và Scheme, nhấn mạnh vào tốc độ, khả năng xử lý mảng và cú pháp giàu tính biểu đạt
• Khi đo độ phức tạp của mã, người ta so sánh số dòng mã và mức độ nén
  • Mã APL tạo cảm giác như dữ liệu nhị phân đã được nén, và thật ấn tượng với những người có thể hiểu được nó
• Số dòng mã không phải là thước đo tốt vì được sử dụng khác nhau tùy ngôn ngữ
  • Cách đo tốt hơn là xem xét số lượng nút trong cây cú pháp, độ sâu và các yếu tố phân nhánh
• Tính rõ ràng của bài toán là điều quan trọng, và các ngôn ngữ kiểu Iversonian (bao gồm J và K) khác biệt với các ngôn ngữ khác
  • Lời giải một dòng rất đáng kinh ngạc, và hữu ích cho việc mô tả cũng như thực thi mảng một cách hiệu quả
• Có ý kiến cho rằng chương trình K nên kết thúc bằng QED, và thắc mắc liệu điều đó có liên quan đến KQED hay không
  • KQED là đối tác PBS ở vùng Bay Area
• Có người thắc mắc liệu các ngôn ngữ như APL/k có giúp suy nghĩ về bài toán hiệu quả hơn không
• Việc học APL và các ngôn ngữ mảng có giúp ích cho các ngôn ngữ khác, nhưng rồi không còn dùng hằng ngày nữa
  • APL khó giải quyết vấn đề nếu không biết cách tiếp cận cụ thể cho dạng bài đó
• Có những lời giải tốt hơn các lời giải kém hiệu quả từng thấy trong một số sách hướng dẫn thiết kế thuật toán
  • Năm 2015 đã có một bài đăng blog viết về điều này
• Lời giải Sudoku dùng Scryer Prolog dễ đọc và mạnh mẽ, với khả năng giải ràng buộc rất xuất sắc
  • Scryer Prolog là một Prolog hiện đại, hiệu năng cao và tuân thủ ISO rất tốt