CSC-SY

مسألة الوزراء الثمانية الشهيرة (لمن لا يعرفها المطلوب فيها وضع ثمانية وزراء على رقعة الشطرنج دون أن يهدد أي منها الآخر).

لحل المسألة سنقوم بترميز رقعة الشطرنج كمايلي: (مثال من أجل 4 * 4).

________________
|     |     | Q  |     |
|___|___|___|___|
|  Q |     |     |     |
|___|___|___|___|
|     |     |      | Q |
|___|___|___|___|
|     | Q  |      |    |
|___|___|___|___|

من أجل حالة الرقعة السابقة فإننا سنمثلها بقائمة الأرقام 3,1,4,2 وهي كما تلاحظون أرقام سطر كل وزير إذا عددنا الأعمدة من اليسار إلى اليمين.

كي لا يهدد أي وزير وزيراً آخراً يجب أن لا يكون على نفس السطر أو العمود أو القطر مع أي وزير آخر.
إذا كان أي حل من الحلول محققاً لشرط السطر والعمود فإن تمثيله سيكون أحد تباديل المجموعة 1 2 3 4 5 6 7 8 ....
أي أن مجموعة الحلول هي مجموعة جزئية من مجموعة تباديل 1 2 3 4 5 6 7 8

بقي لدينا شرط عدم وجود وزيرين على نفس القطر الرئيسي أو الثانوي.
إن الذي فكر بحل المسألة بالطريقة التقليدية (خوارزميات 1 ) لا بد أن يتذكر ما يلي:
1- جميع مربعات القطر الرئيسي (والأقطار الأخرى التي توازيه من الشكل / ) تحقق أن رقم سطرها - رقم عمودها = ثابت.... أي إذا وجد وزيران على نفس القطر / فإن المقدار سطر - عمود متساوي.
(ولكل قطر من الأقطار ثابته المختلف... تحقق من ذلك بنفسك ) مثال القطر الرئيسي حاصل طرح سطر عمود دائماً هو الصفر.
2- جميع مربعات القطر الثانوي (والأقطار الأخرى التي توازيه من الشكل \ ) تحقق أن رقم سطرها + رقم عمودها = ثابت.... أي إذا وجد وزيران على نفس القطر \ فإن المقدار سطر + عمود متساوي.
(ولكل قطر من الأقطار ثابته المختلف... تحقق من ذلك بنفسك ) مثال القطر الثانوي حاصل جمع سطر + عمود = n + 1 = 8 + 1

أصبح لدينا:

من أجل أي حل abcdefgh (تذكر أن هذه الأحرف هي أرقام الأسطر) أرقام أسطرها هي 12345678 وهذا يعني ليكون الحل مقبولاً :
1- مركبات الشعاع الناتج عن طرح الشعاعين 12345678 و abcdefgh يجب أن تكون مختلفة.
2- مركبات الشعاع الناتج عن جمع الشعاعين 12345678 و abcdefgh يجب أن تكون مختلفة أيضاً.

فالحل المقبول للمسألة هو أي تبديل للشعاع 12345678 يحقق الشرطين السابقين.

والآن لكتابة كود الـProlog سنقوم بتعريف الإجرائيات التالية:
1- perm والذي يعطينا جميع التباديل الممكنة لشعاع.
2- combine والذي يعطينا المجموع والفرق لشعاعين.
3- all_diff والذي يحققه كل شعاع مختلف العناصر.
4- solve والذي سيستخدم ما سبق لحل المسألة.

perm:

perm([],[]).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).   


takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

الشرح:

* تباديل القائمة الخالية هي القائمة الخالية.
*تباديل أي قائمة تبدأ بعنصر X وتتمتها القائمة Y هي جميع القوائم الناتجة من توزيع العنصر X على القائمة W في جميع المواضع، بحيث أن القائمة W هي جميع تباديل القائمة Y.

الإجراء takeout مساعد لـ perm يقوم بإزالة أول ورود لعنصر X في قائمة. (طبعاً بالنسبة لنا في هذه المسألة هو الورود الوحيد).

combine:

combine([],[],[],[]).

