Turing Maze - CodeAbbey

Sometimes troubles build up around as if one is in a maze! A-mazing! Let's make puzzle of it!

We are going to traverse some maze using our Turing Machine. Of course we need to extend it a bit, so it can operate in 2-Dimensional space instead of simple tape.

That's easy! Here is a sum of additions (check the article above for details):

comment ;2d in beginning switch machine to 2d-mode
movement commands now are not only L and R but also U and D
alternative "turtle" movement system includes commands FW, BK, TL, TR - forward, backward, turn-left, turn-right

Problem Statement

We have a maze with no loops (also called "simple" or "perfect"), represented with a rectangle filled with '-'s (passages) and 'W's (walls). One of the cells deep in the maze is marked with '$' - also passage, but additionally evil kobold's chest of gold is here!

Machine starts at top-left corner (which of course is '-') and should find the way to the chest. Mark this way by turning corresponding cells to +.

For example consider the initial maze state and solution we wish:

  initial:                 solved:

--W----W--W              ++W-+++W--W
W-WW-W-WW-W              W+WW+W+WW-W
-----W----W              -++++W+++-W
-WWWWWWW-W$              -WWWWWWW+W+
----WW-----              ----WW--+++