## Solving Paper Mazes with Python

Every year just after Christmas there is a quiz game called "De Rooise Kwis" in which a lot of people in Sint Oedenrode participate. This year there were 151 teams.

The quiz consists of questions in a wide range of categories, which can be found here

As soon as we got the questions we formed pairs to solve a different category, i was assigned to the puzzles. While scanning through the questions i quickly saw the large maze which had to be solved. There are letters in the maze which form a word if you follow the correct path to the exit.

Instead of manually solving the puzzle i decided to try and solve it with some Python. First i scanned the image of the maze and opened up Gimp to prepare the image by replacing colors with black and white colors.

This approach uses the Breadth First Search algorithm which is not very efficient but guarantees to solve it. A visualization of the algorithm can be found at Pathfinding.js.

```
import sys
from Queue import Queue
from PIL import Image
# Point where the algorithm should start
start = (4,4)
# Point where the maze is solved
end = (1363,1368)
# Check if the pixel is white/visitable
def iswhite(value):
if value == (255,255,255):
return True
def getadjacent(n):
x,y = n
return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]
# Breadth first search
def BFS(start, end, pixels):
queue = Queue()
queue.put([start]) # Wrapping the start tuple in a list
while not queue.empty():
path = queue.get()
pixel = path[-1]
if pixel == end:
return path
for adjacent in getadjacent(pixel):
x,y = adjacent
if x > 0 and y > 0 and iswhite(pixels[x,y]):
pixels[x,y] = (127,127,127) # mark the visited area grey
new_path = list(path)
new_path.append(adjacent)
queue.put(new_path)
print "No answer was found."
if __name__ == '__main__':
maze_image = "maze.png"
base_img = Image.open(maze_image)
base_pixels = base_img.load()
path = BFS(start, end, base_pixels)
path_img = Image.open(maze_image)
path_pixels = path_img.load()
for position in path:
x,y = position
path_pixels[x,y] = (255,0,0) # red
path_img.save("maze-solved.jpg")
```

The code runs the algorithm and when it finds a solution it draws a red 1 pixel line (hard to see) to the exit of the maze.

The whole solution took me around 20 minutes, which saved me a lot of time compared to the other people who tried to solve it, and in some cases did not even finish it.