Comment by qbane

How about Algorithm X [0]? Fundamentally it is still a backtracking algorithm but it allows efficiently updating the solver state.

[0]: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X