Knight’s Tour brute force algorithm example

(From Wikipedia) The Knight’s Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight’s tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open.

Just developed my brute-force algorithm implementation, using GLib and based on a simple recursive function.

Download and try it here!

As an example of result, this is the open Knight’s Tour found by the algorithm in a 5×5 board, starting from position [0,0]:
[0,0][1,2][2,4][4,3][3,1][1,0][2,2][0,3][1,1][3,0][4,2][3,4][1,3][0,1][2,0][4,1][3,3][1,4][0,2][2,1][4,0][3,2][4,4][2,3][0,4]

And this one, the first Knight’s Tour found by the algorithm in a 8×8 board, starting from position [0,0]:
[0,0][1,2][2,4][3,6][5,7][7,6][6,4][7,2][6,0][4,1][5,3][6,5][7,7][5,6][7,5][6,3][7,1][5,0][6,2][7,4][5,5][6,7][4,6][5,4][6,6][4,5][3,3][5,2][7,3][6,1][4,0][2,1][4,2][3,0][1,1][0,3][2,2][0,1][2,0][3,2][4,4][2,3][0,4][1,6][3,7][2,5][1,7][0,5][1,3][3,4][1,5][0,7][2,6][4,7][3,5][2,7][0,6][1,4][0,2][1,0][3,1][4,3][5,1][7,0]

Both examples above show open Knight’s Tours.

Posted on January 13, 2010, in Development and tagged , . Bookmark the permalink. 1 Comment.

  1. u did a great job.n it is realy simple solve using u r algo…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: