لغز الحصان التائه !

تقبل اخي Delphawi هذه المشاركة البسيطة

فانا عاشق قديم للشطرنج ولكني سأقدم الحل بدون خوارزمات أو أكواد ولكن بالرسم

فالحصان يصل للمربع H8 في سبعة نقلات

عذرا أخي sailor24 يبدوا أنك تعجلت قليلا وأنت تضع الفكرة !

فالمربع A 1 لايعتبر نقله وعلي ذلك فعدد النقلات يكون 6 نقلات فقط

والرسم التالي يوضح مسار أخر للنقلات بالحصان للمربع H 8

شكراً أخ smart-m و sailor24 , لكن هذا هو الجزء السهل يا شباب :) المشكلة اننا نريد حل دائم لجميع الحالات وبدءاً من أي مكان على اللوحة

بمعنى آخر , كيف سنجعل الكمبيوتر يفكر كما فكرتم ؟

بالمناسبة الحلول الجزئية مقبولة , لا يشترط ان تضع خوارزمية شاملة لكل الحلول ولا يشترط ان تترجمها إلى كود , يمكنك وضع ما توصلت إيه ونتناقش فيه إن شاء الله :)

السلام عليكم ورحمه الله وبركاتة

مرحباً بكم مجدداً إخوانى الكرام

يوجد عده حلول للوصول لهذا الهدف ولكن جميعها تعتمد على أن تكون هناك خطوتان ضروريتان يجب أن ينجزهما الحصان وهى تراجع خطوة لليسار فى أحد خطواته وأخرى للأسفل ليستطيع أن يصل للهدف ,

تفسير هذا لأن خطوات الحصان تحتم عليه أن يسير فى شكل L إما أفقى أو رأسى للوصول للهدف فلو طبقنا هذه القاعدة نسير بالحصان أربع حركات لن نستطيع الوصول للهدف لكون الهدف موجود فى مدى أقل

من مدى حركة الحصان وبالتالى يتسنى للحصان أن يقوم بتنفيذ الحركتين الضروريتين وهما خطوة للأسفل وأخرى للخلف ليستطيع تهيئة مكانه الصحيح للوصول للهدف .

أرجو أن أكون وفقت بشرح ما يدور فى ذهنى .

وإليكم طريقة أخرى للحل وهناك طرق أخرى تتبع القاعدة السابقة أيضاً :

هذا صحيح فعلا اخي ahmedsaoud31

فبعد ان راجعت النقلات التي اقترحها sailor24 و Smart-m والتي اقترحتها انت وجدت انه فعلا يتحتم دائما أن تكون هناك خطوتان ضروريتان يجب أن ينجزهما الحصان وهى تراجع خطوة لليسار فى أحد خطواته وأخرى للأسفل ليستطيع أن يصل للهدف ,

ولكن هل هذا يساعد علي استنباط خوارزمة للحل ؟

فلي رجاء لمن يضع تلك الخوارزمة ان يشرح لنا كيفيه انشاءها وكيف تعمل للاستفادة

السلام عليكم

اقتباس

ولكن هل هذا يساعد علي استنباط خوارزمة للحل ؟

فلي رجاء لمن يضع تلك الخوارزمة ان يشرح لنا كيفيه انشاءها وكيف تعمل للاستفادة

عذراً ما تعنى بخوارزمية كود بزيدو كود أم رسم flowchart لمحكاة برنامج يحاكى حركة الحصان على طاولة الشطرنج للوصول للهدف.

أم شرح لكيفية وصولة للهدف؟ فكما شرحة سابقاً لو طبقت خطوتين إحداهما للأسفل والأخرى لليسار فى أى مراحل حركة الحصان سوف تصل للهدف . لو قمت بتجربة هذه القاعدة سوف تصل لحلول أخرى كثيرة

غير الحلول السابقة .

فهيم فهمي كتب:

هذا صحيح فعلا اخي ahmedsaoud31

فبعد ان راجعت النقلات التي اقترحها sailor24 و Smart-m والتي اقترحتها انت وجدت انه فعلا يتحتم دائما أن تكون هناك خطوتان ضروريتان يجب أن ينجزهما الحصان وهى تراجع خطوة لليسار فى أحد خطواته وأخرى للأسفل ليستطيع أن يصل للهدف ,

ولكن هل هذا يساعد علي استنباط خوارزمة للحل ؟

