• 0
ahmed_youssef

مقدمة في برولوج وحل لعبة سودكو

بواسطة ahmed_youssef,

سؤال

تم النشر منذ

لعبة سودكو الشهيرة، تعتمد في حلها على عدم تكرار نفس الرقم في نفس الصف او في نفس العمود او في نفس المربع

 


سنقوم بعمل برنامج لحل اللعبة بإستخدام لغة برولوج وعلى نموذج مصغر 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-التنصيب


 

مستخدمي لينكس موجود لديكم في مدير الحزم

[email protected] ~/m/prolog> touch hello.pl master

[email protected] ~/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.


4

شارك هذا الرد

رابط المشاركة
شارك الرد من خلال المواقع ادناه

0 إجابة على هذا السؤال .

لاتوجد إجابات على هذا السؤال حتى الآن .

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان
إذهب إلى قائمة الأسئلة الذكاء الاصطناعي وتطبيقاته

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .