Solution Reachability
Since ties are broken in a deterministic and unfair way (e.g., alphabetical order of state names), the next move is determined uniquely.
States can be divided into two groups: solution reachable/unreachable states (reach a solution/reach local-minima)