This mission is an adaptation of the "Filling" game (from Simon Tatham's Portable Puzzle Collection ). If you are lost or just want to play, the game is available here .

You have a rectangular grid with digits. You have to fill the grid with digits in such a way that each connected region (diagonally separated squares are not adjacent) of identical digits has an area equal to that common digit.

Empty cells are represented by zeros.

Note: It is possible that the solution grid contains regions without that none of its cells were given in the input grid (such as the 3s and a 1 in the first example).

[[0, 2, 0],  ===\  [[2, 2, 1],
 [0, 0, 2],  ===/   [3, 3, 2],
 [0, 1, 0]]         [3, 1, 2]]



[[1, 0, 1, 0, 1, 4, 0, 0],       [[1, 3, 1, 3, 1, 4, 4, 4],
 [3, 0, 2, 3, 0, 0, 0, 4],        [3, 3, 2, 3, 3, 5, 5, 4],
 [0, 0, 0, 1, 0, 0, 5, 1],  ===\  [4, 4, 2, 1, 5, 5, 5, 1],
 [4, 0, 1, 3, 0, 1, 0, 0],  ===/  [4, 4, 1, 3, 3, 1, 8, 8],
 [5, 0, 0, 0, 0, 0, 0, 8],        [5, 5, 5, 2, 3, 8, 8, 8],
 [0, 0, 1, 2, 1, 0, 0, 0]]        [5, 5, 1, 2, 1, 8, 8, 8]]

Input: A list of lists of integers.

Output: A list/tuple of lists/tuples of integers.

filling([[0, 2, 0], [0, 0, 2], [0, 1, 0]]) == [[2, 2, 1], [3, 3, 2], [3, 1, 2]]
filling([[1, 0, 1, 0, 1, 4, 0, 0],
         [3, 0, 2, 3, 0, 0, 0, 4],
         [0, 0, 0, 1, 0, 0, 5, 1],
         [4, 0, 1, 3, 0, 1, 0, 0],
         [5, 0, 0, 0, 0, 0, 0, 8],
         [0, 0, 1, 2, 1, 0, 0, 0]]) == [[1, 3, 1, 3, 1, 4, 4, 4],
                                        [3, 3, 2, 3, 3, 5, 5, 4],
                                        [4, 4, 2, 1, 5, 5, 5, 1],
                                        [4, 4, 1, 3, 3, 1, 8, 8],
                                        [5, 5, 5, 2, 3, 8, 8, 8],
                                        [5, 5, 1, 2, 1, 8, 8, 8]]

To play the puzzles / tests yourself: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Preconditions:

• All puzzles have one and only one solution.
• 3 ≤ len(grid) ≤ 25 and 3 ≤ len(grid[0]) ≤ 25.
• all(len(row) == len(grid[0]) for row in grid).