Binary sequences without two consecutive ones
Print, in lexicographic order, all the binary sequences of length n (n ≤ 15) in which there are no two neighbouring ones.
Example
Input
3Output
000
001
010
100
101Backtracking systematically tries all the possibilities, but as soon as it notices that the current attempt cannot succeed, it goes one step back and chooses another possibility. It is used for scheduling, puzzles, subsets and all the tasks in which arrangements have to be found or counted.
The solution is built step by step. In every step:
All the choices together form a search tree. Backtracking traverses it in depth, and pruning skips the branches that are known in advance not to lead to a solution.
The general form:
void search(int step) {
if (the solution is complete) {
process the solution (print it, count it…);
return;
}
for (every possibility p for this step) {
if (p is allowed) { // pruning
apply p; // choose
search(step + 1); // explore
undo p; // restore the state
}
}
}
n natural numbers and a number S are given. How many subsets have the sum exactly S? For every number we choose: we take it or not. If the current sum is already greater than S, there is no point in searching further (the numbers are positive) – that is pruning.
#include <iostream>
#include <vector>
using namespace std;
int n, S;
vector<int> a;
int solutionCount = 0;
void search(int i, int sum) {
if (sum > S) return; // pruning: we have already gone over S
if (i == n) { // we have decided about all the numbers
if (sum == S) solutionCount++;
return;
}
search(i + 1, sum + a[i]); // we take a[i]
search(i + 1, sum); // we do not take a[i]
}
int main() {
cin >> n >> S;
a.resize(n);
for (int &x : a) cin >> x;
search(0, 0);
cout << solutionCount << endl;
return 0;
}
For 2 3 5 7 8 and S = 10 the solutions are {2, 3, 5}, {2, 8} and {3, 7}. Here the state does not have to be undone explicitly, because the sum is passed as a parameter.
N queens have to be placed on an N × N board so that no two of them attack each other. We place the queens row by row; for every column we check whether it is free and whether both diagonals are free. We use three arrays of logical values for occupancy, so the check is instant.
#include <iostream>
using namespace std;
int n, placements = 0;
bool column[20], diag1[40], diag2[40]; // diag1: r + c, diag2: r - c + n
void place(int r) {
if (r == n) { // all the queens have been placed
placements++;
return;
}
for (int c = 0; c < n; c++) {
if (column[c] || diag1[r + c] || diag2[r - c + n]) continue; // an attacked square
column[c] = diag1[r + c] = diag2[r - c + n] = true; // choose
place(r + 1); // explore
column[c] = diag1[r + c] = diag2[r - c + n] = false; // undo
}
}
int main() {
cin >> n;
place(0);
cout << placements << endl;
return 0;
}
For N = 8 there are 92 placements. The task with printing the placements and a detailed explanation: N queens – solution.
In the worst case backtracking traverses the whole search tree, and it is exponentially large (2n subsets, n! permutations). That is why it is used when n is small (usually up to 20–25 for subsets, up to 10–12 for permutations) or when pruning rejects a large part of the tree. If the same states repeat during the search, dynamic programming often helps instead of backtracking.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
Print, in lexicographic order, all the binary sequences of length n (n ≤ 15) in which there are no two neighbouring ones.
3000
001
010
100
101A maze is an n × m matrix (n, m ≤ 6) in which . marks a passage, and # a wall. How many different paths are there from the top left to the bottom right cell, if you move up, down, left and right and no cell is visited twice?
3 3
...
.#.
...2n competitors (n ≤ 20) with given strengths have to be split into two teams so that the difference between the sums of the strengths is as small as possible. Print the smallest difference.
5
3 1 4 2 20bool).1. What does "undo a choice" mean in backtracking?
2. How many nodes are there on the last level of the search tree for the subsets of a set of n elements?
3. What is pruning for?