# Tagged Questions

The tag has no usage guidance.

224 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 ...
8 views

### Why to use Gashnig's algorithm instead of forward checking?

Gaschnig's algorithm operates in such a way that if trying to assign a value to a leaf no consistent assignment can be done, we back-jump to the last node n that made a leaf to be inconsistent. ...
67 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 ...
1k 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 ...
111 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$. ...
440 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 ...
167 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 ...
119 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,-...
459 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 ...
162 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$. ...
2k 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 ...
40 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 ...
74 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 ...
45 views

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

Taking this as an example: ...
191 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,...,...