Python script to generate permutations of a 3x3 grid divided into rectangles

areagrid.py

import string

primes = []
first100primes = []
START_VALS = range(0,3)
SIZE_VALS = range(1,4)

class XY:
    def __init__(self, x, y):
        self.x = x
        self.y = y

#start and size are of class XY
class Rect:
    def __init__(self, start, size):
        self.start = start
        self.size = size

    def move(self, moveXY):
        return Rect(XY(self.start.x + moveXY.x, self.start.y+moveXY.y), self.size)

    def contains(self, xy):
        return xy.x >= self.start.x and xy.x < self.start.x+self.size.x and xy.y >= self.start.y and xy.y < self.start.y+self.size.y

buildingBlocks = [] #list of Rects with start position 0,0
for width in SIZE_VALS:
    for height in SIZE_VALS:
        buildingBlocks.append(Rect(XY(0,0), XY(width,height)))
        
        
class Grid:

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

    def __str__(self):
        out = [[0,0,0],[0,0,0],[0,0,0]]
        for i,rect in enumerate(self.rects):
            for x in range(rect.start.x, rect.start.x + rect.size.x):
                for y in range(rect.start.y, rect.start.y + rect.size.y):
                    out[y][x] = i+1
        return '\n'.join(str(x) for x in out)   #returns the three sublists on seperate lines

    def withRect(self, rect):
        if self.isRectValid(rect):
            return Grid(self.rects + (rect,))

    def getFreePosition(self):
        for x in START_VALS:
            for y in START_VALS:
                xy = XY(x,y)
                if self.getSomeBlockingRect(xy) is None:
                    return xy
        return None

    def getSomeBlockingRect(self, xy):
        for rect in self.rects:
            if rect.contains(xy):
                return rect
        return None

    def getValidAdditionalRects(self, start):
        validRects = []
        for block in buildingBlocks:
            rect = block.move(start)
            if self.isRectValid(rect):
                validRects.append(rect)
        return validRects

    def isRectValid(self, rect):
        coords = [XY(x,y) for x in range(rect.start.x, rect.start.x+rect.size.x) for y in range(rect.start.y, rect.start.y+rect.size.y)]
        for xy in coords:
            x = xy.x
            y = xy.y
            if x < 0 or x > 2 or y < 0 or y > 2:
                return False
            if self.getSomeBlockingRect(xy) is not None:
                return False
        return True
        

emptygrid = Grid(tuple())

def permutate(grid, output):
    start = grid.getFreePosition()
    if (start is None):
        output.append(grid)
        return

    for rect in grid.getValidAdditionalRects(start):
        newGrid = grid.withRect(rect)
        permutate(newGrid, output)

def getPermutations():
    output = []
    permutate(emptygrid, output)
    return output