CareerCup

Just use right hand rule for a robot, always go forward, if it is not possible turn right and go forward, until robot finds the exit.

A maze is, when simplified, little more than a set of permutations of choices, of which only one (unless it has multiple paths to end) is the correct. For a position p in the maze, there are at most c choices (usually 3, left, right, forward) so to traverse the maze accurately you need O(c^n) time, where n is the maximum number of turns possible in the maze before hitting a dead end or the end of the maze. This is essentially a tree.

Supposing the robot is able to backtrack and has no awareness of what lay around any of the presented options (left, right, forward) you can utilize a recursive algorithm

in python with some assumed functions:

class Position:
	#contains a list of pointers, choices, and position value.
	# also contains a function move_to which creates a position for that direction
	#and a function is_end which specifies if the position is the end of the maze

	#contains a static set called visited which indicates when a specific position has
	#been previously visited by the algorithm.


def solve_maze(position):
	if position in position.visited:
		return []
	position.visited.add(position)
	if position.is_end():
		return [position]
	for x in position.choices:
		y = solve_maze(position.move_to(x))
		if not y:
			continue
		else:
			return position + y
	return []

The solve_maze function returns a ordered list of positions. If the returned list is empty, it is ignored as it means that that sub-tree of movements resulted in a dead end. Otherwise, the current position of that recursion layer is added to it, and returned.

What this means is the recursion will always hit the bottom of the tree of possible paths first, then begin working in depth-first order. The only paths which will propagate back up to the root are those which result in reaching the end of the maze.

Additionally, the visited list will prevent parts of the maze which loop creating an infinite recursion. In no maze is there ever a reason to go to the same point twice.

The Position class will, when given the move_to command, continue until the next point in the maze where you encounter a choice.

This will run in the runtime stated above, not terribly efficient. Memoization is provided in the form of the visited list, as any one point will have a fixed set of valid paths, regardless of which direction it is approached from.

Use Dijjkstra's algorithm or an A* variant.

This is same as depth first traversal of graph

This is same as Depth first traversal of a graph.
1. Choose a random node
2. Push node to stack
3. Visit the first adjacent unvisited node next to this node.
4. Mark the node in step# 3 as visited
5. Push the node in step #3 to stack
If step #3 is not possible, pop node from stack