فلي رجاء لمن يضع تلك الخوارزمة ان يشرح لنا كيفيه انشاءها وكيف تعمل للاستفادة

الحقيقة الخوارزمية هي خطوات تخبرها للحاسب , مثلاً كما ذكر الأخ أحمد :

تحرك إلى الأعلى

تحرك إلى اليسار

تحرك إلى الأسفل

... تحرك إلى الأعلى

هذه مثلاً خوارزمية , تعبر عن خطوات التنفيذ خطوة خطوة

السؤال , كيف يجد الحصان طريقه لو كان في أي موقع غير الزاوية العليا , وعلى لوحة شطرنج أكبر من 64 مربع ؟

هنا تحتاج إلى خطوات ثابتة يمكن تطبيقها على أي لوحة ومن أي مكان , طبعاً بمعلومية موقع البداية وحجم اللوحة

قمت بعجالة بهذا لذا يمكن أن تشوبه بعض الأخطاء ، الأمر يتعلق بإيجاد متتاليتين كل متتالية تتكون إما من الرقم ٢ أو ١ أو -١ أو -٢ دلالة على كيف تقدم الحصان في الرقعة ، إذن يجب الحصول على هاتين المتتاليتين حسب شرطين وضعتهما على حسب إفتراض لا يمكنني الجزم به لضيق الوقت لكن :

يجب أن يكون مجموع حدود المتتاليتين أصغر ما يمكن (ومتساويا بالنسبة للمتتاليتين ) ، أما الافتراض التاني فهو أن كل متتالية تتكون من عدد من الحدود يساوي طول الرقعة - ٢ .

السلام عليكم

اقتباس

الحقيقة الخوارزمية هي خطوات تخبرها للحاسب , مثلاً كما ذكر الأخ أحمد :

تحرك إلى الأعلى

تحرك إلى اليسار

تحرك إلى الأسفل

... تحرك إلى الأعلى

على هذا فأقل عدد من الحركات للحصان ليصل للهدف هى 6 حركات على أن يكون ضمن تلك الحركات التقدمية نحو الهدف حركتان تراجعيتان إحداهما فى الإتجاه الأسفل والأخرى فى إتجاه اليسار , وهاتين الخطوين

لا تكونا فى الخطوة الأولى أو الأخيرة ولكن تكونان محصورتان فى النطاق من الخطوة الثانية للخطوة الخامسة , وذلك لأن موضع الحصان فى الخطوة الأولى لا يسمح له إلا بحركتين لا ثالث لهما والأخيرة يجب أن يكون فى إحدى موضعين لا ثالث لهما أيضاً للوصل للهدف.

أرجو أن تكون هى تلك الخوارزمية التى تعنيها

تعديل :

اقتباس

السؤال , كيف يجد الحصان طريقه لو كان في أي موقع غير الزاوية العليا , وعلى لوحة شطرنج أكبر من 64 مربع ؟

هنا تحتاج إلى خطوات ثابتة يمكن تطبيقها على أي لوحة ومن أي مكان , طبعاً بمعلومية موقع البداية وحجم اللوحة

تقصد كون نقطة الهدف المراد الوصول إليها تكون فى موضع غير الزاوية العليا ونقطة البداية أيضاً تكون فى أى موضع واللوحة أيضاً تتكون من عدد صفوف وأعمدة n*n غير ثابت.

السلام عليكم ورحمة الله وبركاته

اعتقد انه تم الوصول لأقصر 17 حل فى خلال 6 نقلات فقط

وتم ارفاق الصورة والبرنامج

Chess Puzzle.rar

رائع أخي fmgret12

+1

هل يمكنك شرح كيفيه تصميم البرنامج اثابك الله

وحتي تكتمل الإفادة للجميع

سؤال رائع جدا

وهذي هي الاسئلة المفيدة الي تنمي مهارة البرمجة لدينا

أنا أريد جميع الشباب بلا استثناء يكتب كود برمجي يطبع الطرق الممكنة

راح نصف المشكلة برمجيا وبعدها أترك الجميع يحاول يطبق البرنامج

أولاً: تمثيل لوحة الشطرنج بالحاسب:

لوحة الشطرنج راح تكون بهذا الشكل: أول خانة (1,1) وآخر خانة (8,8) أو تكون أول خانة (0,0) والاخيرة (7,7)

راح تكون كالتالي:

