Quick script to brute-force http://ask.metafilter.com/259160/How-many-different-colors-does-this-quilt-need

gistfile1.py

#!/usr/bin/env python

from copy import deepcopy
from random import shuffle

X = 10
Y = 12

grid = [[None for i in range(X)] for j in range(Y)]
indices = [(i,j) for j in range(Y) for i in range(X)]
shuffle(indices)

# patterns will be a dict of dict of lists, such that:
# patterns[c1][c2] = [(dx, dy), ...] where (dx, dy) are the offsets
# from a tile of color c2 to a tile of color c1
patterns = {}

for i,j in indices:
    c = 0
    while True:
        c += 1
        
        # check if we're the same color of adjacent tiles 
        print 'on tile ', i, j, ' trying ', c
        if j>0:
            if i>0:
                if grid[j-1][i-1] == c:
                    print 'matches above left'
                    continue
            if i+1<X:
                if grid[j-1][i+1] == c:
                    print 'matches above right'
                    continue
            if grid[j-1][i] == c:
                print 'matches above'
                continue
        if i>0:
            if grid[j][i-1] == c:
                print 'matches left'
                continue
        if i+1<X:
            if grid[j][i+1] == c:
                print 'matches right'
                continue
        if j+1<Y:
            if i>0:
                if grid[j+1][i-1] == c:
                    print 'matches below left'
                    continue
            if i+1<X:
                if grid[j+1][i+1] == c:
                    print 'matches below right'
                    continue
            if grid[j+1][i] == c:
                print 'matches below'
                continue
            
            
        # now check the offsets. the test algorithm is destructive, so 
        # copy the dict
        newpatterns = deepcopy(patterns)
        flag = False

        for ii,jj in [(ii,jj)
                      for jj in range(Y)
                      for ii in range(X)]:
            # skip testing ourself
            if i == ii and j == jj: continue

            dx = ii-i
            dy = jj-j
            testcolor = grid[jj][ii]
            
            # skip if there's no one there
            if not testcolor: continue

            matches = newpatterns.setdefault(c, {}).setdefault(testcolor, [])
            if (dx, dy) in matches:
                print 'matches %d at (%d, %d)' % (testcolor, dx, dy)
                flag = True
                break
            newpatterns[c][testcolor].append((dx,dy))
            newpatterns.setdefault(testcolor,
                                   {}).setdefault(c, []).append((-dx,-dy))
            
        # can't tell if we broke the loop or fell off the end. I know 
        # flags are unpythonic but this was a quick hack. if the flag was
        # never set, we didn't conflict with any existing patterns, so 
        # overwrite the old dict with the ones we've testing by the append
        # statement above
        if not flag:
            patterns = newpatterns
            break

    print 'setting (%d, %d) to %d' % (i, j, c)
    grid[j][i] = c
            
for line in grid:
    print ' '.join(['%02d' % tile for tile in line])
print 'total used: ', max([max(row) for row in grid])