CP-SAT is still a glorified and optimized recursive backtracking search. There's nothing better in the literature. They call it DPLL.
It just evaluates the data and constraints to search the more obvious paths first, and cut illegal paths earlier. And some integer tricks, and a cache of learned constraints. Which the Russians found, when trying to solve Chess efficiently. IBM/Ken Thompson just threw hardware at it, while the Russians made the algorithmic advances. Just as now with LLM's. The US folks just throw hardware at it, whilst the Chinese optimize their algos.
rurban · · focus · HN ↗
It just evaluates the data and constraints to search the more obvious paths first, and cut illegal paths earlier. And some integer tricks, and a cache of learned constraints. Which the Russians found, when trying to solve Chess efficiently. IBM/Ken Thompson just threw hardware at it, while the Russians made the algorithmic advances. Just as now with LLM's. The US folks just throw hardware at it, whilst the Chinese optimize their algos.