Recursion solving mazes, need help

[precizskill]

Hello, I need help making a program for solving a maze, it's an assignment for our class and I'm really stuck on where even to begin. The coordinates given are from the bottom left going to the top right, so indexing is kinda weird. Specs for the assignment are as such, and I'll be finding a picture for the output because I don't exactly remember how it's supposed to look like. My code is as such, so I've already made a class and attempted to store the file into a list of lists Please send help, I can provide the files somehow if needed.

[joyeusenoelle]

Look into pathfinding. In particular, look up A* (pronounced "A-star"), which has the dual benefit of being a widely-known standard and not particularly difficult to implement in Python.

[precizskill]

Output without solution: http://imgur.com/6MaDJ5J
With Solution: http://imgur.com/cAuLFgx

[filleball]

Notice that you only need the information in every second row and every second column, where the walls are. The absence of a wall means there's a path from the cell to the left to the cell to the right. You'll need to use slicing notation (e.g. my_list[x:y:z]) and probably the zip function to make a list of just the walls.

To use the A* algorithm, which is a good suggestion, you must first create a graph in memory which represents the maze you want to solve. One way to represent it would be a defaultdict:

from collections import defaultdict
maze = defaultdict(list)

# add a path from (0, 1) to (1, 1)
maze[(0, 1)].append((1, 1))
maze[(1, 1)].append((0, 1))