Questions tagged [backtracking]
The backtracking tag has no usage guidance.
63
questions
0
votes
0answers
12 views
Big O of my backtracking solution
I have a problem and I've been struggling with my solution time and space complexity:
Given an array of integers (possible duplicates) A and ...
1
vote
1answer
30 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-...
0
votes
0answers
29 views
Problem with the algorithm
I am trying to execute the following algorithm shown in the image from my course slide. I am trying to get the table shown in the image:
1st Iteration
L2: 1:CS=A, SL = A, NSL = A
L3: while NSL!=[]: ...
1
vote
0answers
36 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 - ...
0
votes
0answers
21 views
Extending a solution in backtracking
Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm:
...
0
votes
2answers
81 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 ...
0
votes
0answers
41 views
The class of grammars recognizable by backtracking recursive-descent parsers
It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
1answer
94 views
Can the algorithm be optimized?
I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
0
votes
0answers
7 views
Backtracking - How do explicit constraints depend on problem instance in backtracking?
I was reading the Chapter on Backtracking in Fundamentals of Computer Algorithms by Horowitz and Sahani, and I read the following line.
The explicit constraints depend on the particular instance I ...
3
votes
0answers
552 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 '...
0
votes
1answer
41 views
Why N-Queens Problem is not used as experiment in CSP thesis?
I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems.
If so,when I do master ...
2
votes
2answers
65 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 ...
0
votes
1answer
219 views
Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour
I have implemented the basic algorithm. easily available but I am not getting the complete tour.
The visited square never equals N * N;
1
vote
2answers
85 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 ...
0
votes
2answers
765 views
How to generate all combinations given an array of elements using backtracking?
Given an array, generate all combinations
For example:
Input: {1,2,3}
Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}
I am ...
1
vote
0answers
153 views
How to approach backtracking when using immutable types (Python)? [closed]
In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
1
vote
0answers
23 views
How to rule bactrack research on alphametric puzzles?
I have a funny aphametic problem:
I A
+ I A
-----
P B
I have to find which are the values of the letters. I know I can try backtrack with forward research, MRV ...
1
vote
1answer
36 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 ...
3
votes
2answers
72 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 ...
0
votes
2answers
169 views
Why run -time of N-Queens using backtracking algorithm fluctuates?
I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$.
I think the ...
0
votes
1answer
136 views
Help with graph search problem
For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know ...
1
vote
1answer
31 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 ...
1
vote
1answer
63 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:
...
2
votes
1answer
397 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 ...
0
votes
1answer
256 views
Recursively edit 2-D array using backtracking
I have a 2-D array which contain 3 types of elements:
C (Contaminant)
R (Rock)
W (Water)
The rule is that:
contaminant can seep through water but not through rocks.
Let's say I have the ...
2
votes
1answer
2k 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 ...
0
votes
0answers
119 views
N-Queens problem - maximum number of function calls
N-Queens problem - maximum number of function calls.
We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ ...
0
votes
1answer
63 views
Interpretation of Backtracking Algorithm Problem - weighted matching
I am attempting to resolve the following problem using Backtracking:
Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ ...
-1
votes
2answers
936 views
How can I write this backtracking algorithm using dynamic programming?
Problem:
There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer ...
1
vote
1answer
247 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 ...
0
votes
1answer
91 views
Is any State Space Tree always Binary Tree?
A backtracking algorithm generates, explicitly or implicitly, a
state-space tree.
Introduction to the design & analysis of algorithms / Anany Levitin
I wonder that whether the saying always holds....
1
vote
0answers
415 views
understanding constraint satisfaction problem: map coloring algorithm
I am trying to implement this recursive-backtracking function for a constraint satisfaction problem from the given algorithm:
...
4
votes
1answer
2k 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 ...
2
votes
1answer
334 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 ...
0
votes
1answer
824 views
Divide an array into two sub arrays such that their sums are equal and possibly maximum
Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum. We are free to omit items from the subarrays.
For example, ...
2
votes
1answer
605 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 ...
1
vote
1answer
196 views
Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$
I have the following problem:
Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array ...
2
votes
0answers
33 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), ...
6
votes
1answer
139 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} \ $, $\...
1
vote
1answer
78 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 ...
4
votes
2answers
11k 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 ...
1
vote
2answers
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 ...
1
vote
0answers
194 views
How to systematically think about building implicit tree or a search space graph?
I often see DFS is used interchangeably with backtracking specially in many permutation, combinations and subset problems. But usually DFS has implicit tree and does backtracking at leaf nodes whereas ...
2
votes
1answer
438 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 ...
2
votes
1answer
967 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 ...
4
votes
0answers
71 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 ...
7
votes
1answer
176 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 , ...
2
votes
1answer
249 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 ...
3
votes
1answer
597 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 and -1 for a mismatch. Given two ...
3
votes
1answer
15k 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 ...
