Báo Cáo Đề tài Tìm hiểu ngôn ngữ Prolog và bài toán Puzzle

MỤC LỤC

Phần 1 Giới thiệu Visual prolog 3
1.1 Đặc điểm chung của ngôn ngữ prolog 4
1.2 Cấu trúc của chương trình Visual prolog 13
1.3 Các thành phần trong chương trình Visual prolog 15

Phần 2 Kết nối Visual prolog với C# 28
2.1 Tạo ra file .dll trong chương trình Visual prolog 29
2.2 Kết nối với C# 33

Phần 3 Bài toán ta-canh 36
3.1 Giới thiệu thuật toán A* 37
3.2 Giải bài toán ta canh bằng thuật toán A* 38
3.3 Giải thuật A* của bài toán ta canh viết bằng Visual prolog 39
3.4 Mở rộng bài toán N-puzzle 39
3.5 Giới thiệu về chương trình trò chơi ta canh 42

Phần 4 Tài liệu tham khảo 48









Phần 1: GIỚI THIỆU VISUAL PROLOG

Visual prolog là ngôn ngữ lập trình logic được PDC phát triển dưạ trên nền tảng của Prolog và TurboProlog. Tên gọi Prolog được xuất phát từ cụm từ tiếng Pháp Programmation en logique, nghĩa là "lập trình theo logic". Xuất hiện từ năm 1972 (do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Visual prolog là để hổ trợ lập trình công nghiệp, nhấn mạnh đến những vấn đề phức tạp của tri thức. Ngày nay Visual prolog rất mạnh và là ngôn ngữ lập trình logic rất tốt, kết hợp các tính năng của logic, chức năng (function) và lập trình theo mô hình hướng đối tượng. Đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên vì đây là mục tiêu thiết kế ban đầu của nó. Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm mà ở đó, thay vì phải mô tả cách giải quyết một bài toán trên máy tính, con người chỉ cần mô tả bài toán và máy tính sẽ hỗ trợ họ nốt phần còn lại.

Các tính năng của Visual prolog
· Khái niệm lập trình logic (backtracking ,pattern matching)
· Hỗ trợ unicode
· Quản lý bộ nhớ tự động
· Tính đa hình
·



Visual prolog là môi trường lập trình hoàn hảo với:
· Graphical Integrated Development Environment (IDE)
· Compiler
· Linker
· Debugger

Với Visual prolog bạn có thể xây dựng các ứng dụng trên nền tảng Microsoft Windows 32. Nó cũng hổ trợ client-server và three-tier solutions(các giải pháp 3 tầng).

1.1. Đặc điểm chung của ngôn ngữ prolog
- Prolog không phân biệt giữa khái niệm Data và Program như trong Pascal.
- Sức mạnh của Prolog là đệ qui.
- Toàn bộ chương trình được xem như một cơ sở tri thức (knowledgebase).
- Chương trình Prolog là một tập hợp các luật (rules).
- Prolog là ngôn ngữ được thiết kế chủ yếu cho các suy luận, không coi trọng tính toán.
- Kowalski nói Algorithm = logic+control.
- Logic là phát biểu về cái gì bài toán phải giải quyết.
- Control phát biểu về làm thế nào bài toán được giải quyết.
- Người lập trình luận lý chỉ phải thực hiện phần logic còn phần control hệ thống sẽ đảm nhiệm.



1.1.1. Đặc điểm của biến
- Biến và hằng : Prolog qui định biến có ký tự bắt đầu là ký tự in (upppercase) hoặc ký tự gạch dưới (underscore). Hằng có ký tự bắt đầu là ký tự thường (lowercase).
Thí dụ:
Minh, X, Người, _minh, _x, _người là 6 biến.
minh, x, người, là 3 hằng.
- Biến trong mỗi clauses phải xuất hiện ít nhất 2 lần.
- Nếu biến chỉ xuất hiện một lần trong clauses thì phải thay nó bằng biến rỗng (anonymous). Ngoài ra một thông số nào của vị từ trong clauses mà ta không quan tâm cũng có thể thay nó bằng biến rỗng.
- Biến rỗng được biểu diễn bằng ký hiệu gạch dưới _ (underscore).
Thí dụ:
clauses
danăng(X) :- biết(X, Y), chơi(X, Z).
Biến Y và Z chỉ xuất hiện 1 lần nên phải đổi thành biến rỗng. Do đó :
clauses
danăng(X) :- biết(X, _ ), chơi(X, _ ).
- Các trạng thái của biến là : tự do (free), bị trói (bound), được cởi (unbound). Các trạng thái này do hệ thống thực hiện. Người lập trình không có bất kỳ tác động nào lên biến để thay đổi trạng thái. Do đó Prolog không có hành động gán (assignment) giá trị cho biến như trong ngôn ngữ Pascal.




1.1.2. Kiểu danh sách
- Đây là một loại tập hợp có bản chất đệ qui. Do đó những thao tác trên danh sách cần khai thác tính đệ qui triệt để.
- Danh sách là một loại tập hợp có phần tử là chuỗi các phần tử của một tập hợp trong miền Domains.
- Kiểu danh sách của Prolog được định nghĩa bằng cách thêm ký tự * vào tên kiểu phần tử.
Thí dụ:
domains
họtên = symbol .
dsSV = họtên* .
dsSố = integer* .
dsTên = symbol* .
dsNghềnghiệp = string* .
dsSV là danh sách các phần tử mà mỗi phần tử có kiểu hotên.
dsSố là danh sách các phần tử mà mỗi phần tử là số nguyên.
- Dạng thức của một biến kiểu danh sách :
o Liệt kê : các phần tử của danh sách đặt cách nhau bằng dấu phẩy. Tất cả đặt ở giữa 2 dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1,2,3,4]
o Đệ qui : Danh sách được biểu diễn gồm 2 phần, phần Head gồm 1 phần tử đầu của biểu diễn liệt kê và phần Tail gồm những phần tử còn lại của biểu diễn liệt kê. Phần Tail được biểu diễn bằng một danh sách liệt kê khác. Head và Tail đặt cách nhau dấu sổ xuống. Head và Tail được đặt trong dấu móc vuông.
Thí dụ :
domains
dssố = integer*
Biến X có kiểu Dssố là một danh sách 4 số nguyên 1, 2, 3, 4, được viết như sau :
X = [1|[2,3,4]].
- Một số danh sách đặc biệt :
a. Danh sách trống [] có head và tail không được định nghĩa.
b. Danh sách [1,2,3,4] = [1|[2,3,4]] có head là 1, tail là [2,3,4].
c. Danh sách [1] = [1|[] ] có head là 1, tail là danh sách trống [].
d. Danh sách [[1,2,3], [2,3,4,5], [6]] = [[1,2,3]|[[2,3,4,5], [6]]] có head là [1,2,3] và tail là [[2,3,4,5],[6]].

