News for hackers. Stuff that matters.
Re:Solving Problems with MiniZinc by gjem97 on Monday October 23, 2017 @09:46AM (#15533097)
My understanding was that there are many solvers that you can use. Do they all backtrack?
Re:Solving Problems with MiniZinc by jsjolen on Monday October 23, 2017 @10:59AM (#15533639)
The 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.

Re:Solving Problems with MiniZinc by CJefferson on Monday October 23, 2017 @11:12AM (#15533752)
In 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.