Find solution to knight's tour

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I'm wondering if the closed knight's tour below is solveable. The 8 x 8 board set up as follows:

63g	62	61	60d	59	58	57	56
55	54e	53	52	51	50	49	48
47	46	45	44	43	42	41	40
39	38	37	36h	35	34L	33	32k
31i	30	29	28	27	26	25	24
23	22	21	20	19	18	17	16
15	14	13	12	11f	10	9a	8
7c	6	5	4	3b	2	1	0j

The letters are added to indicate the checkpoints. You start at square 56 and must reach the checkpoints as follows:

9a -> after 3 moves (excluding the preset move of at 56)
3b -> after 4 moves
7c -> after 8 moves
60d -> after 12 moves
54e -> after 13 moves
11f -> after 23 moves
63g -> after 31 moves
36h -> after 33 moves
31i -> after 35 moves
0j  -> after 39 moves
32k -> after 43 moves
34L -> after 53 moves

I'm curious to learn how to solve it, and whether or not writing a program to seek the solution is a must.

I look forward to suggestions or code to solve the puzzle.

Many thanks for reading :)

Comment on Find solution to knight's tour

Replies are listed 'Best First'.
Re: Find solution to knight's tour by McDarren (Abbot) on May 31, 2007 at 19:02 UTC
About two minutes of googling came up with this link, which would seem to give you all the information you need to get started. --Darren	[reply]
Re: Find solution to knight's tour by MidLifeXis (Monsignor) on May 31, 2007 at 18:53 UTC
AM, this is a common problem in computer science literature, and would be an appropriate level for a ~~introductory~~ CS course at the end of a semester. Please show some work you have done to indicate that you have shown some effort, and are not just looking to have someone else do your homework for you. If this is not the case, my apologies in advance. Timing and wording are very "student"ish. You may want to look at topics for recursion, spanning tree, game theory, travelling salesman problem, or NP-Complete for ideas on solving this problem. Update 1: remove introductory Update 2: Add places to look for solutions --MidLifeXis	[reply]
Re: Find solution to knight's tour by kyle (Abbot) on May 31, 2007 at 18:59 UTC
There's a similar puzzle considered in the thread "How to debug a long while loop", so maybe that would help.	[reply]
Re: Find solution to knight's tour by ikegami (Patriarch) on May 31, 2007 at 20:54 UTC
There's a post on this site which shows how to solve it using the regexp engine. If you wish to warp your brain, it's a must read :) I'd link to it but I must leave in a hurry.	[reply]
Re: Find solution to knight's tour by blazar (Canon) on May 31, 2007 at 22:41 UTC
Wikipedia has it and that may be a good starting point. If you follow the links you'll find algorithms and implementations in some languages. Porting them to Perl should be a good exercise for you.	[reply]
Re: Find solution to knight's tour by robot_tourist (Hermit) on Jun 01, 2007 at 13:06 UTC
a bit of recursive backtracking might work. My CS lecturer didn't require checkpoints. IIRC my (java) solution worked for board sizes up to 6x6, then took too long (or crashed) for 7x7, but worked for 8x8. I never bothered to find out why. Although I may be getting confused with the killer queens puzzle. I should really have a look at both again in perl. How can you feel when you're made of steel? I am made of steel. I am the Robot Tourist. Robot Tourist, by Ten Benson	[reply]
Re^2: Find solution to knight's tour by moklevat (Priest) on Aug 27, 2007 at 19:47 UTC
I realize this post is old, but I just came across it and wanted to post a reply in case someone else came across it and wondered why your 7x7 board did not work. For m x m boards, there is no closed tour when m is odd.	[reply]