10x speedup: Only make valid moves

Rather than making all moves, and then checking they are valid (the
latter is expensive)