# Tag Info

Accepted

### Aren’t most constraining variable and least constraining value the exact opposite?

Yes, these two heuristics sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least ...
• 39.1k
Accepted

### Branch and bound for minimum linear arrangement

One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage ...
• 485
Accepted

### Neural Network: Why can't we calculate derivatives during forward prop itself?

You described the simplest case of the neural network, where the center neuron has only one output $a$, which is connected to the final loss function. In general, there can be several outputs and the ...
• 640
Accepted

### Using backtracking to find all possible permutations in a string

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot ...
• 9,837
Accepted

### Binarization of Constraints

Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$. It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$. ...
• 162k

### Optimal way to find maximal sum (with constraints) of array elements

This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we ...
• 7,148

### Maximize number of museums visited in a day

The problem is strongly $NP$-complete by reduction from 3-Partition. Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each ...
• 13.3k

### Why run -time of N-Queens using backtracking algorithm fluctuates?

Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-...
• 13.3k
Accepted

### Why is backtracking a necessary step in the Maze problem?

Your question title doesn't match your question details. You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking. A ...
• 5,736

### Longest sequence of dominoes

Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of ...
• 29.5k

### Trajectories with collisions

One possible approach is to use the Bentley-Ottman algorithm (or similar algorithm) to find all intersections between line segments. More specifically: for each plasma gun, add a directed line ...
• 162k
Accepted

### How to solve a system of XOR equations in a cyclic graph?

You can express this as an instance of XOR-SAT, then find a solution using Gaussian elimination. I am assuming that each value $1,2,3,$ represents a bit-vector of some appropriate length, and you are ...
• 162k

### Minimum sum of distance from entrance gate

I will try to give a solution. Tell me if I am mistaking anywhere. First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill ...

### Time complexity of this solution to N-queens problem

Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an ...
• 30.7k
Accepted

### Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

Integer linear programming can potentially be more efficient. ILP solvers normally combine backtracking with many other methods, so for many problems ILP might be faster than backtracking alone. ...
• 162k
Accepted

### How to count the combinations not greater than a given volume in a knapsack problem?

Why did it fail? Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and ...
• 39.1k
Accepted

### SAT Solving + Turing Machines

Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything ...
• 22.6k
Accepted

### Divide an array into two sub arrays such that their sums are equal and possibly maximum

The problem is NP-hard, by a straightforward reduction from the partition problem. Therefore, you should not expect any efficient algorithm. However, there is a pseudo-polynomial-time algorithm ...
• 162k

### Why run -time of N-Queens using backtracking algorithm fluctuates?

The exponential running time of backtracking for the$N$-queens problem is an upper bound, which means that the algorithm may do better sometimes. If the algorithm is 'lucky' and tries good positions ...
• 8,303

### Line-search does not guarantee convergence so how to use it?

First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia ...

### Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack. So let us consider the $n \times n$ ...
• 22.6k

### Need recursive version of Conflict based backjumping

When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict. Instead of backtracking ...
• 8,101