Reduce the search
Everything that throws away hopeless states before the search wastes time on them: propagation to a fixed point, the all-different matching filter, learned no-goods, and the edge-slipping invariant.
Forward checking looks one move ahead; arc consistency makes every cell's candidate list defend itself against every neighbour's, to a fixed point. Mackworth's AC-3, the optimal refinements that followed, and what the whole family actually measured on this puzzle, including where it is unsound.
No piece may be used twice: one global all-different constraint over 256 cells. Jean-Charles Régin showed in 1994 how bipartite matching filters it completely in polynomial time; its per-colour cousin is the strongest propagator anyone has measured on edge matching, with one sharp caveat about mismatch-tolerant searches.
Louis Verhaard's prize-winning move: let the backtracker place a mismatched piece, but only at chosen depths near the end of the board. Each allowed slip costs one point of score and multiplies the number of target boards astronomically. That is why his 467 was found more than fifty times, and the direct ancestor of Blackwood's breaks.
A failed subtree is a theorem: this partial state can never extend. Store it and never re-enter. The community tried both flavours: chess-style transposition tables over the search frontier, and mined constraints about the puzzle itself. The full ledger of what memory buys at E2 scale, and the small boards where it genuinely pays.