I remember writing a solver for a different game, and already had a dead end check in it, but with increasing board size it took half an hour to find a solution. Then I added another check for a different dead end condition. This actually required quite a lot of additional work, more than doubling the time spent for evaluating each board state. But it brought down the time from 30 minutes to a fraction of a second!
Another possible optimisation might be to order the generated next-moves, so that the 'better' options are returned earlier in the list. Although I'm not sure what 'better' here means, exactly. But, through experimentation, one may find that visiting boards with more available options first, or vice versa(?), could produce a quicker route to the goal?
(Making it an 'informed' search, a kind of greedy/best-first depth-first search)
Example: I'm generating 5 new boards based on this one to check. In 3 of them, there is now a spot that cannot ever be reached. But the board is only half completed and from the spot I jumped to, I can still reach other places.
By trimming these options from the search at the moment of their conception, one can greatly reduce their search time.