കുതിര സഞ്ചാരം

  കുതിര സഞ്ചാരം

ചെസ്സ് പലകയിലെ കുതിരയെ അടിസ്ഥാനമാക്കിയ ഒരു ഗണിതശാസ്ത്രപ്രശ്നമാണ്‌ കുതിര സഞ്ചാരം (Knight's tour). ഒഴിഞ്ഞ ചെസ്സ് പലകയിൽ ഒരു കുതിരയെ വെക്കുകയും, ചെസ്സിലെ നിയമങ്ങളനുസരിച്ച് പലകയിലെ എല്ലാ കളങ്ങളിലും ഒരിക്കൽ മാത്രം ചാടിക്കണമെന്നതുമാണ്‌ പ്രശ്നം. കുതിരയുടെ സഞ്ചാരം തുടങ്ങിയേടത്തു തന്നെ അവസാനിക്കുകയാണെങ്കിൽ അതിനെ അടഞ്ഞ സഞ്ചാരം(Closed tour) എന്നു വിളിക്കുന്നു. അങ്ങനെയാകുന്നില്ലെങ്കിൽ അതിനെ തുറന്ന സഞ്ചാരം(Open tour) എന്നും വിളിക്കുന്നു. ആകെ ലഭ്യമായ തുറന്ന സഞ്ചാരങ്ങളുടെ എണ്ണം ഇന്നും അജ്ഞാതമാണ്‌. കുതിര സഞ്ചാര പ്രശ്നം പരിഹരിക്കുന്ന പ്രോഗ്രാം എഴുതുന്ന ചോദ്യം കമ്പ്യൂട്ടർ ശാസ്ത്ര വിദ്യാർത്ഥികൾക്കു സാധാരണയായി ലഭിക്കുന്ന ചോദ്യങ്ങളിലൊന്നാണ്‌. വിവിധ രീതിയിലുള്ള ചെസ്സ് പലകകളുപയോഗിച്ച് ഈ പ്രശ്നം ചെയ്യാറുണ്ട്. 8 × 8 എന്ന സാധാരണ ചെസ്സ് പലകക്കു പുറമെ മറ്റു പല രീതിയിലുള്ള ചെസ്സ് പലകകളിലും ഇത് ചെയ്യാറുണ്ട്.

  സിദ്ധാന്തം

ഗ്രാഫ് സിദ്ധാന്തത്തിലെ ഹാമിൽട്ടോണിയൻ പാത പ്രശ്നത്തിന്റെ ഒരു ഉദാഹരണമാണ് കുതിര സഞ്ചാരം‌. അടഞ്ഞ സഞ്ചാരത്തിന്റെ നിർദ്ധാരണത്തിലെത്തുന്നത് ഹാമിൽട്ടോണിയൻ ചക്ര പ്രശ്നത്തിന്റെ ഒരു ഉദാഹരണവുമാണ്‌. പക്ഷേ, ഹാമിൽട്ടോണിയൻ പാത പ്രശ്നത്തിനു വിപരീതമായി ഇവിടെ പ്രശ്നത്തിന്റെ നിർദ്ധാരണം ലീനിയർ ടെമിൽ ചെയ്യാൻ സാദ്ധ്യമാണ്.

  ചരിത്രം

കുതിര സഞ്ചാര പ്രശ്നത്തിന്റെ ആദ്യ പ്രതിപാദ്യമുള്ളത് ഒമ്പതാം നൂറ്റാണ്ടിൽ ജീവിച്ചിരുന്ന കാശ്മീരി കവിയായ രുദ്രടൻ എഴുതിയ കാവ്യാലങ്കാര എന്ന ഗ്രന്ഥത്തിലെ ഒരു ശ്ലോകത്തിലാണ്‌.