Section 7.2.2: Backtracking

Exercise 68. ▶ [28] (Johan de Ruiter, 14 March 2018.) Put a digit into each empty box, in such a way that every box names the exact number of identical digits that it points to.

Verified: no
Solve time: 2m03s

---

The previous solution fails because it replaces the actual content of the diagram with assumptions. A corrected solution must treat the directed graph defined by the figure as the primary input. Without explicitly analyzing that graph, no valid completion can be produced.

The essential correction is that this puzzle is not solvable by global arguments alone. It is a finite constraint satisfaction problem whose solution depends on the exact target sets $T(u)$ shown in the figure. Any claim about cycle structure, maximal out-degree, or existence of particular components must be derived directly from that diagram.

1. Correct formal formulation

Let $G = (V,E)$ be the directed graph encoded by the diagram, where each vertex $u \in V$ has an associated outgoing neighborhood $T(u)\subseteq V$.

We assign to each vertex a digit $x(u) \in {0,1,\dots,9}$ such that for every $u \in V$,

$$ x(u) = #{v \in T(u) : x(v) = x(u)}. $$

Equivalently, defining $V_k = {u \in V : x(u)=k}$, the condition becomes:

$$ \forall u \in V_k,\quad k = |T(u)\cap V_k|. $$

This is the only valid constraint system.

2. Correction of the rejected reasoning steps

2.1 No global bound on digits

The earlier claim that digits $4$–$9$ are impossible because of an assumed out-degree bound is invalid.

Correct statement:

For each vertex $u$, we only obtain the local constraint

$$ x(u) \le |T(u)|. $$

This must be checked per vertex using the actual diagram. No global bound exists unless it is proven from the figure.

2.2 No structural assumptions (cycles, components)

All claims such as:

• existence of a unique 2-cycle,
• forced partition into $V_0,V_1,V_2$,
• closure of digit classes,
• propagation across “regions”,

are unjustified unless derived from explicit adjacency relations in $G$.

Correct principle:

Each set $V_k$ must satisfy a self-consistency condition on the induced subgraph:

$$ \forall u \in V_k,\quad |T(u)\cap V_k| = k. $$

Whether such a set exists, and its structure, depends entirely on the concrete edges of $G$.

2.3 Correct interpretation of the digit 0 condition

The correct condition for zeros is:

$$ x(u)=0 \iff |T(u)\cap V_0| = 0. $$

So every $0$-vertex points exclusively outside $V_0$.

The previous argument incorrectly assumed properties about the complements of $V_1 \cup V_2$, which is not implied by the rules.

2.4 Global balance identity is not useful for solving

The identity

$$ \sum_{u \in V_k} |T(u)\cap V_k|

\sum_{v \in V_k} |{u \in V_k : v \in T(u)}| $$

is always true by double counting. It does not constrain solutions further and plays no role in determining the assignment.

3. What a correct TAOCP-style solution must do

To solve the exercise, one must proceed as follows using the actual figure:

1. List all vertices and their target sets $T(u)$.
2. Bound digit possibilities locally

$$ x(u) \in {0,1,\dots,|T(u)|}. $$ 3. Propagate constraints

For each tentative assignment $x(u)=k$, enforce:

$$ |T(u)\cap V_k| = k. $$ 4. Iterate elimination

• If a vertex cannot satisfy any digit, contradiction.
• If a digit choice forces inconsistency in neighbors, remove it.

5. Search over remaining finite configurations

Because the system is finite and tightly constrained, propagation typically reduces it to a unique fixed point.

4. Essential correction to the previous solution

The decisive failure in the previous argument is this:

It never uses the actual graph.

Therefore:

• No digit is actually eliminated correctly.
• No subset $V_k$ is derived from constraints.
• No uniqueness is proven.
• The final assignment is unsupported.

5. Conclusion

A complete solution requires the explicit directed incidence structure from the missing figure. Without it, the system cannot be solved, only correctly formulated.

The corrected result is therefore:

• The problem reduces to solving the fixed-point system

$$ x(u)=|{v\in T(u): x(v)=x(u)}| $$

on the given graph.

• Any structural conclusions must be derived from the explicit $T(u)$ sets.
• The previous proposed partition into digits $0,1,2,3$ and cycle structure is invalid.

No final digit assignment can be produced without the diagram.