1.1.3. Nguyên tắc trả lời GOAL của Prolog
- Tuần tự từ trên xuống : hệ thống sẽ trả lời cho subgoal đầu tiên, kế đến là subgoal thứ 2, thứ 3, cho đến subgoal cuối cùng.
- So trùng (matching) : để trả lời cho từng subgoal hệ thống dò subgoal tuần tự theo từng dòng trong clauses. Việc dò tìm sẽ dừng khi subgoal trùng với một dòng clause nào đó, nếu không trùng thì dò tiếp cho đến dòng cuối cùng của clauses.

1.1.4. Cơ chế hoạt động của Prolog
1.1.4.1. Đồng nhất (unification): Khi so trùng subgoal với các dòng của clauses hệ thống prolog áp dụng cơ chế đồng nhất.
- Nếu subgoal so trùng với một dòng của clauses là fact thì nó sẽ đồng nhất tên vị từ kế đến là danh sách thông số. Các thông số sẽ được đồng nhất theo dạng thức.
Thí dụ :
class predicates
chếtạo(symbol, symbol) .
clauses
chếtạo(minh, tênlửa). (1)
chếtạo(dũng, máytính). (2)
chếtạo(thư, xehơi). (3)
goal
chếtạo(thư, X).
Prolog sẽ trả lời bằng cách dò trên 3 mệnh đề của phần clauses.
o Với mệnh đề 1 chế tạo (minh, tênlửa) : tên vị từ phù hợp cùng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là minh. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 2 chế tạo (dũng, máytính) : tên vị từ phù hợp cũng là chế tạo, cùng có 2 thông số, nhưng thông số thứ 1 của goal là thư khác với thông số thứ 1 của mệnh đề 1 là dũng. Do đó mệnh đề này không phù hợp với goal. Việc so trùng tiếp tục.
o Với mệnh đề 3 chế tạo (thư, xehơi) : tên vị từ phù hợp cũng là chếtạo, cùng có 2 thông số, thống số thứ 1 giống nhau cùng là thư, thông số thứ 2 của goal là biến X chưa có giá trị nên đồng nhất với thông số thứ 2 là xe hơi. Vậy hệ thống sẽ trả lời X là xe hơi.
- Nếu subgoal so trùng với một dòng của clauses là rule thì nó đồng nhất tên, kế đó đồng nhất dạng thức thông số. Cuối cùng là kiểm tra các subgoal diên tả điều kiện có trong mệnh đề đó.
Thí dụ :
domains
dssố = integer*
class predicates
dub(dssố,dssố)
clauses
sub( [], _ ) :- subgoal, . (1)
sub( [_|[3|Y]], [] ) :- subgoal, . (2)
sub( X, [2|[3,4]] ) :- subgoal, . (3)
goal
sub([5], [Y|[3]] ).
Để thoả mãn goal, hệ thống sẽ tiến hành dò từ mệnh đề 1 đến mệnh đề 3.
o Với mệnh đề 1, ở thông số 1 có [] ≠ [5].
o Với mệnh đề 2, ở thông số 1 có _ = [5] nhưng [3|Y]] ≠ [],
o Với mệnh đề 3, ở thông số 1 có X = [5], ở thông số 2 có Y = 2 và [3,4] ≠ [3] (vì danh sách [3,4] có 2 phần tử còn danh sách [3] chỉ có 1 phần tử),
Hệ thống trả lời là không đáp ứng được goal này mặc dù chưa hề kiểm tra đến các subgoal.
- Nhận xét :
o Sự khác biệt giữa rule của Prolog và if then của Pascal.
o If Điềukiện then Kếtquả = lệnh điều kiện của Pascal.
o Kếtquả if Điềukiện = Rule của Prolog.
o Hệ thống Pascal khi thực hiện lệnh if-then sẽ kiểm tra điều kiện trước, nếu đúng mới thực hiện kết quả. Nhưng với rule của Prolog thì kết quả được kiểm tra trước. Việc kiểm tra được thực hiện gồm hai phần - dạng thức và giá trị. Khi dạng thức và giá trị phù hợp thì hệ thống mới kiểm tra điều kiện (các subgoal).
o Trong một số trường hợp trình tự thực hiện này của Prolog có tiện lợi, vì nếu hình thức kết quả không phù hợp thì không cần thiết kiểm tra điều kiện. Trong khi Pascal việc kiểm tra điều kiện và hình thức kết quả đươc gom chung vào trong điều kiện.

