കുതിര സഞ്ചാരം
ചെസ്സ് പലകയിലെ കുതിരയെ അടിസ്ഥാനമാക്കിയ ഒരു ഗണിതശാസ്ത്രപ്രശ്നമാണ്‌ കുതിര സഞ്ചാരം (Knight's tour). ഒഴിഞ്ഞ ചെസ്സ് പലകയിൽ ഒരു കുതിരയെ വെക്കുകയും, ചെസ്സിലെ നിയമങ്ങളനുസരിച്ച് പലകയിലെ എല്ലാ കളങ്ങളിലും ഒരിക്കൽ മാത്രം ചാടിക്കണമെന്നതുമാണ്‌ പ്രശ്നം. കുതിരയുടെ സഞ്ചാരം തുടങ്ങിയേടത്തു തന്നെ അവസാനിക്കുകയാണെങ്കിൽ അതിനെ അടഞ്ഞ സഞ്ചാരം (Closed tour) എന്നു വിളിക്കുന്നു. അങ്ങനെയാകുന്നില്ലെങ്കിൽ അതിനെ തുറന്ന സഞ്ചാരം (Open tour) എന്നും വിളിക്കുന്നു. ആകെ ലഭ്യമായ തുറന്ന സഞ്ചാരങ്ങളുടെ എണ്ണം ഇന്നും അജ്ഞാതമാണ്‌. കുതിര സഞ്ചാര പ്രശ്നം പരിഹരിക്കുന്ന പ്രോഗ്രാം എഴുതുന്ന ചോദ്യം കമ്പ്യൂട്ടർ ശാസ്ത്ര വിദ്യാർത്ഥികൾക്കു സാധാരണയായി ലഭിക്കുന്ന ചോദ്യങ്ങളിലൊന്നാണ്[1]. വിവിധ രീതിയിലുള്ള ചെസ്സ് പലകകളുപയോഗിച്ച് ഈ പ്രശ്നം ചെയ്യാറുണ്ട്. 8 × 8 എന്ന സാധാരണ ചെസ്സ് പലകക്കു പുറമെ മറ്റു പല രീതിയിലുള്ള ചെസ്സ് പലകകളിലും ഇത് ചെയ്യാറുണ്ട്.
 കുതിര സഞ്ചാര പ്രശ്നത്തിന്റെ ഒരു അനിമേഷൻ |
 Knight's graph showing all possible paths for a Knight's tour on a standard 8×8 chessboard. The numbers on each node indicate the number of possible moves that can be made from that position. |
 The Knight's tour as solved by The Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can be completed from any point on the board. |
സിദ്ധാന്തംതിരുത്തുക
ഗ്രാഫ് സിദ്ധാന്തത്തിലെ ഹാമിൽട്ടോണിയൻ പാത പ്രശ്നത്തിന്റെ ഒരു ഉദാഹരണമാണ് കുതിര സഞ്ചാരം. അടഞ്ഞ സഞ്ചാരത്തിന്റെ നിർദ്ധാരണത്തിലെത്തുന്നത് ഹാമിൽട്ടോണിയൻ ചക്ര പ്രശ്നത്തിന്റെ ഒരു ഉദാഹരണവുമാണ്‌. പക്ഷേ, ഹാമിൽട്ടോണിയൻ പാത പ്രശ്നത്തിനു വിപരീതമായി ഇവിടെ പ്രശ്നത്തിന്റെ നിർദ്ധാരണം ലീനിയർ ടെമിൽ[2] ചെയ്യാൻ സാദ്ധ്യമാണ്.
ചരിത്രംതിരുത്തുക
കുതിര സഞ്ചാര പ്രശ്നത്തിന്റെ ആദ്യ പ്രതിപാദ്യമുള്ളത് ഒമ്പതാം നൂറ്റാണ്ടിൽ ജീവിച്ചിരുന്ന കാശ്മീരി കവിയായ രുദ്രടൻ എഴുതിയ കാവ്യാലങ്കാര[3] എന്ന ഗ്രന്ഥത്തിലെ ഒരു ശ്ലോകത്തിലാണ്‌.
അവലംബംതിരുത്തുക
- ↑ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326-328. 2003.
- ↑ A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discrete Applied Math, volume 50, no.2, pp.125-134. 1994.
- ↑ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhi: Parimal Sanskrit Series No. 30.
പുറമെ നിന്നുള്ള കണ്ണികൾതിരുത്തുക
- Richard W. Henderson, Eugene Roger Apodaca A Knight of Egodeth: Zen Raptured Quietude, 240 Solutions to the Knights Tour in form of Game Book
- Warnsdorff's Rule and its efficiency from Warnsdorff's Rule Web Page
- Mario Velucchi The ultimate Knight's Tour page of Links
- The knight's tour
- Knight's tour notes
- Sloane's Integer Sequence
A001230 - Preprint of Pohl's paper (freely accessible)
- SilverKnight - online knight's tour game
ഉത്തരങ്ങൾതിരുത്തുക
- The Knight's Tour by Jay Warendorff, Wolfram Demonstrations Project
- A Simple backtracking implementation in C++
- An implementation in C#
- Knight's Tours Using a Neural Network Program that creates tours using a neural network, plus gallery of images.
[[Category:ചെസ്സ്]