Prolog: Học theo ví dụ

Question

Tôi đang cố gắng tìm hiểu một chút về swi-prolog (ngoài các chương trình cơ bản, vô dụng).

Bất cứ ai có thể giải thích (có lẽ trong mã giả) trình giải sudoku này và các chức năng liên quan đang làm gì? Nếu bạn cần tham chiếu nhiều hơn, nó được tìm thấy trong gói CLP (FD) của swi-prolog.

Cảm ơn!

:- use_module(library(clpfd)). 
sudoku(Rows) :-             
     length(Rows, 9), maplist(length_(9), Rows),     
     append(Rows, Vs), Vs ins 1..9,        
     maplist(all_distinct, Rows),        
     transpose(Rows, Columns), maplist(all_distinct, Columns), 
     Rows = [A,B,C,D,E,F,G,H,I],         
     blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).   


length_(L, Ls) :- length(Ls, L).         

blocks([], [], []).             
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
     all_distinct([A,B,C,D,E,F,G,H,I]),       
     blocks(Bs1, Bs2, Bs3).          


problem(1, [[_,_,_,_,_,_,_,_,_],         
      [_,_,_,_,_,3,_,8,5],         
      [_,_,1,_,2,_,_,_,_],         
      [_,_,_,5,_,7,_,_,_],         
      [_,_,4,_,_,_,1,_,_],         
      [_,9,_,_,_,_,_,_,_],         
      [5,_,_,_,_,_,_,7,3],         
      [_,_,2,_,1,_,_,_,_],         
      [_,_,_,_,4,_,_,_,9]]). 

Answer 1

sudoku/1 về cơ bản mô tả các ràng buộc mà giải pháp Sudoku phải đáp ứng, nơi bảng được trình bày dưới dạng danh sách chín danh sách dài 9. vấn đề/2 gán một bảng đã được khởi tạo một phần cho một số vấn đề. Để sử dụng nó, bạn nên làm

? - vấn đề (1, Board), sudoku (Board).

Bạn nên đọc các vị từ được sử dụng trong the documentation.

Answer 2

Prolog là cách suy nghĩ khác về chương trình: bạn phải suy nghĩ một cách hợp lý.

Trước hết là A :- B, C, D có nghĩa là A là đúng (succeds) nếu B VÀ C VÀ D là đúng.

Đoạn mã bạn được đăng kiểm tra về tính xác thực của một câu đố Sudoku, có ba điều kiện:

• yếu tố đều khác nhau bằng hàng
• yếu tố đều khác nhau bằng cách cột
• yếu tố này là tất cả khác nhau theo khối 3x3

Làm thế nào nó hoạt động?

sudoku (Rows) là đúng nếu:

1. length(Rows, 9) -> có 9 yếu tố trong hàng
2. maplist(_length(9), Rows) ->maplist kiểm tra vị (tham số đầu tiên) trên mọi phần tử của danh sách (tham số thứ hai). Điều này có nghĩa là mỗi hàng phải có chiều dài 9.
3. maplist(all_distinct, Rows) -> giống như trước, nhưng chúng tôi kiểm tra xem mỗi hàng có các phần tử riêng biệt (không phải bằng cặp đôi) hay không.
4. transpose(Rows, Columns), maplist(all_distinct, Columns) -> chúng tôi transpose các hàng vào cột để kiểm tra xem họ là tất cả riêng biệt cũng bằng cách chọn chúng theo cách dọc
5. Rows = [A,B,C,D,E,F,G,H,I] -> chia tách danh sách hàng và đặt mỗi một trong một biến Một khác nhau, B, C, D ... vì vậy A sẽ là hàng đầu tiên, B giây thứ hai và như vậy trên
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> vị từ này phải đúng cho ba hàng.

Hãy nói về phần blocks, điều đó khá buồn cười. Chúng tôi muốn kiểm tra xem mọi khối 3x3 có chứa các giá trị riêng biệt hay không. Làm thế nào chúng ta có thể làm điều đó?

Giả sử có 3 hàng, điều kiện phải đúng cho ba phần tử đầu tiên của mỗi hàng (khối 3x3 đầu tiên), cho các phần tử từ 4 đến 6 (khối thứ hai) và thứ 7-thứ 9 (khối thứ ba).

Vì vậy, chúng tôi có thể suy nghĩ đệ quy: blocks([],[],[]) là không đáng kể, chúng tôi có danh sách trống.

Trường hợp blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) được chọn khi bạn gọi blocks biến vị ngữ với các tham số có danh sách với AT LEAST 3 yếu tố. Vì vậy, chúng ta có thể kiểm tra xem A, B, C, D, E, F, G, H, tôi là tất cả khác biệt, sau đó chúng tôi gọi blocks đệ quy sử dụng làm tham số danh sách còn lại (không có ba yếu tố đầu tiên). Đây là những gì Prolog là về!

Vì vậy, blocks sẽ được gọi đầu tiên với ba hàng gồm 9 phần tử, nó sẽ kiểm tra 3 đầu tiên của mỗi hàng riêng biệt và gọi chính nó với 3 danh sách gồm 6 phần tử, kiểm tra lại và gọi chính nó với 3 danh sách gồm 3 phần tử , hãy kiểm tra lại và tự gọi chính nó bằng ba danh sách trống (trường hợp trival luôn khởi động).

Answer 3

về "append (Rows, Vs), Vs ins 1..9"

http://www.swi-prolog.org/pldoc/man?predicate=append%2F2

Nó có nghĩa là tất cả các yếu tố của danh sách liệt kê phải nằm trong miền 1..9.