title: Riddle: The Square Puzzle
body: <p>Last couple of days, I have refrained myself from master's studies and have been focusing on this (seemingly simple) puzzle:  </p>
  
  <hr>
  
  <p>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 :)  </p>
  
  <p>The rules for traversing are:<br>
  1. Two spaces hop along the vertical and horizontal axis<br>
  2. One space hop along the diagonals<br>
  3. You can visit each square only once</p>
  
  <p>To visualise better, here is a valid example traverse (up to the 8th step):<br>
  <a href="http://img525.imageshack.us/img525/280/squarepuzzle.png" rel="nofollow noreferrer">Example Traverse http://img525.imageshack.us/img525/280/squarepuzzle.png</a></p>
  
  <hr>
  
  <p>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 :)</p>
  
  <p>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.<br>
  The program simply applies exhaustive try &amp; error solving technique. In other words: brute force depth first search.</p>
  
  <p>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.<br>
  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.</p>
  
  <p>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?</p>
  
  <p>Basically, I am looking forward to see ideas on how to:</p>
  
  <ol>
  <li>Capture and exploit <strong>domain knowledge</strong> specific to this problem</li>
  <li><p>Apply <strong>programming techniques/tricks</strong> to overcome exhaustion</p>
  
  <p>..and finally realize into a substantial solution.</p></li>
  </ol>
  
  <p>Thanks in advance.</p>
  
  <hr>
  
  <p><strong>Revision</strong><br>
  Thanks to Dave Webb for relating the problem to domain it belongs: </p>
  
  <blockquote>
    <p>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".</p>
  </blockquote>
  
  <hr>