StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PORiddle: The Square Puzzle
text
Body
copied!<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 & 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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload