EMPTY="." FULL="O" class Piece: def __init__(self,variants): self.variants=variants pieces=[] pieces.append(Piece([ # OO # OO ((0,0),(0,1),(1,0),(1,1)) ])) pieces.append(Piece([ # OOOO ((0,0),(0,1),(0,2),(0,3)), ((0,0),(1,0),(2,0),(3,0)) ])) pieces.append(Piece([ # OOO # .O. ((0,0),(0,1),(0,2),(1,1)), ((0,0),(1,0),(2,0),(1,1)), ((0,0),(1,-1),(1,0),(1,1)), ((0,0),(1,-1),(1,0),(2,0)) ])) pieces.append(Piece([ # .OO # OO. ((0,0),(0,1),(1,-1),(1,0)), ((0,0),(1,0),(1,1),(2,1)), # OO. # .OO ((0,0),(0,1),(1,1),(1,2)), ((0,0),(1,0),(1,-1),(2,-1)) ])) pieces.append(Piece([ # OOO # O.. ((0,0),(1,0),(0,1),(0,2)), ((0,0),(1,0),(2,0),(2,1)), ((0,0),(1,-2),(1,-1),(1,0)), ((0,0),(0,1),(1,1),(2,1)), # OOO # ..O ((0,0),(0,1),(0,2),(1,2)), ((0,0),(0,1),(1,0),(2,0)), ((0,0),(1,0),(1,1),(1,2)), ((0,0),(1,0),(2,0),(2,-1)) ])) WIDTH=5 HEIGHT=5 board=[[EMPTY]*WIDTH for r in range(HEIGHT)] def fill(board): point=firstEmpty(board) if not point: return True res=[] for p in pieces: for v in p.variants: if place(board,point,v): partialRes=fill(board) if partialRes: res+=[((point,v), partialRes)] remove(board,point,v) return res def firstEmpty(board): for (r,row) in enumerate(board): for (c,cell) in enumerate(row): if cell==EMPTY: return (r,c) return None def place(board,point,piece): (r,c)=point if not all(0<=r+ri