Programming Challenge 35 - Knight's Tour

Deadline May 31 2010

By David Bolton, About.com Guide

See More About:

A Knight's moves

This challenge is about programming a Knight piece in chess to do a complete visit to every square on a 20 x 20 chessboard but only visiting each square once. This is called the Knight's Tour. The fastest calculation and output of the 400 squares wins.

Knight Moves in Chess

A knight moves to the opposite corner of a 3 x 2 section. I.e. 2 horizontally and 1 vertically or 2 vertically and 1 horizontally. The first image above shows the 8 possible squares that the piece can move to.

The board for this challenge is 400 squares in size 20 x 20 and the Knight starts in the top left hand square. Squares are numbered from 1 in the top left to 400 in the bottom rigt so 20 is the top right square, 381 in the bottom left.

In the 2nd picture you can see that the Knight have two moves to start with, to squares 23 and 42. From those two squares there are many moves. I've highlighted a few (5,45, 64, 83 and 81) but a Knight on 23 could also move to 41 or 62 and on 42 could move to 3 or 24.

Note. Some knight's tours require the Knight to finish one move away from the starting position. That isn't true here.

The Output

Output a file output.txt in the same location as your exe. It should contain 401 lines with each line after the first holding just 1 move. The first line should be the average time taken (see below) the 2nd should have 1, the 3rd either 23 or 42 and so on. No number should ever be repeated else it means your knight has visited the same square twice or more!

Format

Average Time = 1.2345 secs 1
23

Timing Code

Please time from the start of the calculation until just before the output file is opened for writing then output the time taken as the very first line of the output file. If your code is very fast then repeat it in a loop enough times so the total elapsed time is between 1 and 5 seconds. If your program did 500 iterations in 2 seconds then the average time would be 2/500 secs.

Final Results

A very close finish. Thanks to all seven who entered and commiserations to Gaurav who was just pipped by Tiaan who hedged his bets entering both C# and C++ entries. Also a special mention to Tiaan for generating a png of his moves!

Tiaan Geldenhuys (Canada) Link- C++ Time(secs) = 0.0000135748
Gaurav Sarode (USA, 26) - C++ Time(secs) = 0.000038
Tiaan Geldenhuys (Canada) - C# Time(secs) = 0.00004271
Jeremy Nicklas (USA, 28) - C++ Time(secs) = 0.0000678987
Reid & Jeff (USA, 22) - C++ Time(secs) = 0.0021954
Ehsan Khakifirooz (IRAN, 24) - C# Time(secs) = 0.00239
Sean Jordan (USA, 22) Link - C++ Time(secs) = 0.00273168

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Challenge 35 email address with the subject line Programming Challenge 35.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is May 31 2010.

The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.