# Author: Manfred Scheucher # Date : 04.06.2015 from sys import argv from copy import copy def placeH(grid,stuff,x,y): grid2 = copy(grid) stuff2 = copy(stuff) grid2.append((x,y)) grid2.append((x+1,y)) stuff2[(x,y)] = 'H' return grid2, stuff2 def placeV(grid,stuff,x,y): grid2 = copy(grid) stuff2 = copy(stuff) grid2.append((x,y)) grid2.append((x,y+1)) stuff2[(x,y)] = 'V' return grid2, stuff2 def normalize(grid,stuff): if not grid: return grid, stuff x0 = min([x for (x,y) in grid]) y0 = min([y for (x,y) in grid]) grid2 = [(x-x0,y-y0) for (x,y) in grid] stuff2 = {(x-x0,y-y0):stuff[(x,y)] for (x,y) in stuff} return grid2, stuff2 def print_(grid,stuff): x0 = min([x for (x,y) in grid]) x1 = max([x for (x,y) in grid]) y0 = min([y for (x,y) in grid]) y1 = max([y for (x,y) in grid]) toprint = {(x,y):' ' for x in [x0..x1] for y in [y0..y1]} for (x,y) in stuff: toprint[(x,y)] = stuff[(x,y)] if stuff[(x,y)]=='H': toprint[(x+1,y)] = '-' else: toprint[(x,y+1)] = '|' for y in [y0..y1]: for x in [x0..x1]: print toprint[(x,y)], print def place(k=0,grid=[],stuff=dict()): grid,stuff = normalize(grid,stuff) if stuff not in solutions[k]: solutions[k].append(stuff) if k == n: print "sol #",len(solutions[n]),":",stuff#,grid2 #print #print_(grid,stuff) #print else: if not grid: grid2,stuff2 = placeH(grid,stuff,0,0) place(k+1,grid2,stuff2) grid2,stuff2 = placeV(grid,stuff,0,0) place(k+1,grid2,stuff2) else: for (x,y) in grid: for (dx,dy) in [(-2,0),(1,0),(-1,-1),(0,-1),(-1,1),(0,1)]: # horizontal placement (x2,y2) = (x+dx,y+dy) if (x2,y2) not in grid and (x2+1,y2) not in grid: grid2,stuff2 = placeH(grid,stuff,x2,y2) place(k+1,grid2,stuff2) # vertical placement (mirrored possibilies) (x2,y2) = (x+dy,y+dx) if (x2,y2) not in grid and (x2,y2+1) not in grid: grid2,stuff2 = placeV(grid,stuff,x2,y2) place(k+1,grid2,stuff2) n = int(argv[1]) solutions = {k:[] for k in [0..n]} place() for k in [0..n]: print "a("+str(k)+")="+str(len(solutions[k]))