(0,7),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7)
(0,6),(1,6),(2,6),(3,6),(4,6),(5,6),(6,6),(7,6)
(0,5),(1,5),(2,5),(3,5),(4,5),(5,5),(6,5),(7,5)
(0,4),(1,4),(2,4),(3,4),(4,4),(5,4),(6,4),(7,4)
(0,3),(1,3),(2,3),(3,3),(4,3),(5,3),(6,3),(7,3)
(0,2),(1,2),(2,2),(3,2),(4,2),(5,2),(6,2),(7,2)
(0,1),(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1)
(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0),(7,0)

الحركات المتصورة للحصان هي ثمان حركات:

لو حللنا كل حركة للحصان تكون خطوتين ثم خطوة معامدة

تكون أسمائها كالتالي:

1- خطوتين فوق خطوة شمال ( +2,-1 )

2- خطوتين فوق خطوة يمين (+2, +1)

3- خطوتين يمين خطوة فوق (+1,+2)

4- خطوتين يمين خطوة تحت (-1, +2)

5- خطوتين تحت خطوة يمين

6- خطوتين تحت خطوة شمال

7- خطوتين شمال خطوة فوق

8- خطوتين شمال خطوة تحت

كذا يكون عندنا ثمان احتمالات لحركة الحصان

لو تركنا البرنامج بلا قيود راح يستمر يعمل الى ما لا نهاية

لذلك علينا أن نختبر الحركات، إذا كانت الخطوة صحيحة نأخذها بالاعتبار وإذا كانت خارج لوحة الشطرنج خلاص نلغي الخطوة ونلغي الاحتمال

كيف نعرف ان الخطوة صحيحة؟ لو حسبنا الخطوة وصار هكذا (-1, 8) تكون خطوة لا تحسب ( يعني بالسالب او فوق السبعة نستبعد الاحتمال)

- اللي معطى في السؤال أن الحصان في الزاوية السفلية اليمنى، هذا معناه لو اختبرنا احتمال الخطوة الاولى راح ينتج لنا طريقين فقط، ثم بعدها يتفرع لدينا من كل طريق خمس طرق ويصبح مجموع الطرق عشرة ثم تتضاعف بشكل كبير جدا

- يجب أن ينتهي البرنامج من تلقاء نفسه بعد أن يختبر جميع الاحتمالات

- نقوم بحساب الطريق أنه صحيح إذا تمكن الحصان من الوصول إلى (7,7)

لو كان عندنا ألف طريق مثلا: الحاسب يختبر جميع هذه الطرق وراح يكونوا أحد اثنين: طريق خاطئ، طريق صحيح

- نريد أن نضع قيد آخر: أن الحصان إذا مشى في طريق ونزل في عدة مربعات لا يسمح له أن يعود وينزل في مربع قد نزله سابقا

- أمر آخر ممكن حل البرنامج باستخدام الريكيرجن وممكن باستخدام اللوب

- بإمكانك تستخدم ستاك أو ممكن تستخدم لينكد ليست أو غيرها

بهذه الطريقة قمنا بتحويل المشكلة إلى صورة برمجية

وأريد من الجميع تطبيق الحل باستخدام أحد لغات البرمجة راح ينمي التفكير

اسئلة أخرى:

- ما هو أطول طريق للحل؟

- كم عدد الحلول الصحيحة؟

- كم طريق بعدد ست خطوات؟

- كم طريق بعدد سبع خطوات؟

كل هذه الاسئلة سيتضح حلها بعد تطبيق البرنامج

السلام عليكم ورحمة الله وبركاته

لقد قمت بعمل تعديل ليتناسب مع ايجاد الطرق الممكنة

حيث ان كل الطرق لا يمكن ايجادها حيث ان عدد الطرق والحلول يتزايد بشكل لانهائى

واعتقد ان الصورة والبرنامج بعد التعديل سيوضحان ذلك

وسوف اقوم بوضع الكود والخوارزمية عندما يسمح لى الاخ Delphawi بذلك

وذلك حتى يتسنى لباقى الاعضاء وضع بعض المحاولات

Chess Puzzle.rar

شكرا أخي بارع

شكرا اخي fmgret12

علي فكرة شرحك اخي بارع رااااااااااااااااااااااائع وأسلوبك واضح وبسيط ومتدرج في الشرح

