Roy van Kaathoven
Full Stack Developer

30 Dec

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.

Paper Maze 1

Paper Maze 2