kwartzlab makerspace

Feb
20

Chess Pathfinder

By

Yesterday I was presented with an interesting problem. The task was this: write a program that can move a knight from an arbitrary position on a 10×10 chess board (yes, I know they’re usually 8×8) so that it would move to every square on the board but never hit the same position twice.

The idea I had was to have a two-dimensional array of integers, initialized to values of zero, representing the board. A recursive function would then:

  1. be given a starting position and the number of moves already completed successfully (zero on the first call – obviously)
  2. return true if the number of successful moves already completed would fill the entire board
  3. make sure that the position is within the boundaries of the table (retuning false on failure)
  4. make sure that position was unoccupied (check that the corresponding value in the array is zero – again returning false on failure)
  5. change the value at that location of the array to the current number of moves completed
  6. call the function again with starting positions for each legal move with the new number of successful moves
  7. as soon as one of these functions return true, the function would then return true itself
  8. if no paths were found (all of the functions returned false) the function would then set the value in the array back to zero and return false itself

This table could then be displayed on the screen showing the calculated path.

I wrote a program to do this in about 15 minutes, but the problem is that it takes forever to calculate a path. At present, the program has been running for over 16 hours and still hasn’t come to a conclusion, nor do I even know how close it is to even getting to one.

Naturally, I wanted to rule out programmer error, so I adjusted the size of the board to 5×5 and ran it. This is what I got back instantaneously:

   1    6   15   10   21
  14    9   20    5   16
  19    2    7   22   11
   8   13   24   17    4
  25   18    3   12   23

This indicates to me that the code works, it just takes a long time to run through all the possible permutations.

I’ve posted the C source to my first attempt here and the documentation here.

Hopefully someone can help me find a faster solution, or I can find it myself.

EDIT – 13 Feb 2011:
The source code and documentation were lost. I found the source cached on Google (it’s now hosted at GitHub) and regenerated the documentation.

Posted in Member Blogs |
Tags: , ,