1.1.4.2. Thối lui (backtracking)
- Giả sử có mệnh đề P :- P1, P2, P3. Muốn mệnh đề P thỏa thì các subgoal P1, P2, P3 phải thỏa. Giả sử P1 thỏa nhưng còn 5 trường hợp chưa xét đến. Khi đó hệ thống sẽ kiểm tra xem P2 có thoả hay không. Nếu P2 không thỏa thì hệ thống sẽ thối lui lại để kiểm tra P1 với 5 trường hợp chưa xét. Việc này thực hiện được nhờ cơ chế thối lui của Prolog.
- Các trạng thái của biến
o Tự do (free) : Trước khi bị buộc thì biến được gọi là tự do.
o Bị trói (bound) : Khi biến được đồng nhất thì nó bị buộc giá trị được đồng nhất vào.
o Được cởi (unbind) : Khi backtracking tại vị từ nào thì biến trong thông số của vị từ đó được cởi bỏ giá trị đã mang trước đó ra, và từ lúc này nó được tự do và chờ để bị buộc giá trị mới vào.


Ví dụ :
class predicates
chơisymbol, symbol)
biếtsymbol, symbol)
danăngsymbol)
clauses
chơi(minh, piano). chơi(kính, violon)
chơi(tân, keyboard). chơi(trang, guitare)
biết(tân, vẽtranh). biết(kính, làmthơ)
biết(kính, điêukhắc). biết(kính, soạnnhạc)
đanăng(X) :- biết(X, _), chơi(X, _)
goal
đanăng(X).
+ Để goal thỏa thì 2 subgoal biết(X,_) và chơi(X,_) phải thỏa.
+ Subgoal biết(X, _ ) sẽ được duyệt trên clauses và sẽ lấy giá trị là biết(tân, vẽtranh) và còn 3 mệnh đề mà subgoal này chưa duyệt.
+ Kế đó subgoal chơi(tân, _ ) (biến X không còn tự do đã bị buộc vào giá trị tân) được duyệt nhưng không có mệnh đề nào để nó thỏa vì vậy nó thất bại. Hệ thống sẽ tự thối lui đồng thời biến X được cởi bỏ giá trị tân, nó trở lại trạng thái tự do và dò trở lại subgoal biết(X, _) với 3 mệnh đề còn lại. Như vậy sẽ lấy giá trị biết(kính, làmthơ). Subgoal chơi lại được dò trùng để lấy giá trị. Nó lấy được giá trị chơi(kính, violon). Khi đó goal đã được thỏa và biến X của vị từ đanăng lấy giá trị là kính.
o Chú ý : Biến trong Prolog chỉ có ý nghĩa trong mệnh đề chứa nó. Do đó nhiều mệnh đề khác nhau có thể có cùng tên biến.

1.2. Cấu trúc của chương trình Visual prolog
- Hệ thống visual prolog cung cấp sẵn một số miền tập hợp (Domains) để người lập trình sử dụng : integer, char, real, symbol, string, .
- Hệ thống Visual prolog cũng cung cấp cho người lập trình khả năng tạo ra các tập hợp mới phù hợp với bài toán cần giải.
- Gồm 4 phần: Domains, Predicates, Clauses, Goal.
o Domains là nơi để người lập trình định nghĩa những tập hợp mới (hoặc đặt tên lại).
o Predicates là phần khai báo các quan hệ giữa các domains.
o Clauses là phần định nghĩa các quan hệ đã khai báo trong phần predicates. Clauses gồm các rule. Rule được dùng để biểu diễn cho câu khai báo có dạng điều kiện - if nguyên_nhân then hậu_quả. Nếu rule không có nguyên nhân thì được gọi là sự kiện (fact). Do đó fact là hậu quả tất yếu xảy ra không không cần một nguyên nhân nào.
o Goal là phần đặt câu hỏi đối với hệ thống.

1.2.1. Domains
- Nơi tạo tập hợp mới có cùng kiểu với tập hợp có sẵn.
- Cách khai báo:
domains
<tendomains>=<loại miền>.
Thí dụ :
domains
songuyen=integer.
- Chú thích: Một số kiểu (tập hợp) cơ bản có sẵn:
o integer : kiểu số nguyên,
o real : kiểu số thực,
o char : kiểu ký tự,
o string : kiểu chuỗi, gồm chuỗi các ký tự có chiều dài “tuỳ ý” được đặt giữa hai dấu nháy.
o symbol : là kiểu gồm những ký hiệu, mỗi ký hiệu có chiều dài tối đa 255 ký tự, bắt đầu bằng ký tự thường.

1.2.2. Predicates
- Tạo quan hệ giữa các tập hợp.
- Cách khai báo:
class predicates
<tên predicate:mad:ds1,ds2, ,dsn) [pattern][flow pattern] .
pattern: procedure, multi, determ, nondeterm .
flowpatern: i,o,anyflow.
[​IMG]
Bảng: Pattern of Predicates
Thí dụ :
domains
songuyen=integer.
class predicates
giaithuasonguyen,songuyen) procedure anyflow.

1.2.3. Clauses
Gồm hai phần: sự kiện(fact) và luật (rule)
- Fact: là một quan hệ trên các tập hợp đã xác định (có sẵn hoặc đã được xác định trong Domains).
- Rule : gồm 2 phần head và body
o Cách khai báo một Rule là dùng kí hiệu :-
Thí dụ:
giaithua(N,1):-N<1,!. %Phần khai báo các rule
giaithua(N,N*F):-giaithua(N-1,F).
o Rule là quan hệ được định nghĩa từ nhiều quan hệ khác.
o Rule có dạng của câu điều kiện, nghĩa là gồm nguyên nhân và hậu quả (nguyên nhân → hậu quả). Tuy nhiên Rule là câu điều kiện được trình bày theo dạng thức : Hậu quả ← nguyên nhân.
- Do đó Fact có thể được xem là một loại rule đặc biệt - rule không có điều kiện.

