جولة الفارس

جولة الفارس هي سلسلة من تحركات الفارس على رقعة الشطرنج بحيث يزور كل مربع مرة واحدة فقط. إذا انتهى الفارس في مربع يبعد حركة فارس واحدة عن مربع البداية (بحيث يمكنه العودة إلى الرقعة فورًا باتباع المسار نفسه)، تُسمى الجولة "مغلقة" أو "مُعادية"؛ وإلا فهي "مفتوحة". ^{[ 1 ] [ 2 ]}

مسألة مسار الفارس هي المسألة الرياضية المتعلقة بإيجاد مسار الفارس. ويُعدّ إنشاء برنامج لإيجاد مسار الفارس مسألة شائعة تُطرح على طلاب علوم الحاسوب . ^{[ 3 ]} تتضمن تنويعات مسألة مسار الفارس استخدام رقع شطرنج بأحجام مختلفة عن الحجم المعتاد 8 × 8 ، بالإضافة إلى رقع غير منتظمة (غير مستطيلة).

تُعدّ مسألة جولة الفارس مثالاً على مسألة المسار الهاميلتوني الأكثر عمومية في نظرية المخططات . وبالمثل، تُعدّ مسألة إيجاد جولة فارس مغلقة مثالاً على مسألة الدورة الهاميلتونية . وعلى عكس مسألة المسار الهاميلتوني العامة، يمكن حلّ مسألة جولة الفارس في زمن خطي . ^{[ 4 ]}

يعود أقدم ذكر معروف لمسألة جولة الفارس إلى القرن التاسع الميلادي. ففي كتاب رودراتا " كافيالانكارا" ^{[ 6 ]} (5.15)، وهو عمل سنسكريتي في فن الشعر، عُرض نمط جولة الفارس على نصف رقعة الشطرنج كشكل شعري مُفصّل ( citra-alaṅkāra ) يُسمى " تورغاباداباندها " أو "ترتيب خطوات الحصان". ويمكن قراءة البيت الشعري نفسه، المُكوّن من أربعة أسطر، كل سطر منها ثمانية مقاطع، من اليسار إلى اليمين أو باتباع مسار الفارس في جولته. ولأن أنظمة الكتابة الهندية المُستخدمة في السنسكريتية مقطعية، يُمكن اعتبار كل مقطع بمثابة مربع على رقعة الشطرنج. وفيما يلي مثال رودراتا:

ترجمة صوتية:

على سبيل المثال، يمكن قراءة السطر الأول من اليسار إلى اليمين أو عن طريق الانتقال من المربع الأول إلى السطر الثاني، المقطع الثالث (2.3) ثم إلى 1.5 إلى 2.7 إلى 4.8 إلى 3.6 إلى 4.4 إلى 3.2.

قام الشاعر والفيلسوف فيدانتا ديسيكا ، من أتباع مذهب سري فايشنافا ، خلال القرن الرابع عشر، في ملحمته الضخمة المكونة من 1008 أبيات، والتي يمدح فيها صندل الإله رانغاناثا الإلهي في سريرانغام ، بادوكا ساهاسرام (في الفصل 30: تشيترا باداتي )، بتأليف بيتين متتاليين باللغة السنسكريتية ، كل منهما مكون من 32 حرفًا (على وزن أنوشتوبه ). ويمكن اشتقاق البيت الثاني من البيت الأول من خلال تنفيذ جولة الفارس على رقعة لعب 4 × 8 ، بدءًا من الزاوية العلوية اليسرى. ^{[ 7 ]} البيت التاسع عشر بعد نقله صوتيًا هو كما يلي:

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

sThi thA sa ma ya rA ja thpA

ga tha rA mA dha ke ga vi |

dhu ran ha sAm sa nna thA dhA

sA dhyA thA pa ka rA sa rA ||

يُعتقد أن ديسيكا قد ألف جميع الأبيات الـ 1008 (بما في ذلك بيت تشاتورانغا تورانغا باداباندام الخاص المذكور أعلاه) في ليلة واحدة كتحدٍ. ^{[ 8 ]}

