pentomino puzzle solver
from kandinsky import * shapes = { 'C': ((0, 1, 10, 20, 21), (0, 1, 11, 20, 21), (0, -10, -9, -8, 2), (0, 10, 11, 12, 2)), 'F': ((0, 1, -9, 2, 12), (0, 1, 11, 2, -8), (0, 10, 11, 21, 12), (0, -10, -9, -19, -8), (0, 1, 11, 21, 12), (0, 1, -9, -19, -8), (0, 1, 11, -9, 12), (0, 1, 11, -9, -8)), 'I': ((0, 1, 2, 3, 4), (0, 10, 20, 30, 40)), 'L': ((0, 1, 2, 3, 13), (0, 1, 2, 3, -7), (0, 10, 20, 30, 1), (0, -10, -20, -30, 1), (0, 1, 11, 21, 31), (0, 1, -9, -19, -29), (0, 10, 1, 2, 3), (0, -10, 1, 2, 3)), 'N': ((0, 1, 11, 12, 13), (0, 1, -9, -8, -7), (0, 1, 2, 12, 13), (0, 1, 2, -8, -7), (0, 10, 20, 21, 31), (0, 10, 20, 19, 29), (0, 10, 11, 21, 31), (0, 10, 9, 19, 29)), 'P': ((0, 1, 2, 11, 12), (0, 1, 2, -9, -8), (0, 1, 2, 10, 11), (0, 1, 2, -10, -9), (0, 1, 10, 11, 20), (0, 1, 10, 11, 21), (0, 1, -10, -9, -20), (0, 1, -10, -9, -19)), 'S': ((0, 1, 11, 21, 22), (0, 1, -9, -19, -18), (0, 10, 11, 12, 22), (0, -10, -9, -8, -18)), 'T': ((0, 1, 11, 21, 2), (0, 1, -9, -19, 2), (0, 1, 2, -8, 12), (0, 10, -10, 1, 2)), 'V': ((0, 1, 2, 12, 22), (0, 1, 2, -8, -18), (0, 1, 2, 10, 20), (0, 1, 2, -10, -20)), 'W': ((0, 1, 11, 12, 22), (0, 1, -9, -8, -18), (0, 10, 11, 21, 22), (0, -10, -9, -19, -18)), 'X': ((0, -9, 1, 11, 2),), 'Y': ((0, 1, 2, 3, 12), (0, 1, 2, 3, -8), (0, 10, 20, 30, 11), (0, -10, -20, -30, -9), (0, 1, 11, 21, -9), (0, 1, -9, -19, 11), (0, 11, 1, 2, 3), (0, -9, 1, 2, 3)) } colors = { ' ': color(0,0,0), 'X': color(240,0,0), 'T': color(0,240,0), 'C': color(0,0,240), 'W': color(240,0,240), 'I': color(0,240,240), 'S': color(240,240,0), 'F': color(240,160,160), 'P': color(160,240,160), 'L': color(160,160,240), 'V': color(240,160,240), 'Y': color(160,240,240), 'N': color(240,240,160), } def init(width, height, unit, refresh): global w, h, u, r, n, x0, y0, board, pieces w = width h = height u = unit r = refresh x0, y0 = (320-w*u)//2, 30 board = ['#'] * (10*w+90) for row in range(h): for col in range(w): board[col*10+row+11] = ' ' n = 0 pieces = list("CXTYFWPISLVN") def display(): for col in range(w): for row in range(h): x = col*u+x0 y = row*u+y0 c = colors[board[col*10+row+11]] for i in range(u): for j in range(u): set_pixel(x+i, y+j, c) draw_string('%04d solutions' % n, 4, 4) def solve(): global n for q in range(len(board)): if board[q] == ' ': for p in pieces: for s in shapes[p]: for c in s: for d in s: if board[q+d-c] != ' ': break else: for d in s: board[q+d-c] = p i = pieces.index(p) pieces.remove(p) if not pieces: n += 1 display() else: if r: display() solve() pieces.insert(i, p) for d in s: board[q+d-c] = ' ' return def pentomino(width=10, height=6, unit=30, refresh=True): init(width, height, unit, refresh) solve()