Nhận xét :
- Một predicates được định nghĩa trong clauses bằng nhiều fact hoặc nhiều rule hoặc kết hợp vừa fact vừa rule.

1.2.4. Goal
- Goal là nơi đặt câu hỏi với hệ thống và hệ thống sẽ cho câu trả lời.
- Goal gồm một hay nhiều predicates cùng với thông số. Nếu goal gồm nhiều thành phần thì mỗi thành phần được gọi là subgoal.
- Chương trình thể hiện các phần khai bao trong Visual prolog

[​IMG]



1.3. Các gói thư viện cơ bản trong Visual Prolog
- Package list: chứa các predicates xử lý danh sách

[TABLE="width: 100%"]
[TR]
[TD="colspan: 2"]Predicate Summary[/TD]
[/TR]
[TR]
[TD]append : (Elem* Front, Elem* Tail) -> Elem* List.
List is the result of appending Tail to Front.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]append : (Elem* Front1, Elem* Front2, Elem* Tail) -> Elem* List.
List is the result of append(Front1, append(Front2, Tail)).[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]append : (Elem* Front1, Elem* Front2, Elem* Front3, Elem* Tail) -> Elem* List.
List is the result of append(Front1, append(Front2, append(Front3, Tail))).[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]append : (Elem* Front1, Elem* Front2, Elem* Front3, Elem* Front4, Elem* Tail) -> Elem* List.
List is the result of append(Front1, append(Front2, append(Front3, append(Front4, Tail)))).[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]appendList : (Elem** ListList) -> Elem* List.
List is the result of appending all the lists in ListList.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]classInfo : classInfo.
Class information predicate.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]difference : (Elem* List1, Elem* List2) -> Elem* List1ExceptList2.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]differenceBy : (comparator{Elem} Comparator, Elem* List1, Elem* List2) -> Elem* List1ExceptList2.
List1ExceptList2 contains the elements from List1 which are not in List2.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]drop : (positive Index, Elem* List) -> Elem* NewList.
Takes elements from list List, from the n'th element of index Index till the last one. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]filter : (Elem* List, filterPredicate{Elem} Filter) -> Elem* FilteredList.
Removes all items from List by Filter.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]forAll : (Elem* List, predicate{Elem} Predicate).
Invoke Predicate for all list elements[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]getMember_nd : (Elem* List) -> Elem Value nondeterm.
Returns the members Value of the list List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]intersection : (Elem* ListA, Elem* ListB) -> Elem* IntersectionAB.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]intersectionBy : (comparator{Elem} Comparator, Elem* ListA, Elem* ListB) -> Elem* IntersectionAB.
Returns intersection of ListA and ListB.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isMember : (Elem Value, Elem* List) determ.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isMemberBy : (comparator{Elem} Comparator, Elem Value, Elem* List) determ.
Succeds if Value is member of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]length : (Elem* List) -> positive Length.
Returns the length of the list List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]map : (Elem* List, function{Elem,OutElem} Function) -> OutElem* NewList.
Convert list to another list[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]maximum : (Elem* List) -> Elem Item.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]maximumBy : (comparator{Elem} Comparator, Elem* List) -> Elem Item.
Return maximum Item of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]minimum : (Elem* List) -> Elem Item.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]minimumBy : (comparator{Elem} Comparator, Elem* List) -> Elem Item.
Return minimum Item of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]nDuplicates : (Elem, positive N) -> Elem* NList.
Create list of N duplicates[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]nth : (positive Index, Elem* List) -> Elem Item.
Return Item of List at position Index. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]remove : (Elem* List, Elem Value) -> Elem* Rest.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]removeAll : (Elem* List, Elem Value) -> Elem* Rest.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]removeAllBy : (comparator{Elem} Comparator, Elem* List, Elem Value) -> Elem* Rest.
Remove the all occurences of Value from List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]removeBy : (comparator{Elem} Comparator, Elem* List, Elem Value) -> Elem* Rest.
Remove the first occurence of Value from List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]removeDuplicates : (Elem* List) -> Elem* Rest.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]removeDuplicatesBy : (comparator{Elem} Comparator, Elem* List) -> Elem* Rest.
Remove the all duplicates from List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]reverse : (Elem* List) -> Elem* Reverse.
Reverse is the reverse of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]setNth : (positive Index, Elem* List, Elem Item, Elem* NewList) procedure (i,i,i,o).
Returns the NewList with the Index'th element changed to Item. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]sort : (Elem* List) -> Elem* Sorted.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]sort : (Elem* List, sortOrder Order) -> Elem* Sorted.
Sorted is the sorted version of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]sortBy : (comparator{Elem} Comparator, Elem* List) -> Elem* Sorted.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]sortBy : (comparator{Elem} Comparator, Elem* List, sortOrder Order) -> Elem* Sorted.
Sorted is the sorted version of List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]split : (positive Index, Elem* List, Elem* LeftList, Elem* RightList) procedure (i,i,o,o).
Splits the list List in two lists in a place of element of index Index. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]take : (positive Index, Elem* List) -> Elem* NewList.
Takes elements from list List, from the first one till the n'th element of index Index-1. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryGetIndex : (Elem Item, Elem* List) -> positive Index determ.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryGetIndexBy : (comparator{Elem} Comparator, Elem Item, Elem* List) -> positive Index determ.
Get Index of Item in the List. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryGetNth : (positive Index, Elem* List) -> Elem Item determ.
Return Item of List by Index. Index is zero based.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryLastItem : (Elem* List) -> Elem LastItem determ.
Get the LastItem from the List.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]union : (Elem* ListA, Elem* ListB) -> Elem* UnionAB.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]unionBy : (comparator{Elem} Comparator, Elem* ListA, Elem* ListB) -> Elem* UnionAB.
Returns union of ListA and ListB.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]zip_nd : (A* AList, B* BList) -> tuple{A,B} nondeterm.
Returns the paired values tuple(A,B) from the lists AList and BList.[/TD]
[TD][/TD]
[/TR]
[/TABLE]

