Puzzle

There is a particular type of puzzle where the board is a four by four grid consisting of squares that are either land ('L'), water ('W'), or occupied ('O'), and puzzle pieces consist of squares that are either missing (None), are empty (' '), contain a fish ('F'), or contain a bear ('B').

The six puzzle pieces are as follows:

pieces = [
    [
        [ 'F', 'F' ]
    ],
    [
        [ 'F', 'B' ]
    ],
    [
        [ None, ' ' ],
        [ ' ', 'B' ]
    ],
    [
        [ 'F', ' ' ],
        [ 'B', None ]
    ],
    [
        [ 'F', None ],
        [ ' ', 'B' ]
    ],
    [
        [ ' ', 'B' ],
        [ 'F', None ]
    ]
]

Notice that two pieces consist of two squares each, and the remaining four pieces consist of three squares each. These six pieces together consist of 16 squares, exactly enough to fully cover the board.

Here is an example board:

board1 = [
    [ 'L', 'L', 'W', 'L' ],
    [ 'O', 'W', 'L', 'O' ],
    [ 'W', 'L', 'W', 'W' ],
    [ 'W', 'W', 'W', 'L' ]
]

The rules for filling a board with pieces are as follows:

• The squares of different pieces cannot overlap.
• Bears must be on land; fish must be in water; neither bears nor fish fit on an occupied square.

There is one way to fill the example board:

• The first piece on the bottom row, first and second column, not rotated.
• The second piece on the bottom row, third and fourth column, not rotated.
• The third piece in the top right corner, rotated 90 degrees counterclockwise.
• The fourth piece against the left edge, second and third row, rotated 90 degrees counterclockwise.
• The fifth piece in the top left corner, rotated 180 degrees.
• The sixth piece against the right edge, second and third row, rotated 90 degrees counterclockwise.

We encode this solution into a Python value as follows:

solution = [
   [ 0, 3, 0 ], # Position of first piece: Rotation index 0, 3 rows from the top, 0 columns from the left
   [ 0, 3, 2 ], # Position of second piece: Rotation index 0, 3 rows from the top, 2 columns from the left
   [ 3, 0, 2 ], # Position of third piece: Rotation index 3 (270 degrees clockwise), 0 rows from the top, 2 columns from the left
   [ 3, 1, 0 ], # Position of fourth piece: Rotation index 3 (270 degrees clockwise), 1 row from the top, 0 columns from the left
   [ 2, 0, 0 ], # Position of fifth piece: Rotation index 2 (180 degrees clockwise), 0 rows from the top, 0 columns from the left
   [ 3, 1, 2 ]  # Position of sixth piece: Rotation index 3 (270 degrees clockwise), 1 row from the top, 2 columns from the left
]

• Develop a function piece_rotation that takes a piece given as a list of lists (like above), and returns the piece obtained by rotating the given piece 90 degrees clockwise. The given piece shall either be:
  • a list of length 1 containing a list of length 2, or
  • a list of length 2 containing lists of length 1, or
  • a list of length 2 containing lists of length 2.
• Develop a function piece_rotations that takes a piece given as a list of lists (like above), and returns a list of length 4 containing the pieces obtained by rotating the given piece 0 degrees, 90 degrees, 180 degrees, and 270 degrees clockwise, respectively.
• Develop a function piece_fits that takes a board given as a list of lists (like above), a piece given as a list of lists (as above), an occupancy matrix (a list of four lists, each containing four Booleans indicating whether the corresponding board square already has a puzzle piece on it), an integer rows_from_top, and an integer columns_from_left, and returns True if and only if the given piece can be legally put on the board (per the rules stated above) at the given number of rows from the top and the given number of columns from the left on the given board, and does not overlap with existing pieces.
• Develop a function fill_matrix that takes an occupancy matrix, a piece given as a list of lists, an integer rows_from_top, and an integer columns_from_left, and sets the cells of the occupancy matrix to True that correspond to the squares of the given puzzle, when positioned at the given number of rows from the top and columns from the left.
• Develop a function solutions_for_piece that, given a board, an occupancy matrix, and a piece given as a list of lists, returns the list of all fitting positions for that piece. A position is a list consisting of a rotation index (number of times the piece was rotated 90 degrees clockwise), a number of rows from the top, and a number of columns from the left. For example, if the piece fits at two rows from the top and one column from the left after rotating it clockwise 0 times, but also at one row from the top and zero columns from the left after rotating it clockwise 3 times, this function returns [ [0, 2, 1], [3, 1, 0] ]. Return the solutions sorted by rotation index, then by number of rows from the top, then by number of columns from the left. (Note that this is exactly the way Python sorts lists of lists by default.)
• Develop a function solutions that, given a board, returns the list of all solutions. A solution is a list of length 6, containing a position (rotation index, number of rows from the top, and number of columns from the left) for each piece, like the example solution above. Hint: one possible approach is to first compute the solutions for the first piece, each with a corresponding occupancy matrix. Then, for each of these, compute the ways it can be extended to a solution for the first two pieces. This yields a list of solutions for the first two pieces, each with a corresponding occupancy matrix. Then, for each of these, compute the ways it can be extended to a solution for the first three pieces. Et cetera. Return the solutions lexicographically sorted by the order on positions defined above, i.e. sorted first by the position for the first piece, then by the position for the second piece, etc. (This is the order you will get automatically if you follow the suggested approach, so you typically will not have to do anything special to obtain this order. Also, note that this is exactly the sort order that Python uses for lists of lists of lists by default.)

