Why can the "Wave Function Collapse" algorithm fail?

I have written a few implementations of Wave Function Collapse based on the README of this repo.

My understanding is that the state of each position during the computation is a superposition (set) of tiles that could be placed there, and still follow the constraints.

The README notes that sometimes the algorithm will encounter a contradiction, and cannot continue. My implementations show this.

Given a set of constraints that is solvable, my question is:

Because the state of each position is a superposition of states that would be allowed in that position, how could this cause a contradiction?

All the states that could be chosen for collapse could work, or else they would not be part of the superposition. How could they cause a contradiction if they follow the constraints?

I think it's best to think through a specific simple example. Here is a diagram showing exactly how the algorithm fails. This is in Figure 3.5 of my PhD dissertation. The Wave Function Collapse algorithm is based on the Model Synthesis Algorithm which is based on AC-4 which stands for "Arc Consistency". All the algorithm guarantees is that there is a consistent path or arc between all of the values.

Here is a simple diagram:

The wave function is shown in (d). If we select the 1 label in the bottom right corner, the algorithm will fail. But notice that there is a valid path from the 1 label to every single label in the diagram. Two of these paths are shown in (h) and (i). Each of those paths is a consistent paths from the 1 label to the 2 labels. But those paths are inconsistent with each other and cannot both be simultaneously true as they put a 3 label and 7 label in the same spot.

So why not come up with an algorithm that only allows valid possibilities? Unfortunately, that has been shown to be an NP-hard problem; see Theorem 3.3.4 of my dissertation. This means it would be extremely slow to construct such an algorithm.