Riddle: The Square Puzzle

Question

Last couple of days, I have refrained myself from master's studies and have been focusing on this (seemingly simple) puzzle:

---

There is this 10*10 grid which constitutes a square of 100 available places to go. The aim is to start from a corner and traverse through all the places with respect to some simple "traverse rules" and reach number 100 (or 99 if you're a programmer and start with 0 instead :)

The rules for traversing are:
1. Two spaces hop along the vertical and horizontal axis
2. One space hop along the diagonals
3. You can visit each square only once

To visualise better, here is a valid example traverse (up to the 8th step):
Example Traverse http://img525.imageshack.us/img525/280/squarepuzzle.png

---

Manually, I have been working on this puzzle out of boredom. For years, I have tried to solve it by hand from time to time, but I have never gone beyond 96. Sounds easy? Try yourself and see for yourself :)

Thus, in order to solve the problem, I have developed a short (around 100 lines of code) program in Python. I am a beginner in this language I wanted to see what I can do.
The program simply applies exhaustive try & error solving technique. In other words: brute force depth first search.

My question arises from here on: The program, unfortunately cannot solve the problem because the state space is so big that search never ends withouh ever finding a solution. It can go up to number 98 (and prints that) without much difficulty, nonetheless not a complete solution.
The program also prints out the length of the search tree it has covered so far. In a couple of minutes, the traverse list from, say, 65th element is covered till the end, for just one single path. This number decreases in exponentially increasing time periods. I have run the code for quite some time and could not get beyond 50 barrier and now I am convinced.

It seems that this simple approach will not be enough unless I run it for ever. So, how can I improve my code to be faster and more efficient so that it comes up with solutions?

Basically, I am looking forward to see ideas on how to:

1. Capture and exploit domain knowledge specific to this problem

2. Apply programming techniques/tricks to overcome exhaustion

   ..and finally realize into a substantial solution.

Thanks in advance.

---

Revision
Thanks to Dave Webb for relating the problem to domain it belongs:

This is very similar to the Knight's Tour problem which relates moving a knight around a chess board without revisiting the same square. Basically it's the same problem but with different "Traverse Rules".

---

Answer 1

This is very similar to the Knight's Tour problem which relates moving a knight around a chess board without revisiting the same square. Basically it's the same problem but with different "Traverse Rules".

The key optimisation I remember from tackling the Knights Tour recursively is take your next moves in increasing order of the number of available moves on the destination square. This encourages the search to try and move densely in one area and filling it rather than zooming all over the board and leaving little island squares that can never be visited. (This is Warnsdorff's algorithm.)

Also make sure you have considered symmetry where you can. For example, at the simplest level the x and y of your starting square only need to go up to 5 since (10,10) is the same as (1,1) with the board rotated.