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.