تصف إحدى الجولات المذكورة في الكتاب الخامس من "بهاغافانتاباسكارابي" لبهات نيلاكانثا، وهو عمل موسوعي باللغة السنسكريتية يتناول الطقوس والقانون والسياسة، كُتب إما حوالي عام 1600 أو حوالي عام 1700، ثلاث جولات للفرسان. لا تقتصر هذه الجولات على كونها دائرية فحسب، بل هي متناظرة أيضًا، وتستند الأبيات الشعرية إلى الجولة نفسها، بدءًا من مربعات مختلفة. ^{[ 9 ]} يُعد عمل نيلاكانثا إنجازًا استثنائيًا لكونه جولة مغلقة متناظرة تمامًا، تسبق عمل أويلر (1759) بما لا يقل عن 60 عامًا.

بعد نيلاكانثا، كان ليونارد أويلر من أوائل علماء الرياضيات الذين درسوا مسار الفارس . وكانت قاعدة وارنسدورف، التي وصفها لأول مرة إتش سي فون وارنسدورف عام 1823، هي أول طريقة لإتمام مسار الفارس.

في القرن العشرين، استخدمت جماعة أوليبو من الكتاب هذا الأسلوب، إلى جانب العديد من الجماعات الأخرى. ومن أبرز الأمثلة على ذلك جولة الفارس 10 × 10 التي تحدد ترتيب فصول رواية جورج بيريك " الحياة: دليل المستخدم" .

شهدت المباراة السادسة من بطولة العالم للشطرنج 2010 بين فيسواناثان أناند وفيسيلين توبالوف قيام أناند بـ 13 نقلة متتالية للحصان (على الرغم من استخدامه كلا الحصانين)؛ وقد سخر المعلقون عبر الإنترنت من أن أناند كان يحاول حل مشكلة جولة الحصان أثناء المباراة.

أثبت شوينك ^{[ 11 ]} أنه بالنسبة لأي رقعة m × n حيث m ≤ n ، فإن جولة الفارس المغلقة ممكنة دائمًا ما لم يتم استيفاء شرط واحد أو أكثر من هذه الشروط الثلاثة:

1. m و n كلاهما فرديان
2. م = 1 أو 2 أو 4
3. m = 3 و n = 4 أو 6 أو 8.

أثبت كلٌّ من كول وآخرون وكونراد وآخرون أنه على أي رقعة مستطيلة لا يقل بُعدها الأصغر عن 5، توجد جولة فارس (قد تكون مفتوحة). ^{[ 4 ] [ 12 ]} بالنسبة لأي رقعة m × n حيث m ≤ n ، تكون جولة الفارس (قد تكون مفتوحة) ممكنة دائمًا ما لم يتحقق شرط واحد أو أكثر من الشروط الثلاثة التالية:

1. م = 1 أو 2
2. m = 3 و n = 3 أو 5 أو 6 ^{[ 13 ]}
3. m = 4 و n = 4. ^{[ 14 ]}

على لوحة 8 × 8 ، يوجد بالضبط 26,534,728,821,064 مسارًا مغلقًا موجهًا (أي يتم حساب مسارين على نفس الطريق يسيران في اتجاهين متعاكسين بشكل منفصل، وكذلك الدوران والانعكاس ). ^{[ 15 ] [ 16 ] [ 17 ]} عدد المسارات المغلقة غير الموجهة هو نصف هذا العدد، حيث يمكن تتبع كل مسار في الاتجاه المعاكس. يوجد 9,862 مسارًا مغلقًا غير موجه على لوحة 6 × 6. ^{[ 18 ]}

توجد عدة طرق لإيجاد مسار الحصان على رقعة معينة باستخدام الحاسوب. بعض هذه الطرق عبارة عن خوارزميات ، بينما البعض الآخر عبارة عن طرق استدلالية .

قاعدة وارنسدورف

	أ	ب	ج	د	هـ	و	ز	ح
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	أ	ب	ج	د	هـ	و	ز	ح

تمثيل بياني لقاعدة وارنسدورف. يحتوي كل مربع على عدد صحيح يمثل عدد الحركات التي يمكن للحصان القيام بها من ذلك المربع. في هذه الحالة، تنص القاعدة على الانتقال إلى المربع ذي أصغر عدد صحيح، وهو 2.

قاعدة وارنسدورف هي طريقة استدلالية لإيجاد مسار الفارس. يُحرَّك الفارس بحيث يتجه دائمًا إلى المربع الذي يتطلب منه أقل عدد من الحركات اللاحقة. عند حساب عدد الحركات اللاحقة لكل مربع مرشح، لا تُحتسب الحركات التي تعيد زيارة أي مربع سبق زيارته. من الممكن وجود خيارين أو أكثر يتساوى فيها عدد الحركات اللاحقة؛ وهناك طرق مختلفة لكسر هذا التعادل، منها طريقة ابتكرها بول ^{[ 21 ]} وأخرى ابتكرها سكويرل وكول ^{[ 22 ] .}

