3 ms·
My understanding was that there are many solvers that you can use. Do they all backtrack?
by gjem97 9y ago
My understanding was that there are many solvers that you can use. Do they all backtrack?
- jsjolen 9y agoThe goal of a constraint solver is to bind (constrain) all of the defined variables to a single value which satisfies the constraints put upon that variable. This is in essence traversing through a search tree (through DFS) and finding a valid end-node. This means that when we find an invalid end-node (for example by running out of possible values for a variable) then we must in some way go back up the search tree. There are several different ways of doing this. Short answer: Yes, we must backtrack somehow.
- CJefferson 9y agoIn some vague sense, any solver for an NP-complete problem, must either backtrack, or keep accumulating information and possibly exhaust memory. In practice every practical solver I know of for NP-complete problems backtracks. Now, they often do all kinds of other clever things on top (learning, restarts, parallelisation, heuristics), but when the going gets tough, there is a lot of backtracking.