Eliminating invalid moves is not a "premature optimization", but is at the heart of heuristic search. By eliminating impossible/invalid states, you eliminate them from the search space, which not only speeds things up, but prevents the discovery of an invalid "solution". Put another way, discarding invalid moves reduces the branching factor of the problem -- a fundamental optimization.