Fillomino solutions redux

Relevant wiki: Depth-first Search

This is a more difficult version of the previous problem; instead of $2 \times 3$ , we have $3 \times 3$ . The solution is thus to use programming, a simple exercise in brute force:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import itertools

def size(G, x, y):
    q = [(x, y)]
    S = [[0] * len(G[0]) for _ in range(len(G))]
    ans = 0
    while q:
        i,j = q.pop()
        if S[i][j]: continue
        if G[i][j] != G[x][y]: continue
        S[i][j] = 1
        ans += 1
        if i > 0: q.append((i-1, j))
        if j > 0: q.append((i, j-1))
        if i < len(G)-1: q.append((i+1, j))
        if j < len(G[0])-1: q.append((i, j+1))
    return ans

def check(G):
    for i in range(len(G)):
        for j in range(len(G[0])):
            if size(G, i, j) != G[i][j]: return False
    return True

def solve(candidates, r, c):
    ct = 0
    for k in itertools.product(candidates, repeat=r*c):
        G = [k[i*c:(i+1)*c] for i in range(r)]
        if check(G): ct += 1
    return ct

print(  solve([1,2,3,4,5], 3, 3)
      + solve([1,2,3,6], 3, 3)
      - solve([1,2,3], 3, 3)
      + solve([1,2,7], 3, 3)
      + solve([1,8], 3, 3)
      + solve([9], 3, 3)
)
# prints 445

Here, size(G, x, y) takes a two-dimensional list (supposedly the grid) and returns the "size" of the polyomino containing the square $(x,y)$ . (Here $x$ is the row number and $y$ is the column-number, both zero-indexed. The polyomino is the largest region containing all the same element.) This is just a simple depth-first-search -based flood fill , keeping track of the size.

check(G) is the checking algorithm, testing whether the grid G is a valid Fillomino solution. The idea is simply to check whether the size of each square is equal to the number written in the square.

solve(candidates, r, c) is a simple function to compute the number of solutions for a given candidate list for an $r \times c$ rectangle. The idea is just to brute force: each cell is attempted with each possible number, and the result is checked with check .

At this point, it's actually possible to solve simply with solve([1,2,3,4,5,6,7,8,9], 3, 3) ; however, it takes a long time, so some speedup is required. My speedup is to notice that:

• If there's a 9-mino, then the whole square is a single 9-mino, thus the only candidate is $9$ .
• If there's a 8-mino, then the rest can only be a 1-mino, so the candidates are $1, 8$ .
• If there's a 7-mino, the rest is a 1-mino or a 2-mino. The candidates are thus $1, 2, 7$ .
• If there's a 6-mino, the rest is made up of 1-mino, 2-mino, or 3-mino. However, this will also count solutions that doesn't include any 6-mino, so we need to subtract by that much (we'll count them later). This explains the intriguing term solve([1,2,3,6], 3, 3) - solve([1,2,3], 3, 3) .
• Otherwise, the largest mino has size at most 5, so we just do a single sweep of all these candidates: $1, 2, 3, 4, 5$ .

On my machine, this runs for approximately 20 seconds. Still long, but at least far better than attempting the naive solve([1,2,3,4,5,6,7,8,9], 3, 3) .

The result is $\boxed{445}$ .