Solution finder for The Megakolmio Awakens problem

megasolve.py

"""
Running this script prints out every possible solution
to the Mega triangle problem described at:
http://www.wunderdog.fi/wundernut-megakolmio

Requires Python 2.7 or later!

Author: Kimmo Kiiski
"""
from collections import defaultdict


class MiniTriangle:
    """
    Simple class for a named triange with the given sides.
    """
    def __init__(self, name, sides):
        self.name = name
        self.sides = sides


# Aliases for different side types and their counterparts
FOX_HEAD, FOX_BODY = (1, -1)
DEER_HEAD, DEER_BODY = (2, -2)
RACOON_HEAD, RACOON_BODY = (3, -3)

# Mini triangles used in this problem
P1 = MiniTriangle("P1", [FOX_HEAD, FOX_BODY, DEER_HEAD])
P2 = MiniTriangle("P2", [DEER_HEAD, FOX_BODY, RACOON_BODY])
P3 = MiniTriangle("P3", [DEER_HEAD, FOX_BODY, FOX_HEAD])
P4 = MiniTriangle("P4", [DEER_HEAD, DEER_BODY, FOX_BODY])
P5 = MiniTriangle("P5", [DEER_HEAD, RACOON_BODY, DEER_BODY])
P6 = MiniTriangle("P6", [RACOON_BODY, FOX_BODY, RACOON_HEAD])
P7 = MiniTriangle("P7", [FOX_BODY, RACOON_HEAD, FOX_HEAD])
P8 = MiniTriangle("P8", [RACOON_HEAD, DEER_HEAD, RACOON_BODY])
P9 = MiniTriangle("P9", [FOX_BODY, DEER_BODY, DEER_HEAD])

# Aliases for triangle side indexes.
# NOTE: Each side has the same index than the opposing side on an edge!
TOP_LEFT = BOTTOM_RIGHT = 0
TOP_RIGHT = BOTTOM_LEFT = 1
BOTTOM = TOP = 2

# Aliases for solution indexes to match the numbering on the assignment
I1, I2, I3, I4, I5, I6, I7, I8, I9 = range(9)

# A mappings from triangle indexes to lists of their neighbors.
# Each neighbor is represented as a tuple (<side index>, <triangle index>).
# NOTE: We only need to link positions backward to earlier indexes,
# because the algorithm starts filling from the lowest indexes.
NEIGHBORS = defaultdict(list)
NEIGHBORS[I3].append((BOTTOM_LEFT, I2))
NEIGHBORS[I3].append((TOP, I1))
NEIGHBORS[I4].append((TOP_LEFT, I3))
NEIGHBORS[I6].append((TOP, I2))
NEIGHBORS[I6].append((BOTTOM_LEFT, I5))
NEIGHBORS[I7].append((TOP_LEFT, I6))
NEIGHBORS[I8].append((TOP, I4))
NEIGHBORS[I8].append((BOTTOM_LEFT, I7))
NEIGHBORS[I9].append((TOP_LEFT, I8))


def match(side1, side2):
    """
    Returns whether or not the given sides match each other.
    """
    return side1 + side2 == 0


def edges(selected, triange):
    """
    Generates each possible pair of sides on edges when the given 'triangle'
    is placed at the first available index after the 'selected' triangles.
    The 1st item in each pair is a side of the given triangle and the 2nd
    item is a side on a neighbor.
    """
    for side, neighbor_pos in NEIGHBORS[len(selected)]:
        neighbor = selected[neighbor_pos]
        yield triange.sides[side], neighbor.sides[side]


def fit(selected, triange):
    """
    Returns whether or not 'triange' can be fitted to the first available
    index after the 'selected' trianges.
    """
    return all(match(*sides) for sides in edges(selected, triange))


def rotations(triange):
    """
    Generates three trianges by rotating the given 'triangle' to
    all of its three possible orientations.
    """
    yield triange  # 0 deg
    yield MiniTriangle(triange.name, triange.sides[1:] + triange.sides[:1])  # 120 deg
    yield MiniTriangle(triange.name, triange.sides[2:] + triange.sides[:2])  # 240 deg


def megasolve(options, attempt=[]):
    """
    Generates all the possible solutions for the mega triangle
    using the given set of MiniTriangles, using a recursive
    depth-first search algorithm.
    """
    # All options consumed? Found a solution!
    if not options:
        yield attempt
    # Try each option in all their orientations
    for option in options:
        for rotation in rotations(option):
            if fit(attempt, rotation):
                # If it fits, then recursively fit all other pieces
                for solution in megasolve(options - {option}, attempt + [rotation]):
                    yield solution


if __name__ == "__main__":
    # Print every solution using these triangle pieces
    options = {P1, P2, P3, P4, P5, P6, P7, P8, P9}
    for solution in megasolve(options):
        print "[%s]" % ", ".join(triangle.name for triangle in solution)