Lập trình Logic ProLog: Phần 9 - PGS.TS. PHAN HUY KHÁNH (Hướng dẫn chi tiết)

148 Lp trình lägich trong Prolog

•

Hình II.7. Mt li gii ca bài toán tám quân hu,

biu din bi danh sách [ 1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1

] .

/ ây, phép toán / không phi là phép chia, mà ch" là cách t( hp hai to 

ca mt ô bàn c. Hình 5.6 trên ây là mt li gii khác ca bài toán tám quân

hu c biu din di dng mt danh sách nh sau :

[ 1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1 ]

T' cách biu din danh sách, ta cn tìm li gii có dng :

[ X1/Y1, X2/Y2, X3/Y3, ... , X8/Y8 ]

Ta cn tìm các giá tr ca các bi!n X1, Y1, X2, Y2, X3, Y3, ... , X8, Y8. Do

các quân hu phi n$m trên các ct khác nhau  không th &n l0n nhau, nên ta

có ngay giá tr ca các to  X, và li gii lúc này có dng :

[ 1/Y1, 2/Y2, 3/Y3, ... , 8/Y8 ]

Cho !n lúc này, bài toán tám quân hu ch" t ra i vi bàn c 8 × 8. Tuy

nhiên, li gii phi d, ki!n c cho trng hp t(ng quát khi lp trình. / ây,

ta s- thy r$ng chính trng hp t(ng quát li n gin hn bài toán ban u. Bàn

c 8 × 8 ch" là mt trng hp riêng.

) gii quy!t cho trng hp t(ng quát, ta chuyn kích thc 8 quân hu

thành mt s quân hu bt k nào ó (mi ct mt quân hu), k c s ct b$ng

không. Ta xây d,ng quan h solution t' hai tình hung sau :

1. Danh sách các quân hu là rng : danh sách rng c#ng là mt li gii vì

không xy ra s, tn công nào.

solution( [ ] ).

2. Danh sách các quân hu khác rng và có dng nh sau :

[ X/Y | Others ]

K thut lp trình Prolog 149

Trong trng hp th hai, quân hu th nht n$m trên ô X/Y, còn nhng quân

hu khác n$m trong danh sách Others. N!u danh sách này là mt li gii, thì

nhng iu kin sau ây phi c tho mãn :

1. Nhng quân hu trong danh sách Others không th tn công l0n nhau,

iu này nói lên r$ng Others c#ng là mt li gii.

2. V trí X và Y ca nhng quân hu phi n$m gia 1 và 8.

3. Mt quân hu ti v trí X/Y không th tn công mt quân hu nào khác

trong danh sách Others.

)i vi iu kin th nht, quan h solution phi c gi mt cách 

quy.

)iu kin th hai nói lên r$ng Y phi thuc v danh sách [ 1, 2, 3, 4,

5, 6, 7, 8 ]. / ây, ta không cn quan tâm !n v trí X, vì nó phi tng hp

vi danh sách k!t qu tr v nh ta ã xác nh ngay t' u. Ngha là X phi

thuc v nhng giá tr ã c n nh tng ng.

Gi s iu kin th ba c gii quy!t nh quan h noattack, chng trình

Prolog cho quan h solution nh sau :

solution( [ X/Y | Others ] ) :-

solution( Others ),

member( Y, [ 1, 2, 3, 4, 5, 6, 7, 8 ] ),

noattack( X/Y, Others ).

Bây gi ta cn tìm quan h noattack. Ta thy :

1. N!u danh sách Rlist rng, khi ó noattack là úng, vì không có quân

hu nào tn công quân hu ti X/Y nào ó.

noattack( _, [ ] ).

2. N!u danh sách Rlist khác rng, khi ó có dng [ R1 | Rlist1 ] và

hai iu kin sau ây phi c tho mãn :

(a) Quân hu ti ô R không th tn công quân hu ti ô R1, và

(b) Quân hu ti ô R không th tn công quân hu nào trong Rlist1.

) mt quân hu không th tn công quân hu khác, thì chúng không th n$m

trên cùng hàng, cùng ct và cùng ng chéo chính hoc ph. Ta bi!t chc chn

r$ng các quân hu ã n$m trên các ct phân bit nhau do mô hình li gii ã n

nh. Bây gi ta cn ch" ra r$ng :

• Các to  Y ca các quân hu phi phân bit nhau, và

• Các quân hu không th n$m trên cùng ng chéo chính hoc ph. ngha

là khong cách gia các ô trên trc X phi khác vi các ô trên trc Y.

150 Lp trình lägich trong Prolog

noattack( X/Y, [ X1/Y2 | Others ] ) :-

Y =\= Y1,

Y1 - Y =\= X1 - X,

Y1 - Y =\= X - X1,

noattack( X/Y, Others ).

Di ây là chng trình Prolog y  th nht có cha danh sách li gii là

quan h model. Mô hình làm cho vic tìm li gii cho bài toán tám quân hu tr

nên n gin hn.

% chng trình th nht gii bài toán tám quân hu

% The problem of the eight queens - Program 1

% −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

solution( [ ] ).

solution( [ X/Y | Others ] ) :-

solution( Others ),

ismember( Y, [ 1, 2, 3, 4, 5, 6, 7, 8 ] ),

noattack( X/Y, Others ).