- Package stream: chứa các predicates quản lý việc xuất nhập
Ví dụ: class stdio trong package stream chứa các predicates sau

[TABLE="width: 100%"]
[TR]
[TD="colspan: 2"]Predicate Summary[/TD]
[/TR]
[TR]
[TD]nl : ().
Writes new line symbols to the current output stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]read : () -> _ Term.
Reads a specified term from the current input stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]readBytes : (byteCount Size) -> binary Binary.
Reads Size bytes from the input stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]readChar : () -> char Char.
Reads character from the current input stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]readLine : () -> string String.
Reads line from the current input stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]readString : (charCount NumberOfChars) -> string String.
Reads NumberOfChars characters from the input stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]save : (factDB FactsSectionName).
Save the contents of a named internal facts section in the current output stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]write : ( .) procedure ( .).
Writes arbitrary number variables to the current output stream.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]writef : (string Format [formatString], .) procedure (i, .).
Formatted output to the current output stream.[/TD]
[TD][/TD]
[/TR]
[/TABLE]

- Package string: chứa các predicates xử lý chuỗi.

[TABLE="width: 100%"]
[TR]
[TD="colspan: 2"]Predicate Summary[/TD]
[/TR]
[TR]
[TD]adjust : (string Src, charCount FieldSize, adjustSide Side) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjust : (string Src, charCount FieldSize, string Padding, adjustSide Side) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjust : (string Src, charCount FieldSize, string Padding, adjustBehaviour Behaviour, adjustSide Side) -> string AdjustedString.
Place a string in a field of FieldSize depending on the adjustSide and pads with the padding string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustLeft : (string Src, charCount FieldSize) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustLeft : (string Src, charCount FieldSize, string Padding) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustLeft : (string Src, charCount FieldSize, string Padding, adjustBehaviour Behaviour) -> string AdjustedString.
Place a string to the left in a field of FieldSize and pads with the padding string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustRight : (string Src, charCount FieldSize) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustRight : (string Src, charCount FieldSize, string Padding) -> string AdjustedString.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]adjustRight : (string Src, charCount FieldSize, string Padding, adjustBehaviour Behaviour) -> string AdjustedString.
Place a string to the left in a field of FieldSize and pads with the padding string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]arrayToList : (pointer ArrayOfStrings, unsigned Count) -> string* StringList.
Represents a converter between list of strings and C-style array of these strings.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]charLower : (char Char) -> char CharInLowerCase.
Converts char to lower case[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]charToString : (char Char) -> string CharAsString.
Creates new string with the character.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]charUpper : (char Char) -> char CharInUpperCase.
Converts char to upper case[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concat : (string First, string Second) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concat : (string First, string Second, string Third) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concat : (string First, string Second, string Third, string Fourth) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concat : (string First, string Second, string Third, string Fourth, string Fifth) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concat : (string First, string Second, string Third, string Fourth, string Fifth, string Sixth) -> string Output.
Concatenates two string[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concatList : (string* Source) -> string Output.
This predicate creates a string from the string list.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]concatWithDelimiter : (string* StringList, string Delimiter) -> string Output.
This predicate creates a string from the string list, inserting delimiter string between list elements.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]create : (charCount Length) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]create : (charCount Length, string Fill) -> string Output.
Create a new string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]createCopy : (string Source) -> string Output.
Creates a copy of Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]createFromCharList : (char* CharList) -> string String.
This predicate creates a string from the char list.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]equalIgnoreCase : (string First, string Second) determ.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]equalIgnoreCase : (string First, string Second, unsigned LanguageID) determ.
This predicate performs a case-insensitive strings comparison.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]format : (string FormatString [formatString], .) -> string Output.
Formats several arguments into a string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]front : (string Source, charCount Count, string First [out], string Last [out]).[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]frontChar : (string Source, char First [out], string Last [out]) determ.
Retrieves the first character of a string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]frontToken : (string Source, string Token [out], string Rest [out]) determ.
Returns the first token Token in Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]getCharFromValue : (unsigned16 Value) -> char Char.
This predicate returns a character from the numerical value.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]getCharValue : (char Char) -> unsigned16 Value.
This predicate returns numerical value for the character.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]hasAlpha : (string Source) determ.
Succeds if Source only contains alphabetic characters.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]hasDecimalDigits : (string Source) determ.
Succeds if Source only contains decimal digits.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]hasPrefix : (string Source, string Prefix, string Rest [out]) determ.
checks the prefix in the given string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]hasSuffix : (string Source, string Suffix, string Rest [out]) determ.
checks the suffix in the given string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isLowerCase : (string Source) determ.
Fails if Source contains uppercase letters[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isName : (string StringArg) determ.
Test whether a string represents a valid Prolog identifier name[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isUpperCase : (string Source) determ.
Fails if Source contains lowercase letters[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isValidToRead : (string StringPtr) determ.
Predicate is used for testing the access rights to a range of memory occupying by a string StringPtr.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isWhiteSpace : (char Source) determ.
Succeds if Source only contains white space characters (i.e. ' ', '\t', '\n').[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]isWhiteSpace : (string Source) determ.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]keywordString : (string Name, boolean Major) determ (i,o), (i,i) multi (o,o).
Succeeds if Name is prolog keyword. Major is the type of keyword.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]last : (string Source, charCount Count) -> string Last.
Return the last Count characters of Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]lastChar : (string Source, string First [out], char Last [out]) determ.
Retrieves the last character of a string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]length : (string Source) -> charCount Length.
Returns length Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]listToArray : (string* StringList, pointer ArrayOfStrings [out], unsigned Count [out]).
Represents a converter between list of strings and C-style array of these strings.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replace : (string Source, string ReplaceWhat, string ReplaceWith, caseSensitivity Case) -> string Output [deprecated("Use replaceFirst/4-> instead")].[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replaceAll : (string Source, string ReplaceWhat, string ReplaceWith) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replaceAll : (string Source, string ReplaceWhat, string ReplaceWith, caseSensitivity Case) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replaceAll : (string Source, string ReplaceWhat, string ReplaceWith, caseSensitivity Case, unsigned NumberOfReplacements [out]) -> string Output.
Replaces all occurences of ReplaceWhat with ReplaceWith.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replaceFirst : (string Source, string ReplaceWhat, string ReplaceWith, caseSensitivity Case) -> string Output.
Replaces a part of string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]replacePart : (string Source, charCount Position, charCount HowLong, string ReplaceWith) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]search : (string Source, string LookFor) -> charCount Position determ.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]search : (string Source, string LookFor, caseSensitivity Case) -> charCount Position determ.
Returns the position of the first occurrence of FookFor in Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]searchChar : (string String, char SearchingChar) -> charCount Position determ.
Locate the character SearchingChar in a string String[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]searchChar : (string String, char SearchingChar, caseSensitivity Case) -> charCount Position determ.
Locate the character SearchingChar in a string String[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]searchLast : (string Source, string LookFor, caseSensitivity Case) -> charCount Position determ.
Returns the position of last occurrence of LookFor.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]split : (string Input, string Separators) -> string* Splited.
Splits a string at the separators in the Separators string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]splitStringBySeparators : (string InputStr, string Separators, string HeadStr [out], char CurentSeparator [out], string RestStr [out]) determ.
Splits string by one of separator character[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]split_delimiter : (string Source, string Delimiter) -> string* List.
This predicate creates a list of strings from Source string contents.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]split_length : (string Source, charCount* Separator) -> string* List.
Creates a list of strings from contents of an existing one.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]subString : (string Source, charCount Position, charCount HowLong) -> string Output.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]subchar : (string String, charCount Position) -> char RetChar.
Returns the character RetChar at a given Position in the specified String.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]toCharList : (string Source) -> char* CharList.
Split a string into a list of characters.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]toLowerCase : (string Source) -> string Output.
Changes case of the letter characters in Source[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]toUpperCase : (string Source) -> string Output.
Changes case of the letter characters in Source[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trim : (string Source) -> string Output.
Removes both leading and trailing whitespaces from the string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trimFront : (string Source) -> string Output.
Removes leading whitespaces from the string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trimInner : (string Source) -> string Output.
Removes groups of whitespaces from the Source line.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trimRear : (string Source) -> string Output.
Removes trailing whitespaces from the string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryFront : (string Source, charCount Count, string First [out], string Last [out]) determ.
Splits a string into two strings at a certain position.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]tryReplacePart : (string Source, charCount Position, charCount HowLong, string ReplaceWith) -> string Output determ.
Replaces a part of a string with another string.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trySubString : (string Source, charCount Position, charCount HowLong) -> string Output determ.
Returns a substring of Source.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]trySubchar : (string String, charCount Position) -> char RetChar determ.
Returns the character RetChar at a given Position in the specified String.[/TD]
[TD][/TD]
[/TR]
[TR]
[TD]write : ( .) -> string Output.
Write several arguments into a string.[/TD]
[TD][/TD]
[/TR]
[/TABLE]


