(Please refer to the detailed explanations in the .py file attached).
The code is tested under Python 3.3 under Win x64 environment. If you believe a different python version might cause any trouble, please let me know and I will test the code in the environment you specify.
# This might not be the most efficient implementation, but it should work.
# The idea is to walk randomly, but never make the same move again.
# For example, if we move north from x=0,y=1, and we got stucked,
# then the next time we reach the node x=0,y=1, we should never go north again
# This function determines if we can move to node x,y
# Returns false whenever the node is invalid, or the node is a wall
def CanMove(maze, x, y):
if x < 0 or y < 0 or y >= len(maze):
row = maze[y]
if x >= len(row):
# Move coordinate from x,y forward by 1 unit in the direction facing
def MoveDir(facing, x, y):
if facing == 'N':
The solution contains a working python code that solves the path finding problem. The code is fully documented and contains a detailed explanation of the algorithm.