Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [backtracking]

The tag has no usage guidance.

0
votes
0answers
22 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
25 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$ ...
0
votes
0answers
82 views

Iterative Backtracking Method to Recursive Method

I have the following algorithm as a solution to a maze given the maze as a graph, the point of entry and the point of exit. I am attempting to transform this method into it's recursive equivalent. <...
-1
votes
2answers
146 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
56 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
22 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 ...
1
vote
0answers
33 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: ...
0
votes
1answer
83 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
63 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
193 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
102 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
80 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
22 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
105 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
59 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 ...
3
votes
2answers
5k 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 ...
0
votes
2answers
2k 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
99 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
147 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 ...
1
vote
1answer
370 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 ...
4
votes
0answers
56 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
122 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
244 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 ...
2
votes
1answer
425 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
11k 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 ...
2
votes
0answers
481 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$. ...
4
votes
1answer
909 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 ...
9
votes
1answer
778 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 ...
2
votes
1answer
340 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,-...
5
votes
2answers
2k 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 ...
1
vote
2answers
381 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$. ...
4
votes
2answers
5k 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 ...
0
votes
1answer
77 views

Devise a backtracking algorithm to allocate $p$ projects to $s$ students

There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all ...
1
vote
1answer
117 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 ...
0
votes
1answer
311 views

Find all non-decreasing sequences given lenght and size [closed]

I'm trying to find a solution for this exercise: Give the pseudocode of an algorithm which takes two positive integers n and k and prints all the non-decreasing sequences of length k (1,2,...,n)...
1
vote
1answer
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 ...
1
vote
1answer
566 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 ...