horsepuzzle_start.py

import sys
from time import time
from collections import deque
from itertools import permutations

from pprint import pprint
# xxT = xx Top
# xxB = xx Bottom

# Chocolate Brown
CBT = 'CBT'
CBB = 'CBB'
# Light Brown
LBT = 'LBT'
LBB = 'LBB'
# Gray/Spotted
GST = 'GST'
GSB = 'GSB'
# Silver Beige
SBT = 'SBT'
SBB = 'SBB'

# Top, Right, Bottom, Left
T = 0
R = 1
B = 2
L = 3

matches = {
    CBT: CBB,
    LBT: LBB,
    GST: GSB,
    SBT: SBB}
matches.update((v, k) for (k, v) in list(matches.iteritems()))

cards = [
    [LBT, GSB, CBT, SBT],
    [LBT, GST, CBT, CBB],
    [LBT, CBT, LBB, SBT],
    [SBB, CBB, GST, LBB],
    [SBB, CBT, GST, LBB],
    [SBB, LBB, SBT, GST],
    [SBT, LBB, CBB, GSB],
    [GST, CBB, SBT, LBT],
    [GSB, GST, SBB, CBT],
]

print 'cards:'
pprint(cards)
print 'matches:'
pprint(matches)

class PuzzleGrid(object):

    rows = 3
    cols = 3

    def __init__(self, cards):
        self.cards = cards

    def is_solution(self):
        return all(self._match(c) for c in self.cards)

    def _match(self, card):
        top = self._top(card)
        if (top is not None) and (top[B] != matches[card[T]]):
            return False
        right = self._right(card)
        if (right is not None) and (right[L] != matches[card[R]]):
            return False
        bottom = self._bottom(card)
        if (bottom is not None) and (bottom[T] != matches[card[B]]):
            return False
        left = self._left(card)
        if (left is not None) and (left[R] != matches[card[L]]):
            return False
        return True

    def _left(self, card):
        index = self.cards.index(card)
        if (index % self.cols) == 0:
            return None
        return self.cards[index - 1]

    def _right(self, card):
        index = self.cards.index(card)
        if (index % self.cols) == 2:
            return None
        return self.cards[index + 1]

    def _top(self, card):
        index = self.cards.index(card)
        if index < self.cols:
            return None
        return self.cards[index - self.cols]

    def _bottom(self, card):
        index = self.cards.index(card)
        if index >= (self.cols * (self.rows - 1)):
            return None
        return self.cards[index + self.cols]
    
# Example, shitty inefficient solution

unique_solutions = set()

def exhaust(grid, index=0):
    for i in range(4):
        if grid.is_solution():
            print "solution!"
            pprint(grid.cards)
            solution = tuple(tuple(d) for d in grid.cards)
            if solution not in unique_solutions:
                unique_solutions.add(solution)
        if (index + 1) < (grid.cols * grid.rows):
            exhaust(grid, index + 1)
        current = grid.cards[index]
        current.rotate(1)
        
for p in permutations(cards):
    exhaust(PuzzleGrid([deque(c) for c in p]))