Examples:

>>> piece_rotation([['F', 'B']])
[['F'], ['B']]
>>> piece_rotation([['F'], ['B']])
[['B', 'F']]
>>> piece_rotation([['F', ' '], ['B', None]])
[['B', 'F'], [None, ' ']]
>>> piece_rotations([['F', 'B']])
[[['F', 'B']], [['F'], ['B']], [['B', 'F']], [['B'], ['F']]]
>>> piece_fits(board1, [['F', 'B']], [[True, True, True, True], [True, False, False, True], [False, True, False, True], [True, True, False, False]], 3, 2)
True
>>> piece_fits(board1, [['B', 'F']], [[True, True, True, True], [True, False, False, True], [False, True, False, True], [True, True, False, False]], 3, 2)
False
>>> piece_fits(board1, [['F', 'B']], [[True, True, True, True], [True, False, False, True], [False, True, False, True], [True, True, False, True]], 3, 2)
False
>>> piece_fits(board1, [['B', 'F']], [[False, False, False, False], [False, False, False, False], [False, False, False, False], [False, False, False, False]], 1, 0)
False
>>> piece_fits(board1, [[' ', None], ['F', 'B']], [[True, True, True, True], [False, True, True, True], [False, False, True, True], [True, True, True, True]], 1, 0)
True
>>> piece_fits(board1, [[' ', None], ['F', 'B']], [[False, False, False, False], [True, False, False, False], [False, False, False, False], [False, False, False, False]], 1, 0)
False
>>> piece_fits(board1, [['B', 'F'], [None, ' ']], [[False, False, False, False], [False, False, False, False], [False, False, False, False], [False, False, False, False]], 1, 0)
False
>>> matrix = [[True, True, True, True], [False, False, False, True], [False, False, True, True], [True, True, False, False]]
>>> fill_matrix(matrix, [[None, ' '], [' ', 'B']], 1, 0)
>>> matrix
[[True, True, True, True], [False, True, False, True], [True, True, True, True], [True, True, False, False]]
>>> solutions_for_piece(board1, [[False, False, False, False], [False, False, False, False], [False, False, False, False], [False, False, False, False]], [['F', 'F']])
[[0, 2, 2], [0, 3, 0], [0, 3, 1], [1, 2, 0], [1, 2, 2], [2, 2, 2], [2, 3, 0], [2, 3, 1], [3, 2, 0], [3, 2, 2]]
>>> solutions_for_piece(board1, [[False, False, False, False], [False, False, False, False], [False, False, True, False], [True, False, False, False]], [['F', 'F']])
[[0, 3, 1], [2, 3, 1]]
>>> solutions_for_piece(board1, [[True, True, False, False], [True, True, False, False], [True, True, False, False], [True, True, True, True]], [['F', ' '], [None, 'B']])
[[2, 1, 2]]
>>> solutions(board1)
[[[0, 3, 0], [0, 3, 2], [3, 0, 2], [3, 1, 0], [2, 0, 0], [3, 1, 2]], [[2, 3, 0], [0, 3, 2], [3, 0, 2], [3, 1, 0], [2, 0, 0], [3, 1, 2]]]
>>> board2 = [
    ['L', 'O', 'L', 'W'],
    ['L', 'L', 'L', 'L'],
    ['W', 'L', 'W', 'L'],
    ['W', 'W', 'O', 'W']
]
>>> solutions(board2)
[[[0, 3, 0], [2, 0, 2], [2, 0, 0], [2, 2, 2], [3, 1, 0], [0, 1, 2]], [[2, 3, 0], [2, 0, 2], [2, 0, 0], [2, 2, 2], [3, 1, 0], [0, 1, 2]]]