# bench-only
# bench-args: 100
# bench-output: 100 solutions found
# bench-output:
# bench-output: 1 3 3 3 4
# bench-output:  1 3 2 2 4
# bench-output: 1 3 2 4 4
# bench-output:  1 1 2 5 4
# bench-output: 6 6 8 2 5
# bench-output:  6 8 9 5 5
# bench-output: 6 8 0 9 5
# bench-output:  6 8 0 9 9
# bench-output: 7 8 7 0 9
# bench-output:  7 7 7 0 0
# bench-output:
# bench-output: 9 9 9 9 8
# bench-output:  9 6 6 8 3
# bench-output: 6 6 8 8 3
# bench-output:  6 8 3 3 3
# bench-output: 4 4 2 2 2
# bench-output:  1 4 4 7 2
# bench-output: 1 4 0 7 2
# bench-output:  1 1 0 7 7
# bench-output: 5 5 1 0 7
# bench-output:  5 5 5 0 0

# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org/
#
# contributed by: Olof Kraigher
# 2to3

# COMMAND LINE:
# /usr/local/src/Python-3.4.3/bin/python3.4 meteor.py 2098

# PROGRAM OUTPUT:
# 2098 solutions found
#
# 0 0 0 0 1
#  2 2 2 0 1
# 2 6 6 1 1
#  2 6 1 5 5
# 8 6 5 5 5
#  8 6 3 3 3
# 4 8 8 9 3
#  4 4 8 9 3
# 4 7 4 7 9
#  7 7 7 9 9
#
# 9 9 9 9 8
#  9 6 6 8 5
# 6 6 8 8 5
#  6 8 2 5 5
# 7 7 7 2 5
#  7 4 7 2 0
# 1 4 2 2 0
#  1 4 4 0 3
# 1 4 0 0 3
#  1 1 3 3 3

import sys

width = 5
height = 10

directions  = { "E" : 0, "NE" : 1, "NW" : 2, "W" : 3, "SW" : 4, "SE" : 5}
rotate      = { "E" : "NE", "NE" : "NW", "NW" : "W", "W" : "SW", "SW" : "SE", "SE" : "E"}
flip        = { "E" : "W", "NE" : "NW", "NW" : "NE", "W" : "E", "SW" : "SE", "SE" : "SW"}
move        = { "E" : lambda x,y: (x+1,y),
                "W" : lambda x,y: (x-1,y),
                "NE" : lambda x,y: (x+(y%2),y-1),
                "NW" : lambda x,y: (x+(y%2)-1,y-1),
                "SE" : lambda x,y: (x+(y%2),y+1),
                "SW" : lambda x,y: (x+(y%2)-1,y+1)}

pieces =   [    ["E", "E", "E", "SE"],
                ["SE", "SW", "W", "SW"],
                ["W", "W", "SW", "SE"],
                ["E",  "E", "SW", "SE"],
                ["NW", "W", "NW", "SE", "SW"],
                ["E",  "E", "NE", "W"],
                ["NW", "NE", "NE", "W"],
                ["NE", "SE", "E", "NE"],
                ["SE", "SE", "E", "SE"],
                ["E", "NW", "NW", "NW"]]

solutions = []
masks = [0 for i in range(10)]

valid = lambda x,y: (0 <= x) and (x < width) and (0 <= y) and (y < height)
legal = lambda mask,board: (mask & board) == 0
zerocount = lambda mask: sum([((1<<x) & mask) == 0 for x in range(50)])

def findFreeCell(board):
    for y in range(height):
        for x in range(width):
            if board & (1 << (x + width*y)) == 0:
                return x,y


def floodFill(board, xxx_todo_changeme):
    (x, y) = xxx_todo_changeme
    if not valid(x,y):
        return board
    if board & (1 << (x + width*y)) != 0:
        return board

    board = board | (1 << (x + width*y))

    for f in list(move.values()):
        board = board | floodFill(board, f(x,y))

    return board

def noIslands(mask):
    zeroes = zerocount(mask)

    if zeroes < 5:
        return False

    while mask != 0x3FFFFFFFFFFFF:
        mask = floodFill(mask, findFreeCell(mask))
        new_zeroes = zerocount(mask)

        if zeroes - new_zeroes < 5:
            return False

        zeroes = new_zeroes

    return True

def getBitmask(x,y,piece):
    mask = (1 << (x + width*y))

    for cell in piece:
        x,y = move[cell](x,y)
        if valid(x,y):
            mask = mask | (1 << (x + width*y))
        else:
            return False, 0

    return True, mask

def allBitmasks(piece, color):
    bitmasks = []
    for orientations in range(2):
        for rotations in range(6 - 3*(color == 4)):
            for y in range(height):
                for x in range(width):
                    isValid, mask = getBitmask(x,y,piece)
                    if isValid and noIslands(mask):
                        bitmasks.append(mask)

            piece = [rotate[cell] for cell in piece]
        piece = [flip[cell] for cell in piece]


    return bitmasks

def generateBitmasks():

    global masksAtCell

    masksAtCell = [[[] for j in range(10)] for i in range(width*height)]

    color = 0
    for piece in pieces:
        masks = allBitmasks(piece, color)
        masks.sort()
        cellMask = 1 << (width*height-1)
        cellCounter = width*height-1

        j = len(masks)-1

        while (j >= 0):
            if (masks[j] & cellMask) == cellMask:
                masksAtCell[cellCounter][color].append(masks[j])
                j = j-1
            else:
                cellMask = cellMask >> 1
                cellCounter -= 1
        color += 1


def solveCell(cell, board, n):

    global solutions, masks, masksAtCell

    if len(solutions) >= n:
        return

    if board == 0x3FFFFFFFFFFFF:
        # Solved

        s = stringOfMasks(masks)
        solutions.append(s);
        solutions.append(inverse(s));
        return

    if board & (1 << cell) != 0:
        # Cell full

        solveCell(cell-1, board, n)
        return

    if cell < 0:
        # Out of board

        return

    for color in range(10):
        if masks[color] == 0:
            for mask in masksAtCell[cell][color]:
                if legal(mask, board):
                    masks[color] = mask
                    solveCell(cell-1, board | mask, n);
                    masks[color] = 0

def solve(n):
    generateBitmasks()
    solveCell(width*height-1, 0, n)


def stringOfMasks(masks):
    s = ""
    mask = 1;
    for y in range(height):
        for x in range(width):
            for color in range(10):
                if (masks[color] & mask) != 0:
                    s += str(color)
                    break
                elif color == 9:
                    s += "."
            mask = mask << 1
    return s

def inverse(s):
    ns = [x for x in s]

    for x in range(width):
        for y in range(height):
            ns[x + y*width] = s[width-x-1 + (width - y - 1)*width]

    return s

def printSolution(solution):
    str = ""
    for y in range(height):
        for x in range(width):
            str += solution[x + y*width] + " "

        if (y%2) == 0:
            print(str)
            str = " "
        else:
            print(str)
            str = ""

if __name__ == "__main__":

    if not len(sys.argv) > 1:
        sys.exit()

    solve(int(sys.argv[1]))
    print(str(len(solutions)) + " solutions found")
    print()
    printSolution(min(solutions))
    print()
    printSolution(max(solutions))
    print()