noattack( _ , [ ] ).

noattack( X/Y, [ X1/Y1 | Others ] ) :-

Y =\= Y1,

Y1 – Y =\= X1 - X,

Y1 – Y =\= X - X1,

noattack( X/Y, Others ).

ismember( X , [ X | L ] ).

ismember( X, [ Y | L ] ) :-

ismember( X, L ).

model( [ 1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8

] ).

?- model( S ), solution( S ).

S = [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1] ;

S = [1/5, 2/2, 3/4, 4/7, 5/3, 6/8, 7/6, 8/1] ;

S = [1/3, 2/5, 3/2, 4/8, 5/6, 6/4, 7/7, 8/1] ;

S = [1/3, 2/6, 3/4, 4/2, 5/8, 6/5, 7/7, 8/1] ;

S = [1/5, 2/7, 3/1, 4/3, 5/8, 6/6, 7/4, 8/2] ;

S = [1/4, 2/6, 3/8, 4/3, 5/1, 6/7, 7/5, 8/2]

Yes

S dng v t' not, ta vi!t li chng trình nh sau :

solution( [ ] ).

solution( [ X/Y | Others ] ) :-

K thut lp trình Prolog 151

solution( Others ),

member( Y, [ 1, 2, 3, 4, 5, 6, 7, 8 ] ),

not( attack( X/Y, Others )).

attack( X/Y, Others ) :-

member( X1/Y1, Others ),

( Y1 = Y,

Y1 is Y + X1 - X;

Y1 is Y - X1 + X ).

member( A, [ A | L ] ).

member( A, [ B | L ] ) :-

member( A, L).

% Mô hình li gii

model( [ 1/Y1, 2/Y2, 3/Y3, 4/Y4, 5/Y5, 6/Y6, 7/Y7, 8/Y8

] ).

?- model( S ), solution( S ).

S = [1/1, 2/1, 3/1, 4/1, 5/1, 6/1, 7/1, 8/1] ;

S = [1/1, 2/8, 3/1, 4/1, 5/1, 6/1, 7/1, 8/1] ;

S = [1/2, 2/8, 3/1, 4/1, 5/1, 6/1, 7/1, 8/1] ;

S = [1/1, 2/1, 3/7, 4/1, 5/1, 6/1, 7/1, 8/1] ;

S = [1/3, 2/1, 3/7, 4/1, 5/1, 6/1, 7/1, 8/1] ;

S = [1/1, 2/2, 3/7, 4/1, 5/1, 6/1, 7/1, 8/1]

Yes

>4 GE"a!,@e!

Trong chng trình th nht, ta ã a ra li gii biu din bàn c có dng :

[ 1/Y1, 2/Y2, 3/Y3, ... , 8/Y8 ]

do mi ct ch" t úng mt quân hu. Th,c ra, ta không mt thông tin n!u b+ i

các to  X. Ta có th biu din bàn c ch" vi các to  Y ca các quân hu :

[ Y1, Y2, Y3, ... , Y8 ]

) không xy ra các quân hu n$m trên cùng ct, cn phi b trí mi quân

hu mt hàng. T' ây ta t ra ràng buc cho các to  Y : mi hàng 1, 2, 3, ...,

8 ca bàn c ch" c phép t duy nht mt quân hu. Ta nhn thy r$ng mi

li gii là mt hoán v ca danh sách các s 1 .. 8 sao cho th t, ca mi con s

là khác nhau :

[ 1, 2, 3, 5, 6, 7, 8 ]

Mi hoán v ca danh sách là mt li gii S sao cho các quân hu  trng thái

an toàn (không &n c l0n nhau). Ta có :

152 Lp trình lägich trong Prolog

solution( S ) :-

permutation( [ 1, 2, 3, 5, 6, 7, 8 ], S ),

insafety( S ).

Trong chng 1 trc ây, ta ã xây d,ng quan h permutation, bây gi ta

cn nh ngha quan h safety. Xy ra hai trng hp nh sau :

1. N!u danh sách S rng, khi ó S c#ng là li gii, vì không có quân hu nào

tn công quân hu nào.

insafety( [ ] ).

2. N!u danh sách S khác rng, khi ó S có dng [ Queen | Others ].

Ta thy S là li gii n!u các quân hu trong Others là  trng thái an

toàn và quân hu Queen không th tn công quân hu nào trong Others.

T' ó ta có :

insafety( [ ] ).

insafety( [ Queen | Others ] ) :-

insafety( Others ),

noattack( Queen, Others ).

Trong nh ngha insafety, quan h noattack t+ ra tinh t! hn so vi

c#ng cùng quan h này trong chng trình 1 trên ây. Khó kh&n n$m  ch v trí

ca mt quân hu ch" c xác nh bi các to  Y, mà vng mt to  X. )

nh ngha quan h noattack, ta tìm cách khái quát vn  nh nh minh ho 

hình di ây.

•

Hình II.8. Khong cách gia to  X ca Queen và to  X ca Others là 1.

(b) Khong cách gia to  X ca Queen và to  X ca Others là 3.

Ta thy r$ng s dng ích :

noattack( Queen, Others )

(a) (b)

Others

Queen

khong cách to  X = 1 khong cách to  X = 3

Lập Trình Logic Trong ProLog - PGS.TS. PHAN HUY KHÁNH phần 9

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi