لعبة سودكو الشهيرة، تعتمد في حلها على عدم تكرار نفس الرقم في نفس الصف او في نفس العمود او في نفس المربع
سنقوم بعمل برنامج لحل اللعبة بإستخدام لغة برولوج وعلى نموذج مصغر 4x4 ولكن بنفس القواعد. والأرقام المقبولة هي 1,2,3,4
?- solve(1,4, _, _, _, _, 4, _, 2, _, _,_, _, _, _, 3). 1 4 3 2 3 2 4 1 2 3 1 4 4 1 2 3
كيف نقوم بحل ذلك السؤال؟
انظر على حلول لغات مثل سي هنا
يوجد اتجاه او اسلوب برمجي اخر يسمى ال declarative programming ... كل ماعلينا هو أن نقوم بوصف الحل لا الخطوات للحل..
طريق سريع لبرولوج
1-التنصيب
مستخدمي لينكس موجود لديكم في مدير الحزم
striky@localhost ~/m/prolog> touch hello.pl master
striky@localhost ~/m/prolog> swipl master?
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.6.6)
Copyright (c) 1990-2013 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- write('Hello, World!').
Hello, World!
true.
?- write('Hello,'), nl, write('world').
Hello,
world
true.
?- X is 3*4 + 2.
X = 14.لاحظ أي امر في برولوج ينتهي بال نقطة .
write يستخدم لطباعة نص
nl
تستخدم لطباعة سطر جديد
البرنامج في برولوج عبارة عن قاعدة معرفة knowledge base وفيه يتم ادراج الحقائق facts وقواعد الأستنباط rules
friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). loves(john, julia). loves(julia, sam). loves(sam, julia). male(brad). male(john). male(jim). male(alfred). female(marry). child(brad, alfred). child(john, jim). child(john, marry).
هذا ملف KB يشمل مجموعة من الحقائق ... برولوج ستساعدنا كثيرا لإجابة الكثير من الاسئلة .. لنرى!
?- [hello]. % hello compiled 0.00 sec, 3 clauses true. ?- listing(friend). friend(john, julia). friend(john, jack). friend(julia, sam). friend(julia, molly). true. ?- listing(loves). loves(john, julia). loves(julia, sam). loves(sam, julia). true. ?- listing(parent). ERROR: toplevel: procedure `parent' does not exist (DWIM could not correct goal)
نستطيع استخدام listing لعرض الحقائق
?- friend(john, julia). true . ?- friend(john, jack). true. ?- loves(john, julia). true. ?- loves(john, sam). false.
استعلامات بسيطة على الحقائق التي لدينا
?- friend(john, Who). Who = julia ; Who = jack.
هذا الاستعلام يعني ... ماهي قيمة المتغير Who التي تجعل العلاقة friend(john, Who) صحيحة؟
نجد في ال KB قيم مثل julia وتقوم برولوج بإخبارنا بذلك .. ولكن يوجد قيم اخرى نستطيع الوصول اليها بالضغط على ;
*لاحظ ان المتغيرات تبدأ بحرف capital
الواد john دا ابن مين
?- listing(child). child(brad, alfred). child(john, jim). child(john, marry). true. ?- child(john, X). X = jim ; X = marry.
الأستنباط
يوجد الكثير من الأسئلة والأجابات
مثلا هل العلاقات
friend(julia, john)
صحيحة؟
هل john is friendzoned؟
:D
هل فلان ابو فلان؟
لنقوم بإضافة بعض القواعد
rule :- stmt1, stmt2,...
تنطق ال rule محققة اذا كان ( :- ) stmt1, stmt2 محققين
parent(X, Y) :- child(Y,X).
فلان X هو أبو Y في حال اذا كان Y هو ابن ل X
father(X, Y) :- child(Y,X), male(X).
فلان X هو اب ل Y في حال اذا كان Y هو ابن X وX هو male
mother(X, Y) :- child(Y,X), female(X).
فلان X هي ام ل Y في حال اذا كان Y هو ابن ل X و X تكون female
friend(X, Y) :- friend(Y,X).
فلان X صديق Y .. اذا كان في ال kB معروف ان Y صديق X
friendzoned(X) :- loves(X, Y), \+ loves(Y,X).
فلان X في ال friendzone اذا كان X بيحب Y وفي نفس الوقت Y لاتحب X
?- friend(julia, john). true . ?- male(jim). true. ?- parent(jim,X). X = john. ?- father(jim, X). X = john. ?- mother(X, john). X = marry. ?- mother(marry,X). X = john. ?- mother(marry, john). true.
قصة قصيرة حزينة...
جون بيحب جوليا، ولكن جوليا وسام بيحبوا بعض
?- loves(julia, X). X = sam. ?- friendzoned(julia). false. ?- friendzoned(john). true.
الكود
اولا نقوم بتعريف ال domain .. وهو القيم المقبولة للمتغيرات
num(1). num(2). num(3). num(4).
التأكد من أن القيم فريدة بين 4 متغيرات
%create unique values of A,B,C,D based. uniq(A,B,C,D) :- num(A), num(B), num(C), num(D), \+ A=B, \+ A=C, \+ A=D, \+ B=C, \+ B=D, \+ C=D.
هنا نقول ان A لايساوي B ولايساوي C ولايساوي D وكذلك B لايساوي C ولا يساوي D وكذلك C لايساوي D وكل منهم عبارة عن رقم قد يكون 1 او 2 او 3 او 4
الحصول على الحل
%find solution to sudoku 4x4 based on constraints. solution(C11, C12, C13, C14, C21, C22, C23, C24, C31, C32, C33, C34, C41, C42, C43, C44) :- %rows (every row is uniq). uniq(C11, C12, C13, C14), uniq(C21, C22, C23, C24), uniq(C31, C32, C33, C34), uniq(C41, C42, C43, C44), %columns (every column is uniq). uniq(C11, C21, C31, C41), uniq(C12, C22, C32, C42), uniq(C13, C23, C33, C43), uniq(C14, C24, C34, C44), %blocks (every block (2x2) cells is uniq). uniq(C11, C12, C21, C22), uniq(C31, C32, C41, C42), uniq(C13, C14, C23, C24), uniq(C33, C34, C43, C44).
لاتنزعج!
اولا الboard او لوحة السودكو عبارة عن 16 خانة .. 4 صفوف و 4 أعمدة
قم بتسميتهم من C11 الى C44
C21 تعني الخلية في الصف الثاني والعمود الأول
الآن لنصف الحل ..
الحل يعتمد على
1-تفرد القيم في كل صف ..
uniq(C11, C12, C13, C14)
هنا نقول ان القيم C11, C12, C13,C14 المكونة للصف الأول يجب ان يتم اسناد قيمة مختلفة لها من 1 ل 4 وهذا ماوضحناه في uniq
وبالمثل مع الخلايا المكونة لباقي الصفوف الثاني والثالث والرابع
2- تفرد الفيم في كل عمود ..
uniq(C11, C21, C31, C41)
وبالمثل مع الخلايا المكونة لباقي الأعمدة
3- تفرد القيم في كل مربع
لدينا ٤ مربعات (C11, C12, C21, C22) (C31, C32, C41, C42)(C13, C14, C23, C24)(C33, C34, C43, C44)
يجب ان تكون الأرقام مختلفة داخل المربع
uniq(C11, C12, C21, C22)
لقد أنتهينا!
الآن برولوج ستقوم بالبحث عن القيم اللتي تتفق مع وصفنا لتلك المشكلة
الآن لنقوم بعرض القيم
solve(C11, C12, C13, C14, C21, C22, C23, C24, C31, C32, C33, C34, C41, C42, C43, C44) :- solution(C11, C12, C13, C14, C21, C22, C23, C24, C31, C32, C33, C34, C41, C42, C43, C44), showrow(C11, C12, C13, C14), showrow(C21, C22, C23, C24), showrow(C31, C32, C33, C34), showrow(C41, C42, C43, C44),nl.
كان من الممكن دمجهم في الكود السابق
فقط نقوم بطباع كل 4 خلايا المكونين لصف عن طريق showrow المعرف كالتالي
showspace :- write(' ').
%row representation.
showrow(A, B, C, D) :-
showspace, write(A), showspace, write(B), showspace, write(C), showspace, write(D), nl.*لاحظ showspace تقوم بطباعة مسافة فارغة فقط لاأكثر
الكود كامل
%based on thinking as computation example
%domain
num(1). num(2).
num(3). num(4).
showspace :- write(' ').
%row representation.
showrow(A, B, C, D) :-
showspace, write(A), showspace, write(B), showspace, write(C), showspace, write(D), nl.
%create unique values of A,B,C,D based.
uniq(A,B,C,D) :-
num(A), num(B), num(C), num(D), \+ A=B, \+ A=C, \+ A=D, \+ B=C, \+ B=D, \+ C=D.
%find solution to sudoku 4x4 based on constraints.
solution(C11, C12, C13, C14,
C21, C22, C23, C24,
C31, C32, C33, C34,
C41, C42, C43, C44) :-
%rows (every row is uniq).
uniq(C11, C12, C13, C14), uniq(C21, C22, C23, C24), uniq(C31, C32, C33, C34), uniq(C41, C42, C43, C44),
%columns (every column is uniq).
uniq(C11, C21, C31, C41), uniq(C12, C22, C32, C42), uniq(C13, C23, C33, C43), uniq(C14, C24, C34, C44),
%blocks (every block (2x2) cells is uniq).
uniq(C11, C12, C21, C22), uniq(C31, C32, C41, C42), uniq(C13, C14, C23, C24), uniq(C33, C34, C43, C44).
solve(C11, C12, C13, C14,
C21, C22, C23, C24,
C31, C32, C33, C34,
C41, C42, C43, C44) :-
solution(C11, C12, C13, C14,
C21, C22, C23, C24,
C31, C32, C33, C34,
C41, C42, C43, C44),
showrow(C11, C12, C13, C14), showrow(C21, C22, C23, C24), showrow(C31, C32, C33, C34), showrow(C41, C42, C43, C44),nl.