Build boards up
Building a high-scoring board from an empty grid instead of digging with backtracking: beam search keeps the best partial boards alive and grows them cell by cell. The workhorse behind this project's from-scratch builders, and a clean illustration of why breadth alone stalls in the deep interior.
Keep the K most promising partial boards alive at once and grow them cell by cell. Beam search is the workhorse behind this project's from-scratch builders, and a clean illustration of why breadth alone stalls in the deep interior.
Slice the board into overlapping two-row bands, solve each band to perfection with a column-by-column dynamic program under beam pruning, and chain the bands top to bottom. A full board at 444 of 480 matched edges in 35 seconds, with the whole loss provably parked in the late vertical seams.