combine([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
     S1 is X1 +Y1,
     D1 is X1 - Y1,
     combine(X,Y,S,D).

الشرح:
* مجموع وفرق قائمتين فارغتين هما قائمتان فارغتان.
* مجموع (أوفرق) قائمتين تبدأان بالعنصرين X1, Y1 وتتمتهما القائمتين X, Y هي القائمة التي تبدأ بـ X1 + Y1 (أو X1 - Y1) وتنتهي بالقائمة التي هي مجموع (أو فرق) القائمتين X, Y.

all_diff:

all_diff([_]).
all_diff([X|Y]) :-  \+member(X,Y), all_diff(Y).

الشرح:
* جميع عناضر القائمة وحيدة العنصر مختلفة.
* لتكون القائمة التي تبدأ بـ X وتتمتها القائمة Y مختلفة العناصر يجب أن تكون Y مختلفة العناصر و ( X من عناصر Y) لا يمكن إثباته (أي X ليس من عناصر Y).

ملاحظة: \+ تعني not provable .

solve:

solve(P) :-
     perm([1,2,3,4,5,6,7,8],P), 
     combine([1,2,3,4,5,6,7,8],P,S,D),
     all_diff(S),
     all_diff(D).

الشرح:
P هو حل للمسألة إذا كان من أحد تباديل القائمة 12345678 و كان كلٌّ من مجموعِهِ وفرقِهِ مع الشعاع 12345678 هو شعاع ذو عناصر مختلفة.

الكود النهائي للتنفيذ بـ SWI-Prolog

solve(P) :-
     perm([1,2,3,4,5,6,7,8],P), 
     combine([1,2,3,4,5,6,7,8],P,S,D),
     all_diff(S),
     all_diff(D).



all_diff([_]).
all_diff([X|Y]) :-  \+member(X,Y), all_diff(Y).



combine([],[],[],[]).
combine([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
     S1 is X1 +Y1,
     D1 is X1 - Y1,
     combine(X,Y,S,D).



perm([],[]).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).   



takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

كيفية التنفيذ:
1- احفظ الكود السابق إلى ملف مثل queen.pl
2- قم بتشغيل SWI-Prolog
3- قم بتغيير مسار العمل إلى مكان حفظك للملف بواسطة التعليمة

cd('<yourpath>').

<yourpath> هو مكان حفظك للملف

4- حمل الملف بالتعليمة:

['queen.pl'].

5- نفذ التعليمة التالية للحصول على الحلول:

solve(X).

.

فيظهر لك أول حل. ومن أجل الحلول الأخرى إضغط الفاصلة المنقوطة بدلاً من enter

_____________

البرنامج السابق يقوم بتوليد جميع الحلول من أجل المسألة 8*8 والبالغ عددها 92 ولكن من أجل مسائل أكبر تستطيع ملاحظة عدم فعاليته...

لاحظ أن البرنامج يولد جميع التباديل الممكنة للحصول على الحلول مع العلم أن العديد من التباديل يمكن رفضها قبل المتابعة لأنها ستخل بشرط الأقطار.
مثال:
الحل الجزئي الذي يبدأ بـ 1,3,2 يمكن التعرف إليه مسبقاً بأنه لن يحقق الشرط القطري....

السؤال: كيف يمكننا التعديل على البرنامج السابق بحيث نستطيع تلافي هذه المشكلة؟
في الحقيقة أنا حاولت شوي بس ما مشي الحال

_________
ملاحظة: يمكنكم تحميل SWI-Prolog من الرابط التالي:

http://www.swi.psy.uva.nl/cgi-bin/nph-download/SWI-Prolog/w32pl5213.exe

حجمو أكتر من 3 ميغا بشوي... يالله.... بيعينكم الله

for Visual Prolog 5.2

domains

nlist = integer*


predicates
nondeterm solve(nlist)
combine(nlist,nlist,nlist,nlist)
all_diff(nlist)
nondeterm perm(nlist,nlist)
nondeterm takeout(integer,nlist,nlist)
nondeterm member(integer,nlist).


clauses



solve(P) :-
     perm([1,2,3,4,5,6,7,8],P), 
     combine([1,2,3,4,5,6,7,8],P,S,D),
     all_diff(S),
     all_diff(D).



combine([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
     S1 = X1 +Y1,
     D1 = X1 - Y1,
     combine(X,Y,S,D).
combine([],[],[],[]).

all_diff([_]):-!.
all_diff([X|Y]) :-  not(member(X,Y)), all_diff(Y).


perm([],[]).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).   



takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

member(X,[X|_]):-!.
member(X,[_|Z]):-member(X,Z).



goal

solve(X).

thanx Salem

انا طالبه فى جامعه مطلوب مننابحث عن الوزراء الثمانيه ياريت ترودو عليا