يمكن تطبيق هذه القاعدة بشكل أعم على أي رسم بياني. من منظور نظرية الرسوم البيانية، تُجرى كل حركة إلى الرأس المجاور ذي الدرجة الأقل . ^{[ 23 ]} على الرغم من أن مسألة مسار هاميلتون تُصنف عمومًا ضمن مسائل NP-hard ، إلا أن هذه الطريقة الاستدلالية قادرة على إيجاد حل في وقت خطي على العديد من الرسوم البيانية الشائعة . ^{[ 21 ]} تُعد جولة الفارس حالة خاصة من هذا القبيل. ^{[ 24 ]}

تم وصف الاستدلال لأول مرة في "Des Rösselsprungs einfachste und allgemeinste Lösung" بواسطة HC von Warnsdorff في عام 1823. ^{[ 24 ]}

قام جوردون هورسينجتون بكتابة برنامج حاسوبي يجد مسار الفارس لأي وضعية بداية باستخدام قاعدة وارنسدورف، ونُشر في عام 1984 في كتاب Century/Acorn User Book of Computer Puzzles . ^{[ 25 ]}

حلول الشبكات العصبية

تُعدّ مسألة جولة الفارس قابلةً للحلّ باستخدام الشبكات العصبية . ^{[ 26 ]} تُصمّم الشبكة بحيث يُمثّل كلّ نقلة قانونية للفارس بعصبون ، ويُهيّأ كلّ عصبون عشوائيًا ليكون إمّا "نشطًا" أو "غير نشط" (قيمة 1 أو 0)، حيث تشير القيمة 1 إلى أنّ العصبون جزء من الحلّ. كما يمتلك كلّ عصبون دالة حالة (موصوفة أدناه) تُهيّأ قيمتها إلى 0.

عندما يُسمح للشبكة بالعمل، يمكن لكل عصبون تغيير حالته ومخرجاته بناءً على حالات ومخرجات جيرانه (الذين يبعدون عنه مسافة حركة فارس واحدة بالضبط) وفقًا لقواعد الانتقال التالية:

$${\displaystyle U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)}$$

$${\displaystyle V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{إذا كان}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{إذا كان}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{فيما عدا ذلك}},\end{array}}\right.}$$

أين${\displaystyle t}$يمثل فترات زمنية منفصلة،${\displaystyle U(N_{i,j})}$هي حالة العصبون الذي يربط المربع${\displaystyle i}$إلى مربع${\displaystyle j}$،${\displaystyle V(N_{i,j})}$هو ناتج الخلية العصبية من${\displaystyle i}$ل${\displaystyle j}$، و${\displaystyle G(N_{i,j})}$هي مجموعة جيران الخلية العصبية.

على الرغم من إمكانية وجود حالات متباينة، إلا أنه ينبغي أن تتقارب الشبكة في النهاية، وهو ما يحدث عندما لا يغير أي عصبون حالته من وقت لآخر.${\displaystyle t}$ل${\displaystyle t+1}$عندما تتقارب الشبكة، فإنها إما تشفر جولة الفارس أو سلسلة من دائرتين مستقلتين أو أكثر داخل نفس اللوحة.

• أبو بكر بن يحيى السولي
• لغز الملكات الثماني
• جورج كولتانوفسكي
• أطول مسار فارس لم يُقطع
• المشي المتجنب للذات

• الوسائط المتعلقة بجولات نايتس على ويكيميديا ​​كومنز
• تسلسل OEIS A001230 (عدد جولات الفارس المغلقة غير الموجهة على رقعة شطرنج 2n × 2n)
• تسلسل OEIS A390833 (عدد مسارات هاميلتونية غير موجهة على الرسم البياني k X n knight)
• HC von Warnsdorff 1823 في كتب جوجل
• مقدمة عن جولات نايت بقلم جورج جيليس
• ملاحظات جولة الفارس بقلم جورج جيليس
• فيليب، أنيش (2013). "خوارزمية جولة الفارس الزائفة المعممة لتشفير الصور". مجلة IEEE Potentials ، 32 (6): 10-16 . Bibcode : 2013IPot...32f..10P . doi : 10.1109/MPOT.2012.2219651 . S2CID 39213422 .