It ought to be possible to generate valid states ordered by total value and lexicographical order or something.

But whether that is practical is a different matter. It does allow you to unambiguously define state #5546335 with the lowest number of bits

Although at that point, your attempts to cut the state will probably resemble a look-up table enumerating every valid board state, which obviously balloons the executable size by a large amount.

yes but there could conceivably be better tricks to discover

It's not quite literally the smallest, but the interesting question is what fraction of all states represent such unreachable states.