StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Update: I missed that a move is not required to be between two adjacent cells - this enlarges the number of possible moves at each step but does not really change the general idea.</p> <p>The easiest implementation is probably <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">depth-first search</a> - you start at the starting cell and look at all possible moves - except for the first move there are at most three possible moves. For each possible move you do the same recursively until you reach the starting cell again or there is no possible move remaining. In the later case you track back one move and try the next possibility if there is one remaining.</p> <p>You have to pass the direction of the last move along with the recursive call because this direction is not valid for the next move. If it is not allowed to visit cells several times you have to track the visited cells, too, and unmark them when tracking back. If it is allowed to visit cells several times you have to track the direction you left a cell when you visited it before in order to avoid cycles.</p> <p>Using <a href="http://en.wikipedia.org/wiki/Breath-first_search" rel="nofollow">breath-first search</a> instead of depth-first search will avoid trying long paths that are no solutions at the cost of keeping book of a large number of partial solutions. <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="nofollow">A* search</a> might be another option to speed this up.</p> <p>Side note: It may be the case that there is no value in visiting a cell several times because you could have take the other move directly when visiting the cell for the first time. The exception is doing the move not allowed when entering the cell for the first time but I am not sure if such a path is possible.</p>

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