# -------------------------------------------------
# A rectangular board is given.
# Also, a  set of rectangular tiles is given.
# The problem is to list all possible tilings of the board 
# by the given tiles. 
# The tiles cannot overlap each other on the board
# and also all tiles must be used.
# -------------------------------------------------

# The board
#         0    1   2   3   4   ...  X axis
#      +---+---+---+---+---+---+---+
#   0  |   |   |   |   |   |   |   |
#      +---+---+---+---+---+---+---+
#   1  |   |   |   |   |   |   |   |
#      +---+---+---+---+---+---+---+
#   2  |   |   |   |   |   |   |   |
#      +---+---+---+---+---+---+---+
#  ... |   |   |   |   |   |   |   |
#      +---+---+---+---+---+---+---+
#  Y axis

# A tile is represented as a pair [height, width]
# Note, we do not register the tile position on the board as a part of information about the tile,
#  this information is stored on the board.
# Later, in more complex problems, it may be useful to store the tile position separately
# or in the tile object/record. However, here it would not help.


def canPutTile( tileNo, posY, posX ): # position is bottom right corner of the tile on the board
    global tileList, board
    currTile = tileList[tileNo] 
    tileULcornerY = posY - currTile[0] + 1
    tileULcornerX = posX - currTile[1] + 1
    if tileULcornerY < 0 or tileULcornerX < 0: return False
      
    for y in range( tileULcornerY, posY+1 ):
        for x in range ( tileULcornerX, posX+1 ):
            if board[y][x] != freeSpace:
                return False
    return True
        
def putTile( tileNo, posY, posX ):
    global tileList, board
    currTile = tileList[tileNo] 
    for y in range( posY - currTile[0] + 1, posY+1 ):
        for x in range ( posX - currTile[1] + 1, posX+1 ):
            board[y][x] = tileNo

def liftTile( tileNo, posY, posX ):
    global tileList, board
    currTile = tileList[tileNo] 
    for y in range( posY - currTile[0] + 1, posY+1 ):
        for x in range ( posX - currTile[1] + 1, posX+1 ):
            board[y][x] = freeSpace

# produce a humanly readable output
def printBoard():
    global counter
    counter += 1
    print( '+' + ('-' * (len(board[0])*2) ) + '-+' )
    for y in range( len(board) ):
        print( '| ', end = '' )
        for x in range ( len(board[y]) ):
            symbol = '.'
            if board[y][x] != freeSpace:
              symbol = str( board[y][x] )
            print( symbol+' ', end = '' )
        print( '|' )
    print( '+' + ('-' * (len(board[0])*2) ) + '-+ ' + str(counter) )

# ========== main recursive function ================
def tileBoard( currTileNo ):
    if currTileNo == len( tileList ):
        printBoard()
        return            
    for posY in range( len(board) ):
        for posX in range ( len(board[posY]) ):
            if canPutTile( currTileNo, posY, posX ):
                putTile( currTileNo, posY, posX )
                tileBoard( currTileNo + 1 )
                liftTile( currTileNo, posY, posX )
                

freeSpace = -1
tileList = [ [3, 3], [2,2], [2,2], [2,1], [3,2] ]
boardHeight, boardWidth = 5, 5
board = [ [freeSpace] * boardWidth for k in range(boardHeight) ]
counter = 0

tileBoard( 0 )