Phần 2: KẾT NỐI VISUAL PROLOG VỚI C#

Để kết nối được chúng ta sẽ tạo ra file .dll trong Visual prolog rồi nhúng vào C#. Ở đây ta lấy ví dụ dùng C# để gọi predicates tính giai thừa của Visual prolog.











2.1. Tạo ra file .dll trong chương trình Visual prolog
- Chạy chương trình Visual prolog ta được hình bên dưới

[​IMG]

- Click nút New Project

[​IMG]

o Project Name: điền tên của project (giaithua)
o UI Strategy: chọn Console
o Target Type: chọn Dll
- Sau khi đã điền như trên ta được hình như sau

[​IMG]

- Click OK ta được

[​IMG]

o Ta chú ý vào file export.cl và export.pro


- D_click vào export.cl ta được hình như sau
[​IMG]


- Ta sẽ thay thế exportedPredicate : () procedure () language stdcall as "exportedPredicate".
thành
giaithuainteger INT) -> integer Gt procedure (i) language stdcall as "gt".
Chú ý: “gt” là điểm để gọi ta sẽ nhớ nó để qua C# còn làm
- Ta đã xong phần định nghĩa predicates mà ta sẽ gọi. bây giờ ta sẽ xây dựng luật tính giai thừa và trả về kết quả cho predicates giaithua.
- D_click vào export.pro hình bên dưới suất hiện

[​IMG]

- Ta sẽ xây dựng luật tính giai thừa như sau:
class predicates
gtinteger,integer) procedure (i,o).
clauses
gt (N, 1) :- N<1, !.
gt(N, N*F) :- gt(N-1, F).
- Sau đó ta sẽ xây dựng luật cho predicates giaithua
clauses
giaithua(A) = Result:-gt(A,Result).
- Đưa các luật trên vào export.pro ta được hình sau

