sudoku của Dyalog APL trả về tất cả các ma trận lời giải có thể có từ ma trận câu đố trong đó ô trống được đặt là 0, đồng thời triển khai cùng một bài toán theo nhiều cách theo phong cách APL/K- Đối tượng mặc định là Sudoku 9×9, trong đó mỗi khối 3×3, hàng và cột phải chứa các số từ 1 đến 9 không lặp lại
- Đầu vào
prob chứa 1-9 ở các ô đã điền và 0 ở ô trống; có thể chỉ định cả khối không vuông như 2×3, 3×4 bằng đối số trái tùy chọn shape
- Thuật toán giải của Veli-Matti Jantunen vector hóa ma trận, tạo chỉ mục hàng/cột/khối, rồi giảm dần các ứng viên và mở rộng từ nhóm bị ràng buộc mạnh nhất
- Các ví dụ
s33 và s22 mỗi ví dụ có 3 lời giải, 3 4 sudoku s34 có 2 lời giải; bài viết cũng giới thiệu one-liner K 5 của Arthur Whitney cùng nhiều bản tái triển khai bằng APL
Đầu vào Sudoku và kết quả của hàm sudoku
- Câu đố Sudoku là một lưới gồm các khối 3×3 được bố trí thành 3×3, và mỗi ô hoặc để trống hoặc có một số từ 1 đến 9
- Lời giải phải thỏa mãn cả ba điều kiện không trùng lặp
- Mỗi khối 3×3 chứa các số từ 1 đến 9 không lặp lại
- Mỗi hàng 9 ô chứa các số từ 1 đến 9 không lặp lại
- Mỗi cột 9 ô chứa các số từ 1 đến 9 không lặp lại
- Ma trận
prob dùng các số 1-9 cho ô đã điền và 0 cho ô trống
- Đối số trái tùy chọn
shape chỉ định hình dạng khối của câu đố không phải dạng vuông mặc định
- Với ma trận 6×6 có vùng con là 2×3, gọi theo dạng
2 3 sudoku mat
- Kết quả là một vector chứa tất cả các ma trận lời giải
- Nếu không có lời giải, trả về
⍬
- Tình huống lỗi có thể được biểu thị bằng
''; tài liệu ghi là “không nên xảy ra, nhưng khi số kết quả cực kỳ lớn”
Luồng giải của Veli-Matti Jantunen
- Thuật toán xử lý ma trận Sudoku như một vector, và biểu diễn hàng, cột, vùng Sudoku lần lượt bằng vector chỉ mục
- Sau khi vượt qua các kiểm tra cơ bản, thuật toán kiểm tra từng phương án trong danh sách ứng viên
- Ở mỗi bước, thuật toán lọc các phần tử có thể có của mọi ô
- Nếu có dù chỉ một ô không có giá trị khả dĩ nào, ứng viên lời giải đó bị loại
- Nếu một ô có từ hai số ứng viên trở lên, thuật toán chọn ô trong nhóm bị ràng buộc mạnh nhất và thêm các tổ hợp ứng viên của ô đó vào danh sách
- Nếu mỗi ô chỉ còn lại đúng một số, nó được xử lý như một lời giải rồi chuyển sang ứng viên tiếp theo
- Cùng phần này cũng bao gồm hàm
Shuffle, dùng để xáo một bảng Sudoku hiện có thành một bảng khác
One-liner của Arthur Whitney và các triển khai thay thế
- Triển khai
sudoku thay thế của David Crossley nhận cấu hình N×N làm đầu vào, dành cho trường hợp kích thước khối N*÷2 là số nguyên
- Đầu vào phải là một bố cục hợp lệ, trong đó một số ô có các số từ 1 đến
N và các ô còn lại là 0
- Mỗi hàng, cột và khối phải chứa tất cả các số từ 1 đến
N trong kết quả
- Bên trong triển khai có các hàm phụ trợ như
valid, search, rules, sole, singles, uniques, matches, NinN, setup
- Lời giải K 5 của Arthur Whitney được trình bày dưới dạng một dòng mã
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
- Phil Last cung cấp triển khai
sudoku chuyển mã của Whitney sang D-function
- Bản viết lại của Morten Kromberg định nghĩa tường minh một số thành phần của K, có hình thức gần với bản gốc hơn
- Giống phiên bản K, nó nhận và trả về vector 81 phần tử thay vì ma trận
- Triển khai
Sudoku của Roger Hui có dạng tổng quát hơn, xử lý được cả câu đố không vuông
svec tạo vector lời giải, còn pvex và pvec triển khai các bố cục khả dĩavl tạo danh sách các số khả dĩ, còn emt tìm chỉ mục hàng/cột của các ô trốngrcb, box, cmap, CMAP cấu thành quan hệ xung đột giữa hàng/cột/khối
Câu đố ví dụ và số lượng lời giải
s33 là bài mẫu 9×9, và kết quả của sudoku s33 có 3 lời giải- Hàm
sbox chia các khối bên trong để hiển thị lưới Sudoku dễ đọc hơn
- 0 được hiển thị bằng dấu chấm (
·)
- Được xuất ra dưới dạng ma trận ký tự có vẽ ranh giới khối
s22 là bài mẫu 4×4, và kết quả của sbox¨ sudoku s22 có 3 lời giảis34 là bài mẫu dùng khối 3×4
- Hiển thị bài toán theo dạng phân tách khối bằng
3 4 sbox s34
- Kết quả của
3 4 sudoku s34 có 2 lời giải
Liên kết tham khảo và mục nên xem cùng
1 bình luận
Các ý kiến trên Hacker News
Dòng đó được viết bằng K. K là ngôn ngữ do Arthur Whitney tạo ra dựa trên APL và Scheme
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*xThỉnh thoảng tôi ước lượng độ phức tạp của mã bằng cách so sánh số dòng mã với kết quả đầu ra bên dưới
tar -cf - . | gzip | base64 | wc -lNói cách khác là xem “nó nén tốt đến mức nào?”. Nhìn APL làm tôi nhớ đến lúc lỡ gửi đầu ra gzip ra terminal
p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵Thật ấn tượng khi có người còn lần theo loại mã này và hỏi “có tìm được bug không?”. Nó có cảm giác như dữ liệu nhị phân đã nén mà mọi người đều đã có cùng một cuốn từ điển
∘không có toán hạng bên phải; cònn n←⍴⍵trông như một tín hiệu rằng nó đặtnhai lần và kỳ vọng⍵là hai chiều, nhưng tùy ý định thì_ n←⍴⍵hoặcn←⊃⌽⍴⍵sẽ tự nhiên hơnNgoài ra
⊥sẽ lỗi nếu⍴⍵không phải một số nguyên đơn lẻ hoặc vector rỗng, nên rốt cuộc chẳng khác gìn←⍴⍵và chỉ khiến khó hiểu hơn. Nhiều dấu,trùng lặp và↑⍵cũng có thể loại bỏ, và toàn bộ biểu thức thực ra gần như trở thànhp←(n+1)⍴⊂⍳n×n←⍴⍵, tức là một cấu trúc trả ran+1vector1..n²Nhìn bề ngoài thì kỳ lạ, nhưng nếu học các ký hiệu và phép toán cơ bản, APL lại thẳng thắn đến bất ngờ. Chỉ là để thành thạo thì cần thời gian, và khi đạt đến điểm đó nó có cảm giác như siêu năng lực
Nói rằng những người ủng hộ ngôn ngữ này nhấn mạnh tốc độ, khả năng xử lý mảng dễ dàng và cú pháp giàu sức biểu đạt là đúng
https://en.m.wikipedia.org/wiki/K_(programming_language)
Số dòng mã là một chỉ số không tốt vì mỗi ngôn ngữ có cách dùng dòng khác nhau
Một thước đo tốt hơn có thể là đếm số nút trong cây cú pháp theo các ký hiệu không kết thúc có ý nghĩa như “hằng số” hay “lời gọi hàm”. Xa hơn nữa, nếu tính cả độ sâu và hệ số phân nhánh của cây đó thì càng tốt
Lời giải một dòng chiếm rất ít không gian màn hình, nên là lợi thế lớn khi xử lý vấn đề phức tạp. Việc di chuyển mắt trong màn hình nhẹ nhàng hơn nhiều so với cuộn qua lại giữa các file, và tải nhận thức là điều quan trọng
Ngay cả khi không biết K, việc các hằng số hiện ra cạnh nhau trông như đang dùng biểu diễn dữ liệu trực tiếp của bài toán. Nếu văn hóa K khuyến khích loại mã như vậy và kéo tư duy về phía trực tiếp, đơn giản, tôi sẽ muốn đưa loại nước sốt đặc chế đó vào nhóm
https://cliffle.com/esoterica/hq9plus/
https://en.wikipedia.org/wiki/Algorithmic_information_theory
Tôi thường tự hỏi liệu khi dùng các ngôn ngữ như APL/K, lập trình viên có thật sự có thể suy nghĩ về vấn đề hiệu quả hơn không
avg a+bNếu là ngôn ngữ không lấy mảng làm trung tâm, rất có thể sẽ cần kiểm tra biên, một vòng lặp
forlớn, các biến tạm để chứa tổng và số lượng, v.v. Một việc trong ngôn ngữ như C mất khoảng 6 dòng thì trong Q kết thúc bằng 6 ký tựTuy vậy mọi ngôn ngữ đều có tính năng giúp suy luận tốt hơn về một số vấn đề nhất định. Các ngôn ngữ hàm có kiểu dữ liệu đại số và pattern matching, chẳng hạn OCaml hay F#, tốt hơn một
switchhoặcif-else-iflớn; còn ngôn ngữ có cú pháp đường nhưasync/awaitthì có lợi cho xử lý đồng thờiKhi làm quant, tôi dùng kdb+/q rất nhiều trong hơn 5 năm cho các chiến lược tần suất trung bình, nhưng khi chuyển sang giao dịch tần suất cao, nơi các phép tính sổ lệnh không dễ hoặc không hiệu quả để vector hóa, việc tiếp tục dùng ngôn ngữ lấy mảng làm trung tâm lại khiến việc suy luận về vấn đề phức tạp hơn
https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
Phần đó nằm trong ngữ cảnh trình biên dịch, nhưng toàn bộ bài nói xem Dyalog và APL như một hệ ký pháp toán học. Mạch chính là việc tối ưu hóa biểu thức toán học có thể dễ hơn tối ưu hóa mã thông thường
Một trong những điểm quan trọng nhất ở đây là bộ sinh bài toán ở phía trên rất rõ ràng. Đây chính là khác biệt giữa các ngôn ngữ ký hiệu kiểu Iverson, bao gồm J và K, với các ngôn ngữ khác
Nó không có sự tao nhã và sức mạnh của lời giải một dòng, nhưng rất gọn gàng và dễ hiểu ngay cả khi không có chú thích nghiêm ngặt. Tuy vậy, tôi nghĩ
lampkhông phải là một ký hiệu chú thích hayLời giải một dòng thật đáng kinh ngạc, và lập trình ngầm định hay đến mức làm xoắn cả não. Ý tưởng dùng khả năng nén độc đáo của các ngôn ngữ dựa trên glyph để mô tả và thực hiện lập trình hàm, rồi lại áp dụng nó cho toàn bộ mảng, đúng là thiên tài
https://www.jsoftware.com/papers/fork.htm
Tất nhiên, nếu loại bỏ khả năng đó thì có thể buộc người ta viết mã dài dòng hơn, nhưng như thế sẽ làm giảm đáng kể thế mạnh của nó với tư cách một công cụ tương tác. Các ngôn ngữ kiểu Iverson hữu ích cho công việc tương tác vì có thể viết mã rất ngắn. Khi đó mã thậm chí còn không được lưu lại, nên đúng nghĩa là mã write-only
Khi viết mã để đưa vào file, bạn có thể chọn phong cách mình muốn, và khi đó tôi khuyên nên viết ít nén hơn. Dù vậy, ngay cả khi viết theo phong cách dài dòng, các ngôn ngữ kiểu Iverson vẫn cho mã ngắn hơn nhiều so với hầu hết ngôn ngữ khác
Phần lớn mọi người ngại vì các ký hiệu, nhưng vấn đề của tôi không phải vậy
Tôi thích APL và các ngôn ngữ mảng, và những gì học được đã giúp ích rất nhiều cả khi dùng các ngôn ngữ khác. Nhưng chúng không trở thành công cụ hằng ngày của tôi; không phải vì ký hiệu, mà vì sau khoảng 3–4 năm thỉnh thoảng động đến, tôi đã đụng phải một bức tường không vượt qua được
Ở các ngôn ngữ khác thường có một cách tiếp cận chung để ít nhất cũng giải quyết vấn đề một cách tạm ổn, rồi sau này nếu tìm ra “bí quyết” của vấn đề đó thì có thể sửa lại cho tao nhã và hiệu quả hơn. APL thì cảm giác như không có lối vòng tạm thời như vậy: hoặc bạn biết bí quyết, hoặc không biết
Tôi không rõ thực tế có đúng như vậy không, hay nếu học đủ nhiều bí quyết thì trực giác giải quyết vấn đề sẽ hình thành, hay rốt cuộc vẫn chỉ toàn là bí quyết, hoặc đơn giản là tôi chưa đọc tài liệu chiến lược cốt lõi nào đó
⍸⍣¯1là được mà?”, trong khi rất có thể chưa từng có ai nói với bạn rằng⍸có phép toán nghịch đảo và cách dùng nóĐến nay tôi đã dùng những ngôn ngữ này nhiều năm, nhưng những bức tường mã mà một số lập trình viên mảng tạo ra vẫn hơi gây ngợp. Tôi hiểu vì sao họ viết như vậy, nhưng cá nhân tôi thích mã có một chút khoảng trắng hơn
Tôi đang làm một ngôn ngữ mảng dựa trên APL, và một trong các mục tiêu ban đầu là biến phong cách mệnh lệnh thành công dân hạng nhất mà không trừng phạt người mới dùng những thứ như câu lệnh
if. Tôi xem phong cách này nằm khoảng giữa kiểu APL thuần túy và các ngôn ngữ mệnh lệnh thông thườnghttps://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
Nhưng đó cũng không phải giới hạn của bản thân ngôn ngữ. Theo kinh nghiệm của tôi, quá trình xuyên qua bức tường đó chính là lúc mô hình tư duy bắt đầu khớp vào nhau. Chỉ sau khi dành khoảng 500 giờ hack một nguyên mẫu parser YAML trong một năm, các mảnh ghép mới bắt đầu ăn khớp
Cốt lõi có vẻ là sự kết hợp giữa các nguyên tắc thiết kế hướng dữ liệu, cách tận dụng cụ thể các đặc tính kiểu Iverson của ký pháp tốt trong kiến trúc phần mềm, và việc làm quen với các idiom cùng cách chúng biểu đạt khái niệm miền
https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
https://www.jsoftware.com/papers/tot.htm
Có một video về chủ đề này
https://www.youtube.com/watch?v=DmT80OseAGs
Bạn có thể tự thử lời giải tại https://tryapl.org/
Có thể sẽ thú vị nếu so sánh một dòng này với các lời giải code golf trong nhiều ngôn ngữ lập trình
https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes
https://codegolf.stackexchange.com/a/5030