Set solver that looks for a deck where the first N plays have one and only one solution

set.py

import random
import itertools


NUMBERS = {1: "One", 2: "Two", 3: "Three"}
SHADES = {1: "Clear", 2: "Hatched", 3: "Solid"}
COLORS = {1: "Red", 2: "Green", 3: "Purple"}
SHAPES = {1: "Pill", 2: "Diamond", 3: "Tilde"}


class Card:
    def __init__(self, number, shade, color, shape):
        self.number = number
        self.shade = shade
        self.color = color
        self.shape = shape

    def __str__(self):
        return NUMBERS[self.number] + SHADES[self.shade] + COLORS[self.color] + SHAPES[self.shape]

    def __repr__(self):
        return self.__str__()

class Deck:
    def __init__(self):
        self.stack = []
        for number in NUMBERS.keys():
            for shade in SHADES.keys():
                for color in COLORS.keys():
                    for shape in SHAPES.keys():
                        self.stack.append(Card(number, shade, color, shape))
        if len(self.stack) != 81:
            print len(self.stack)
            raise ValueError('The stack of cards is not the right size!')
        self.archived_stack = tuple(self.stack)

    def flop(self, n):
        cards = []
        while n > 0:
            card = self.stack.pop()
            print card
            cards.append(card)
            n -= 1
        return cards


class Game:
    def __init__(self):
        self.deck = Deck()
        self.board = []
        self.sets = []
        self.shuffle()

    def shuffle(self):
        '''Resets the game deck'''
        # return used cards to the stack
        self.deck.stack = self.deck.stack + self.board + list(itertools.chain.from_iterable(self.sets))
        self.board = []
        self.sets = []
        random.shuffle(self.deck.stack)
        self.deck.archived_stack = tuple(self.deck.stack)

    def deal(self):
        '''Deals appropriate number of cards based on current board.
        Does not check for sets before doing so.'''
        board_size = len(self.board)
        if board_size == 0:
            # initial deal
            print "Dealing initial board"
            cards = self.deck.flop(12)
            self.board = cards
        elif board_size == 9:
            # let's add three cards
            print "Dealing"
            cards = self.deck.flop(3)
            self.board = self.board + cards
        elif board_size % 3 == 0:
            print "Dealing another"
            cards = self.deck.flop(3)
            self.board = self.board + cards
        else:
            print board_size
            raise ValueError("Number of cards on the board is invalid.")
        assert len(self.board) % 3 == 0

    def remove_set(self, card_list):
        '''Remove a set from the board, add it to the list of sets.'''
        for card in card_list:
            try:
                self.board.remove(card)
            except ValueError:
                print card
                print card_list
                raise
        self.sets.append(card_list)
        print "Removed set: " + str(card_list)

    def valid_set_attr(self, attr):
        '''takes a list of the three cards' values for a single attribute, 
        tests if they're all the same or all different, based on sum'''
        if sum(attr) in [3, 6, 9]:
            return True
        elif sum(attr) in [4,5,7,8]:
            return False
        print attr
        raise ValueError("I got a sum I didn't expect, oh no")


    def is_set(self, cards):
        '''Given a list of three Card objects, 
        returns boolean for whether they're a valid set or not.'''
        try:
            assert self.valid_set_attr([cards[0].number, cards[1].number, cards[2].number])
        except AssertionError:
            #print "Bad number"
            return False
        try:
            assert self.valid_set_attr([cards[0].shade, cards[1].shade, cards[2].shade])
        except AssertionError:
            #print "Bad shade"
            return False
        try:
            assert self.valid_set_attr([cards[0].color, cards[1].color, cards[2].color])
        except AssertionError:
            #print "Bad color"
            return False
        try:
            assert self.valid_set_attr([cards[0].shape, cards[1].shape, cards[2].shape])
        except AssertionError:
            #print "Bad shape"
            return False
        return True


    def find_multi_sets(self):
        '''Finds all valid sets on the current board.'''
        sets = []
        combinations = list(itertools.combinations(self.board, 3))
        for combo in combinations:
            if self.is_set(combo):
                sets.append(list(combo))
                if len(sets) > 1:
                    break
        return sets


DESIRED_NUM = 7
MAX_ATTEMPTS = 5000

if __name__ == "__main__":
    print "Let's play some Set!"
    # for testing purposes
    # this seed finds a solution for 7 single-solutions within <5000 attempts
    random.seed(9000)
    g = Game()
    max_singles = 0
    single_solution_sets = 0
    # looking for a deck that gives us a singular solution
    # for at least the first five plays
    num_attempts = 0
    while num_attempts < MAX_ATTEMPTS:
        num_attempts += 1

        while single_solution_sets < DESIRED_NUM:
            # fill board
            g.deal()
            # look for sets
            sets = g.find_multi_sets()
            if len(sets) == 1:
                # yay
                single_solution_sets += 1
                max_singles = single_solution_sets if single_solution_sets > max_singles else max_singles
                g.remove_set(sets[0])
            elif len(sets) != 0:
                # non-zero number of sets means too many sets
                break

        # did we solve?
        if single_solution_sets == DESIRED_NUM:
            break
        else:
            print "* * * * * * * * * *"
            print "Too many options, reshuffling"
            print "* * * * * * * * * *"
            g.shuffle()
            single_solution_sets = 0

    if single_solution_sets == DESIRED_NUM:
        print "* * * * * * * * * *"
        print "HOORAY!!!!"
        print "Sets: " + str(g.sets)
        print g.deck.archived_stack[::-1]
    else:
        print "Ran out of attempts :("
        print max_singles