لقد استوعبت منك بسهولة طريقة تحليلك للمعطيات والوصول الي أفضل الطرق الممكنة للوصول للنتائج المطلوبه

تحياتي لك ولأخي fmgret12 والذي ننتظر منه أيضا المزيد

بارك الله فيكم إخواني

السلام عليكم إخواني

جزاكم الله خيراً على المشاركة , وقد انتهيت تقريباً -الحمد لله بنسبة 99%- من وضع الخوارزمية , بقي شرحها وكتابة برنامج لتنفيذها ولكن بسبب اسبوعي امتحانات فللأسف سوف أتأخر في وضعهم .. إعذروني

أخي fmgret12 جزاك الله خيراً على المشاركة , لم أطلع على الكود بعد , لكن يبدو لي أن حلك يستغرق كثيراً من الوقت , تخيل لو انك معطى لوحة 1000*1000 فإنك ستسغرق وقتاً لا بأس به لإيجاد أقصر طريق

حاول استثناء بعض الحلول لتزيد من السرعة .

قمت بكتابة كود لحل المسألة، الكود ليس طويلا عشرين سطر تقريبا

بعدما نفذت الكود، لم ينتهي التنفيذ استغربت توقعت ان هناك خلل في الكود، راجعت الكود مرة اخرى أشعر انه سليم

بعدها قلت ممكن المشكلة تحتاج زمن طويل،

قمت بتوقيف البرنامج وصغرت طاولة الشطرنج وجعلتها ثلاثة في ثلاثة غيرت 7*7 وجعلتها 3*3

بعدما نفذت الكود طبع لي التالي:

good paths:2

bad paths:0

جربت على 4*4

good paths:138

Bad paths :2798

قلت الكود سليم أجل سأكبر الطاولة وجعلتها 5*5

عملت رن للكود، تأخر قليلا ثم طبع لي:

Bad paths:3262152

good paths:88920

جلس الكود 24 ثانية

جعلت الطاولة 6*6 وشغلت الكود، تأخر جدا وانتظرته ساعتين ثم مللت وأغلقته

قلت أصغر شوي بين 5*5 و 6*6 جربت أجعل الطاولة 6*5 وعملت رن وتأخر طويلا لكنه انتهى والوقت المستغرق 27 دقيقة

Bad paths:198956851

good paths:4192272

لم يخطر على بالي ان المشكلة تحتاج هذا الوقت الخرافي، لكنه رياضيا يوجد ملايين الاحتمالات

هذا الحصان ماكر لديه ملايين الاحتمالات على هذه الطاولة الصغيرة

إذا سمح الأخ دلفاوي سأضع الكود هو صاحب السؤال وهو المسؤول عن سير الموضوع

ممم حسناً أخ بارع و fmgret12 يمكنكم وضع محاولاتكم , سأحاول مناقشتها معكم إلى أن انتهي من كتابة وشرح الخوارزمية والكود

بالطبع طريقة الحساب التي اقترحتموها صحيحة , لكنها غير مناسبة بالطبع , والسبب أنها تختبر كل الطرق ..

بالمناسبة هذه الطريقة تسمى BruteForce , وتكون مفيدة جداً في بعض المشاكل (التي لا تستغرق وقتاً طويلاً) لأن الحل الذي تنتجه يكون غالباً صحيح 100% , لذا تستخدم للتحقق من صحة الخوارزميات الأسرع منها .

والسلام عليكم

فكرة اللغز والذي يتم حله بخوارزمة ، عبقرية فعلا أخي Delphawi

+1

انا شغوف لمتابعة تلك المناقشات وفي انتظار ان تكتب الخوارزمة الصحيحة للحل

هذا الحل مكتوب بلغة Scala

وهو يعرض جميع الحلول الصحيحة للحصان وهذا لا يتم إلا باختبار جميع الطرق.

البرنامج هذا يقوم بإيجاد جميع الحلول الصحيحة للحصان

أما إذا كان المطلوب هو إيجاد أقصر الطرق فقط وليس جميع الحلول، فالموضوع يختلف ونحتاج إلى طرق أخرى أسرع

من الطرق استخدام نفس الكود بالأعلى مع تطبيق Breadh-First Search يعني البحث العرضي أو البحث مرحلة مرحلة توضحها الصورة التالية:

نبحث الأرزق إذا لم نجد حل نبحث الأحمر إذا لم نجد حل ننتقل للاصفر وهكذا حتى نجد الحل