[​IMG]

- Sau đó ta nhấn (ctrl+alt+shift+B) để Rebuild All. Sau khi Rebuild xong nó sẽ tạo ra 3 file .dll là Giaithua.dll,vip7kernel , vip7run. Ba file .dll này trong trong thư mục exe của project mà ta đã tạo ra ban đầu. Chúng ta đã xong bước tạo ra file .dll trong Visual prolog

2.2. Kết nối với C#
- Khởi động chương trình C# chọn File / New/ Project hình sau xuất hiện

[​IMG]

- Ta chọn Windows Forms Application
o Name: ta chọn tên của project ở đây ta để mặc đinh như trên
o Location: đường dẫn chứa project
- Click OK. Form của project sẽ xuất hiện ta thêm một nút button tên Kết quả một textbox để nhập và một lable hiển thị kết quả khi nhấn vào nút button ta được hình sau:

[​IMG]

- Chọn tag Form1.cs và thêm vào những dòng lệnh khoanh tròn bên dưới hình:

[​IMG]

- Bây giờ ta viết sự kiện cho nút kết quả.
- Trở về tag Form1.cs[Design]* d_click vào button kết quả và viết sự kiện cho nó , sự kiện được thêm vào được khoan tròn như hình dưới.

[​IMG]

- Sau khi viết sự kiện xong ta nhấn F6 để build chương trình và chương trình sẽ báo lỗi vì ta chưa đưa file .dll vào. Bây giờ ta sẽ coppy 3 file .dll đã tạo ra từ chương trình Visual prolog vào thư mục Debug của project C#.
- Sau đó nhấn F6 để Buil lại và chạy chương trình. Để chạy chương trình bạn nhấn Ctrl+F5 nếu bạn nhấn F5 chương trình sẽ báo lỗi.










Phần 3: BÀI TOÁN TA-CANH

3.1. Giới thiệu bài toán:
· 8-puzzle


- Trạng thái ban đầu
[TABLE="align: center"]
[TR]
[TD]2[/TD]
[TD]3[/TD]
[TD]5[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD][/TD]
[TD]7[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]6[/TD]
[TD]8[/TD]
[/TR]
[/TABLE]

- Trạng thái đích
[TABLE="align: center"]
[TR]
[TD]1[/TD]
[TD]2[/TD]
[TD]3[/TD]
[/TR]
[TR]
[TD]8[/TD]
[TD][/TD]
[TD]4[/TD]
[/TR]
[TR]
[TD]7[/TD]
[TD]6[/TD]
[TD]5[/TD]
[/TR]
[/TABLE]

- Bài toán giải quyết đưa trạng thái ban đầu đưa về trạng thái đích bằng cách di chuyển ô trống.

3.2. Giới thiệu thuật toán A*
- Thuật toán A* là thuật toán tìm kiếm có tính heuristic trên không gian trạng thái dựa vào hàm f, được định nghĩa như sau:
f=g(n)+h’(n)
g(n): chi phí thực sự đi từ nút đầu đến nút n
h’(n): chi phí ước lượng đi từ nút n đến trạng thái đích


[​IMG][​IMG]

- Để cài đặt giải thuật A* ta dùng hai danh sách để chứa các trạng thái, danh sách Open chứa các trạng thái chưa xét, danh sách Close chứa các trạng thái đã xét.

3.3. Giải thuật A* cho bài toán ta canh
- Tính hàm h’(n) bằng khoảng cách Manhattan
[​IMG] [​IMG]
Current State Goal State
[​IMG] [​IMG] [​IMG]
2 bước 3 bước 3 bước

h’(n)=h’(Current State)=2+3+3=8
g(n)=g(Current State)=g(cha Current State)+1
- Nếu Current State là nút khởi đầu thì g(Current State=0)
f(n)=f(Current State)=g(Current State)+h’(Current State)

