Ocaml:

Consider the maze shown below, where "S" marks the start position and "G" marks the two goal positions.

Your task is to write a function maze that returns the first path from an "S" position to one of the "G" positions that is found.

To keep this computation from happening when we load the file into utop, the function should take () the unit value as input and return a list of pairs on integer representing a path, wrapped up in an option type.

This function will have some things in common with the wolf-goat-cabbage problem that we solved in class, so make sure you understand that before attempting this one.

It is suggested that you write a function maze_moves that takes a position as input with the type int * int and then returns a list of positions, with type (int * int) list that are all the positions that could be moved to, while respecting the boundaries and lines in the maze. For example, one cannot move from position (3,1) to position (4,1).

You can implement this with a rather large match expression that just hard-codes the moves seen in the image above.

For example, your solution may execute the search in an order so that maze () evaluates to

Or, your maze function might instead return the path

Thus, the type of maze must be

Your maze runner solution should use the same KeepLooking exception to indicate when a deadend in the search has been reached or when some other reason exists to keep looking for solutions.

Your functions will also be checked that they conform to the proper style and use exceptions as described in class to implement backtracking search.

234 S G 12345 234 S G 12345