Backtracking
Depth-first search done seriously. The order a solver visits the cells is its one free choice and moves the tree size by orders of magnitude; restarts turn a heavy-tailed runtime into a portfolio. This is the family behind every record backtracker.
The order in which a backtracker visits the 256 cells is its one free choice: it costs nothing at runtime and moves the size of the search tree by orders of magnitude. Twenty years of community science, from the fixed-vs-dynamic wars and the strategy races to the magic 10×16 square and Verhaard's comb search, all answer the same question: which path through the board is cheapest?
Run the same backtracker on the same puzzle twice and the runtimes differ by powers of ten. The community measured this in 2007; the CSP literature had already named it. The cure (cut off, reshuffle, restart) is why every record solver since has been a restart portfolio.