Skip to main content
9 votes
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 ...
John L.'s user avatar
  • 39.1k
7 votes
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 ...
Ggouvine's user avatar
  • 485
6 votes
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 ...
Maxim's user avatar
  • 640
6 votes
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 ...
fade2black's user avatar
  • 9,837
4 votes
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$. ...
D.W.'s user avatar
  • 162k
3 votes

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 ...
Draconis's user avatar
  • 7,148
3 votes

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 ...
Tom van der Zanden's user avatar
3 votes

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-...
Tom van der Zanden's user avatar
3 votes
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 ...
reinierpost's user avatar
  • 5,736
3 votes

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 ...
Steven's user avatar
  • 29.5k
3 votes

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 ...
D.W.'s user avatar
  • 162k
3 votes
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 ...
D.W.'s user avatar
  • 162k
2 votes

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 ...
User Not Found's user avatar
2 votes

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 ...
gnasher729's user avatar
  • 30.7k
2 votes
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. ...
D.W.'s user avatar
  • 162k
2 votes
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 ...
John L.'s user avatar
  • 39.1k
2 votes
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 ...
Juho's user avatar
  • 22.6k
2 votes
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 ...
D.W.'s user avatar
  • 162k
2 votes

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 ...
Discrete lizard's user avatar
  • 8,303
2 votes

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 ...
baris_esmer's user avatar
2 votes

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$ ...
Juho's user avatar
  • 22.6k
2 votes

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 ...
Kyle Jones's user avatar
  • 8,101
2 votes

Best approach to resource allocation problem

Let us first show that your proposed greedy algorithm for the second restriction is not optimal. For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $...
Watercrystal's user avatar
  • 1,526
2 votes

Longest sequence of dominoes

Regarding each given domino as an edge in a graph connecting the vertices labelled from $[\![0, k-1]\!]$, with "doubles" $\langle j,j\rangle$ handled separately, we need to answer: is the ...
Joffan's user avatar
  • 219
2 votes

Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

The problem can be shown to be weakly NP-hard by noticing that it is a generalization of partition. In particular, when $m=2$ the input set of integers is a yes instance of partition if and only if ...
Steven's user avatar
  • 29.5k
1 vote

Cracking code with clues

Your problem is a variant of Mastermind. In particular, it is "Super Mastermind". Wikipedia contains some relevant pointers, and you can find many more by searching for Super Mastermind. For example, ...
Yuval Filmus's user avatar
1 vote

Maximize number of museums visited in a day

I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day. In particular: at 11:00pm, what plan gives you the ...
Draconis's user avatar
  • 7,148
1 vote

Help with graph search problem

"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem. For this problem, think of a matrix, or a state, as a node ...
Art's user avatar
  • 133
1 vote

Filling a 3x3 board with connected tiles

There are only $9^9$ possible ways to fill each cell with one of the 9 tiles. That's a bit under 400 million possibilities. So, I suggest a simple approach: enumerate all of them, and for each, ...
D.W.'s user avatar
  • 162k
1 vote

Find if a sequence of nodes is yielded by a preorder traversal of a binary tree

The idea of construction in fade2black's answer is correct (while the pseudocode may be buggy). I rewrite it here: ...
xskxzr's user avatar
  • 7,520

Only top scored, non community-wiki answers of a minimum length are eligible