
Filling
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.
Examples:
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).