Questions tagged [backtracking]
The backtracking tag has no usage guidance.
77
questions
1
vote
1
answer
90
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 ...
- 13
1
vote
1
answer
90
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 ...
- 43
1
vote
0
answers
19
views
Find optimal starting point of recursive search, with solution known
An Exact Cover problem is commonly denoted as a matrix of 0s and 1s. Columns denote requirements, rows denote possible choices. The problem is solved when a set of rows was found such that, using just ...
- 319
0
votes
1
answer
78
views
Time Complexity - Palindrome Partition
I am solving an interview practice question:
Partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
My solution is as below, and was ...
- 3
1
vote
0
answers
788
views
Minimum no of swaps to be done in an array such that, no two adjacent elements are same
Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-
n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or
a[5] )
n = 8,...
- 31
0
votes
0
answers
19
views
How do I group elements of a list into windows of predefined sizes with minimum cost given longer windows are cost efficient?
You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. ...
- 1
0
votes
0
answers
45
views
Complexity of backtracking to find power set given random array of numbers
Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.
...
- 23
2
votes
2
answers
321
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 ...
- 6,942
-2
votes
1
answer
183
views
recurrence relation for this n queen problem algorithm . and the time complexity
I am not able to understand how to write a recurrence relation for this n queen problem algorithm down below. Recurrence relation is for n*n board and the time complexity
...
- 11
0
votes
0
answers
47
views
How to solve this combinatoric problem without bruteforce
I'm trying to solve the following problem :
A tile results of a number and a color.
a tile can be black, red, orange or blue.
a tile number is >= 1 and <= 15.
Given a random set a tiles (a ...
0
votes
0
answers
22
views
I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]
I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
1
vote
2
answers
148
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 ...
- 163
1
vote
1
answer
197
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 ...
- 113
0
votes
0
answers
39
views
Maximize Possible Subset Sums of A Multiset
The following problem is a problem I faced in one of my coding competitions.
Given two positive integers $N$, $M$. You can have $M$ distinct types of stones, for which different types of stones must ...
0
votes
0
answers
42
views
Number of Hamilton paths in graphs
I am trying to find a fast algorithm that can compute the number of hamiltonian paths in an undirected graph. I saw this on the web, but it sounds like this finds all hamiltonian paths starting from ...
- 101
1
vote
1
answer
48
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-...
- 194
0
votes
0
answers
31
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!=[]: ...
- 249
2
votes
0
answers
41
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 - ...
- 21
0
votes
0
answers
60
views
Extending a solution in backtracking
Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm:
...
- 101
1
vote
2
answers
747
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
0
answers
60
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 ...
- 203
1
vote
1
answer
112
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 ...
- 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 '...
- 2,280
0
votes
1
answer
51
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 ...
- 43
2
votes
2
answers
178
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 ...
- 43
0
votes
1
answer
483
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
2
answers
424
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 ...
- 11
0
votes
2
answers
1k
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 ...
- 101
1
vote
0
answers
233
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 ...
- 11
1
vote
0
answers
26
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
1
answer
39
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 ...
- 111
3
votes
2
answers
83
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
2
answers
437
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 ...
- 43
0
votes
1
answer
192
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 ...
- 31
1
vote
1
answer
58
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 ...
- 200
1
vote
1
answer
176
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:
...
- 113
2
votes
1
answer
677
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 ...
- 131
0
votes
1
answer
449
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 ...
- 111
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 ...
0
votes
0
answers
166
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$ ...
- 101
0
votes
1
answer
76
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$ ...
- 105
-1
votes
2
answers
1k
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 ...
- 439
1
vote
1
answer
372
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
1
answer
161
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....
- 115
1
vote
0
answers
444
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:
...
- 19
4
votes
1
answer
4k
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 ...
user94485
2
votes
1
answer
534
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 ...
- 103
0
votes
1
answer
1k
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, ...
- 125
2
votes
1
answer
1k
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 ...
- 255
1
vote
1
answer
268
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 ...
- 125