صورة أخرى توضح الترتيب بالارقام

بهذه الطريقة نجد أقصر الحلول بشكل أسرع

هذه أحد الطرق ويوجد طرق أسرع، ننتظر أخينا دلفاوي يوضحها

.

Program.txt

يمكن أن نطبق أحد خوارزميات الأمثلية على اللغز مثل الخوارزمية الجينية GA وخوارزمية مستعمرة النمل ACO ؟

ما هو رأيكم أخواني ... وبذلك نختصر وقت المعالجة الكبير؟

icedragon كتب:

يمكن أن نطبق أحد خوارزميات الأمثلية على اللغز مثل الخوارزمية الجينية GA وخوارزمية مستعمرة النمل ACO ؟

ما هو رأيكم أخواني ... وبذلك نختصر وقت المعالجة الكبير؟

هذه المشكلة تصنف أنها من نوع الـ Pathfinding

أشهر الخوارزميات للـ Pathfinding

- خوارزمية ايه ستار *A

- وخوارزمية ديجكسترا Dijkstra's algorithm

صورة توضح خوازمية ايه ستار من ويكيبيديا

للتوسع، الموضوع في ويكيبيديا: Pathfinding

رائع أخ بارع ,

والمطلوب هو إبجاد أقصر طريق كما ذكرت , وغالباً سيكون العمل على لوحة كبيرة إن شاء الله :P

الحقيقة فكرت في A* , لكن لم يكن لدي وقت لدراستها والتدرب عليها (لا أحب استخدام أكواد جاهزة تشرحها)

بالنسبة لطريقة Breadh-First Search فأعتقد أني طبقت جزءاً منها دون علم بالطريقة إلا الآن :)

شكراً أخ iceDragon على الاقتراح , الحقيقة لم أتعامل مع هذه الخوارزميات بشكل جدي , إن شاء الله سأحاول القراءة عنهم لإيجاد طرق أفضل

شكرا على المعلومات المفيدة أخ بارع ...

أظن أنه يمكن تطبيق خوارزمية مختلطة بحيث نقوم بتوليد المجمتع الأولي من خلال الخوارزمية الجينية ومن ثم تحسين الحل للوصول للحلول المثلى باستخدام خوارزمية النمل

لكن ما مدى جودة الحل مقارنة بالخوارزميات التي ذكرتها ... لا فكرة لدي ... مع اني مقتنع جدا بتطبيق حلي

ان شاء الله سأقوم بمحاولة تطبيق الحل ... ولي عودة بإذن الله

السلام عليكم ورحمة الله وبركاته

بالنسبة للكود والخوارزمية فهو مكتوب بلغة فيجوال بيسك 6

وانا شغوف ايضا بمعرفة الخورازمية الافضل لاننى غير مقتنع تماما بهذه الخورازمية

Dim co As New Collection
Dim s, d As String
Dim x, y, x1, y1, sx, sy As Double
Private Sub cmd_clear_Click()
lbl_result.Caption = ""
txt_Less.Text = 1
End Sub

Private Sub cmd_find_Click()
lst_done.Clear
lbl_result.Caption = ""
co.Add "A1"
Do While lst_done.ListCount < 1
For q = 1 To co.Count
s = co.Item(q)
co.Remove (q)
    x = Asc(Right(s, 2)) - 64
    y = Asc(Right(s, 1)) - 48
    If x <> Val(txt_n) And y <> Val(txt_n) Then
        For i = 1 To 8
            x1 = Choose(i, 2, 2, -2, -2, 1, -1, 1, -1)
            y1 = Choose(i, 1, -1, 1, -1, 2, 2, -2, -2)
            sx = x + x1
            sy = y + y1
                If sx >= 1 And sx <= Val(txt_n) And sy >= 1 And sy <= Val(txt_n) Then
                    d = Chr(sx + 64) & sy
                    d = s & "  " & d
                    co.Add (d)
                    If sx = Val(txt_n) And sy = Val(txt_n) Then
                        lst_done.AddItem co.Item(co.Count)
                    End If
                End If
        Next i
    End If
Next q
Loop
lbl_result.Caption = lst_done.ListCount
txt_Less.Text = lbl_result.Caption + 1
Set co = Nothing
End Sub

فى انتظار اخى Delphawi للخورازمية الجديدة