3.4. Giải thuật A* của bài toán đa canh viết bằng Visual prolog
State: trạng thái đang xét
Goal: trạng thái đích
DS: độ sâu của một node hay nó là hàm g trong giải thuật A*
Openlist: Danh sách Open chứa các trạng thái chưa xét
Closelist: Danh sách Close chứa các trạng thái đã xét
CLS: giống như danh sách Close nhưng các trạng thái có hàm f(n)
- Luật tìm danh sách CLS chứa các trạng thái mà giải thuật A* đã xét
search_d(State,Goal,DS,Openlist,Closelist,CLS):-
if State=Goal then themh(DS,State,NState),%them hàm f vào một node
CL=list::append([NState],CLS),%cho trạng thái đích vào danh sách CL
assertz(listnode(CL)),assertz(stt(list::length(CL)))%lưu lại tập CL vào danh sách listnode
else
if list::isMember(State,Closelist) %if State có trong Closelist thì làm
then
NewState=list::nth(0,Openlist),%tìm 1 trạng thái mới trong danh sách Open
NOpen=list::remove(Openlist,NewState),%remove trạng thái ra khỏi danh sách Open
loaibohfc(NewState,NNewState),%loại bỏ hàm f
h_fcn(NNewState,H),%tính h'(n)
DSS=list::nth(0,NewState)-H,%tính g(n)
search_d(NNewState,Goal,DSS,NOpen,Closelist,CLS)
else
themh(DS,State,NState),% them ham huerictic vao mot node
phatsinh(DS,NState,Children),% tu mot tran gthai phat sinh ra cac trang thai co the
NewClose=list::append([State],Closelist),%add trang thai dang xet vao danh sach closelist
CL=list::append([NState],CLS),
NewOP=list::append(Children,Openlist),
NewOpen=list::sort(NewOP,core::ascending()),%sap xep lai openlist
NewState=list::nth(0,NewOpen),%tim mot trang thai moi trong openlist
NOpen=list::remove(NewOpen,NewState), remove trạng thái ra khỏi danh sách Open
loaibohfc(NewState,NNewState),%loai bo ham huerictic
h_fcn(NNewState,H),%tinh khoang cach mathan
DSS=list::nth(0,NewState)-H,%tinh do sau cua node dang xet
search_d(NNewState,Goal,DSS,NOpen,NewClose,CL)end if end if.
- Sau khi đã tìm được danh sách CLS ta bắt đầu tìm đường đi từ trạng thái đích lên trạng thái đầu.
- Luật tìm đường đi
sinhGoal(DS,Goal,Closelist,Path):-if DS>-1
then C=[Sinh||move(DS,Sinh,Goal,_)],%tìm tất cả các trạng thái sinh ra Goal
L=list::difference(C,Closelist),%lấy các trạng thái ko có trong danh sách Closelist
SN=list::nth(0,list::difference(C,L)),%lấy ra một trạng thái có trong Closelist la SN
move(DS,SN,Goal,P),%tìm đường đi từ trạng thái SN đến Goal
Pa=list::append([P],Path),%Cho đường đi vào một danh sách
sinhGoal(DS-1,SN,Closelist,Pa) %tìm đường đi cho nút sinh ra nút SN
else Pa= list::append(Path,["TC"]),assertz(path(Pa)) %ghi danh sach vào fact path
end if.
3.5 Mở rộng bài toán n-puzzle
· 15-puzzle


Khá ổn thỏa với bài toán 8-puzzle, ta thử phân tích tiếp bài toán 15-puzzle. Và bất ngờ bạn gặp phải vấn đề khi kiểm tra theo cách tương tự như với bài toán 8-puzzle: Khi di chuyển ô trống trong bảng giữa các dòng và tính toán giá trị N thì bạn nhận ra rằng N sẽ thay đổi giá trị chẵn, lẽ.
[​IMG]
15-puzzle
Ví dụ như các bảng phía trên bạn tính được N tương ứng khi di chuyển ô trống giữa các dòng lần lượt là 60, 59, 60, 61. Qua vài lần thử bạn có thể nhận ra quy luật là N là lẻ khi ô trống nằm ở các dòng lẻ tính từ trên xuống (dòng đầu tiên là 1), và N là chẵn khi ô trống nằm ở các dòng chẵn tính từ trên xuống.
Sự khác biệt này so với phiên 8-puzzle là do độ dài cạnh (n) khác nhau. Tức là với n lẻ thì giá trị N mod 2 sẽ ko thay đổi, với n thì thì nó sẽ thay đổi tương ứng với vị trí dòng của ô trống trên bảng.
Ta đã so sánh và nhận thấy là không thể áp dụng cùng quy luật của bài toán 8-puzzle để kiểm tra xem bài toán có thể giải được không. Phân tích lại bài toán 8-puzzle bạn có thể vẫn thắc mắc tại sao việc di chuyển ô trống giữa hai dòng lại không làm thay đổi tính chẵn lẻ của N.
Thử chuyển bảng 3×3 này dạng mảng 1 chiều rồi hình dung việc di chuyển ô trống giữa các hàng.
[​IMG]
8-puzzle dạng mảng một chiều
Như trong bảng 3×3 khi di chuyển ô trống lên phía trên tức là hoán vị ô thứ 3 và ô thứ 6. Tạm thời không quan tâm đến ô trống, ta chỉ xét ô có giá trị 1, dãy trên chuyển thành như sau:
[​IMG]
Giá trị N ban đầu được tăng lên 2 là do hiện tại có thêm hai ô lớn hơn nằm trước ô có giá trị 1. Nếu thử vài lần bạn có thể thấy khi di chuyển ô trống giữa các dòng thì giá trị N mới sẽ có 1 trong 3 trường hợp: không thay đổi, tăng 2, giảm 2. Ta có nhận xét: giá trị N mới tăng giảm ±1 với số lần chẵn.
Tương tự với n=4 ta có:
[​IMG]
Di chuyển ô trống giữa các dòng trong 15-puzzle
- L1: Việc di chuyển ô số 6 xuống vị trí cuối làm giảm N đi 2 đơn vị (do đứng sau ô 3 và 5) và tăng N lên 1 đơn vị (do đứng sau ô số 9). Ta được N = N – 1 – 1 + 1.
- L2: di chuyển ô số 4 xuống vị trí 12 tăng N lên 2 đơn vị (đứng sau ô 14 và 10) và giảm N 1 đơn vị (do đứng sau ô số 1). Ta được N = N +1 +1 – 1.
- L3: Tương tự N = N + 1 +1 – 1.
Tức là mỗi lần ô trống giữa các dòng ta chỉ làm thay đổi giá trị N đi 1 đơn vị. Nếu thử với các trường hợp khác, giá trị N có thể thay đổi 3 đơn vị. Nhận xét giá trị N mới tăng giảm ±1 với số lần lẻ.
Với hai ví dụ trên ta nhận ra một quy luật là:
Khi thay đổi vị trí ô trống giữa các dòng thì giá trị N sẽ thay đổi tương ứng với giá trị là số lẻ hay số chẵn tùy thuộc vào n. Tổng quát lên chính là n-1 cũng là giá trị tối đa mà N có thể thay đổi.
Cuối cùng ta suy ra phương pháp tổng quát để áp dụng cho mọi n.