Questions tagged [backtracking]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
9 votes
1 answer
1k views

Conflict Driven Clause Learning backtracking clarification

On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack ...
Jake's user avatar
  • 3,800
8 votes
1 answer
273 views

Branch and bound for minimum linear arrangement

I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost. Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
Bibek Bhattarai's user avatar
7 votes
2 answers
366 views

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

Assume we have a sequence of $0$s and $1$s: $n_1, n_2, ..., n_N$, in which $0$ stands for a leaf node, and $1$ stands for an uncertain node that may or may not be a leaf node. How can we check if this ...
Harold H.'s user avatar
6 votes
2 answers
7k views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
user26288's user avatar
6 votes
1 answer
6k views

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

So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
user avatar
6 votes
2 answers
3k views

How does one formulate a backtracking algorithm

I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood ...
ManMohan Vyas's user avatar
6 votes
1 answer
408 views

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

I have been studying Andrew Ng's Coursera course about Deep Learning. In that he mentions that we calculate the activation functions during the forward pass, and the derivatives $\dfrac{dL}{dz} \ $, $\...
Hemant Singh's user avatar
5 votes
2 answers
15k views

Using backtracking to find all possible permutations in a string

I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In ...
ankush981's user avatar
  • 153
4 votes
1 answer
1k views

Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
user35202's user avatar
  • 231
4 votes
0 answers
37 views

Cardinalities in set coverings

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
Matheus Diógenes Andrade's user avatar
4 votes
0 answers
78 views

(Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
ZakC's user avatar
  • 141
3 votes
2 answers
102 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
Stefan Borović's user avatar
3 votes
1 answer
893 views

Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base) -1 gap penalty -1 for a mismatch. Given two ...
andreas.vitikan's user avatar
3 votes
1 answer
37 views

Trajectories with collisions

Say that I have a plasma gun: It's easy to compute the trajectory of the plasma ray starting from the gun. However, another ray may come from afar: As everybody knows, plasma rays are deviated when ...
cdupont's user avatar
  • 131
3 votes
1 answer
16k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
Eric Z's user avatar
  • 131
3 votes
0 answers
1k views

Backtracking vs Branch-and-Bound

I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound. What confuses me: Stack Overflow: Difference between '...
Martin Thoma's user avatar
  • 2,360
2 votes
2 answers
807 views

Longest sequence of dominoes

Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
Nathaniel's user avatar
  • 15k
2 votes
1 answer
808 views

Binarization of Constraints

I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints. I've been reading ...
Johannes Heesterman's user avatar
2 votes
1 answer
2k views

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

Problem: Find the maximum sum of the elements in an array, with the following constraints: all the elements of the array are non-negative integers each element can either be left out completely from ...
Attilio's user avatar
  • 255
2 votes
2 answers
235 views

Need recursive version of Conflict based backjumping

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach? In AIMA they give the recursive ...
Cecelia's user avatar
  • 53
2 votes
1 answer
686 views

SAT Solving + Turing Machines

I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques: Randomness Heuristics Backtracking SAT is just one example ...
Schmetterling's user avatar
2 votes
1 answer
583 views

Basic question about backjumping in SAT solvers

I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić. My question is about how backjumping is defined. In an example [1], there is a conflict clause C equal to [-1,-...
user118967's user avatar
2 votes
1 answer
263 views

Ways to speed up a Recursive Backtracking Algorithm

When dealing with a Recursive Backtracking Algorithm what are the ways to speed it up and what computational hardware is involved? I'm assuming from ignorance that everything is done by the CPU so the ...
Daviid's user avatar
  • 123
2 votes
1 answer
827 views

Can memoization be applied to any recursive algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming. I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
Spindoctor's user avatar
2 votes
1 answer
3k views

Checking the validity of a pyramid of dominoes

I came across this question in a coding interview and couldn't figure out a good solution. You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level ...
Alona Korzhnev's user avatar
2 votes
1 answer
1k views

time complexity of word break algorithm

I found this question here but I don't think the answer is correct. Here is the original word break question: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence ...
ZigZagZebra's user avatar
2 votes
1 answer
271 views

Finding all soldier wins

Consider the following game (see also this question): One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the ...
user35202's user avatar
  • 231
2 votes
0 answers
43 views

Choosing a method for algorithmic problems - is it an art or science?

I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
averbin's user avatar
  • 121
2 votes
0 answers
43 views

Filling a board with maximum number of fixed size tiles

You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
CaptainTrunky's user avatar
2 votes
0 answers
2k views

DPLL time complexity analysis

Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
matheuscscp's user avatar
2 votes
1 answer
173 views

Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
user1234's user avatar
1 vote
2 answers
2k views

Maximum non-intersecting subset of circles

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$. ...
RandomStudent's user avatar
1 vote
2 answers
609 views

Best approach to resource allocation problem

Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
user2891462's user avatar
1 vote
1 answer
345 views

Why is backtracking a necessary step in the Maze problem?

The problem I am working on is specifically this: A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower ...
a_sid's user avatar
  • 113
1 vote
2 answers
3k views

Minimum sum of distance from entrance gate

Assumes we have N position, and 3 entrance gate. For example 10 position: 1--2--3--4--5--6--7--8--9--10 For each entrance gate, there is some people waiting to enter and fill positions, first number ...
Saber mim's user avatar
1 vote
1 answer
146 views

Generating hard puzzles for a backtracking snake

Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer. There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get ...
Gideon's user avatar
  • 487
1 vote
1 answer
645 views

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

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
Fish_n_Chips's user avatar
1 vote
2 answers
929 views

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

Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by ...
FiexPriceo's user avatar
1 vote
1 answer
145 views

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

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem? I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...
Andrea Nardi's user avatar
1 vote
1 answer
335 views

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

You are given a certain set of items with weight wi and the volume of the bag. Case: ...
Hearen's user avatar
  • 113
1 vote
1 answer
168 views

How is ARC consistency un-done after a recursive failure condition?

Taking this as an example: ...
T.T.T.'s user avatar
  • 113
1 vote
1 answer
697 views

Why does backtracking work the way it does?

I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking ...
andreas.vitikan's user avatar
1 vote
1 answer
226 views

Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
jakeprog123's user avatar
1 vote
1 answer
58 views

Does this LCS algo generate all the CS or only all the LCSs?

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
oldsailorpopoye's user avatar
1 vote
2 answers
1k views

Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
Hrishikesh Athalye's user avatar
1 vote
1 answer
41 views

Cracking code with clues

I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities. We have a 5 character code that is consisting of ...
james F.'s user avatar
  • 111
1 vote
1 answer
453 views

Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
Pedro Soriano Ruiz's user avatar
1 vote
1 answer
113 views

Filling a 3x3 board with connected tiles

long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern ...
flybynight's user avatar
1 vote
1 answer
1k views

Backtracking for listing k elements

Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help. Describe a back tracking algorithm for efficiently ...
Algorist's user avatar
  • 181
1 vote
0 answers
33 views

Subset sum backtracking algorithm correctness proof

I'm trying to prove that the algorithm for subset sum, that is the algorithm that given a set of numbers $\\{x_1, \dots, x_n\\}$ and a number $K$ find if there is a subset $\\{x_{1_k}, \dots, x_{n_k}\\...
aram's user avatar
  • 111