Traveling Chess Salesman
Problem 15 Division I 19 Points
Problem Statement
A wee time ago, there once lived a Scottish chess salesman who used to offer a free chess set to any potential customer who could move the Knight piece around the board in the minimum number of moves and land on every square. There were three simple rules. One, the Knight had to start in the Queen's Knight position. Two, no other pieces were on the board. And three, each square could be landed on multiple times, but each move had to count. Of course, the customer would have to agree to buy a chess set if they could not match the salesman's best effort of 63 moves. Legend has it that this chess salesman used to chant the following Lyric before the challenge began:
Knight K can move to any space denoted by an X

   In days of old when Knights were bold,
   And the game was invented,
   The Knight was alone when he went off to course,
   And had to be contented.

   Without any clues, in how little moves,
   Could a Knight cover her Lord's green?
   You've got to make her cover every acre,
   And be certain of where's She's been.

Program Input
The program should model an 8x8 chessboard and a single Knight starting in the top row. The Knight may move horizontally two spaces and vertically one space, or vertically two spaces and horizontally one space, as shown in the diagram above. PROG15.IN contains a single number (1-8) indicating the column of the Knight's starting position.
Program Output
The program must write to PROG15.OUT an 8x8 matrix of numbers 1-64 indicating the jumps the Knight makes to cover the entire chessboard. The numbers indicate the Knight's jump (or move) sequence along the path, and they must line up in 8 rows and 8 columns. The example shows the first 13 moves for one possible solution:
09 -- 03 -- 07 -- 01 --
04 -- 08 -- 02 -- -- --
-- 10 -- 06 -- 12 -- --
-- 05 -- 11 -- -- -- 13
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --
-- -- -- -- -- -- -- --