Backtracking and Brute Force – Examples
How to practise: first try to solve the task on your own (at least on paper), then open the hint, and the solution only at the end. The solutions are mostly in C or C++; if you are learning Java or Python, rewrite the idea in your language.
Brute force
Brute force is the simplest way of solving a problem: we try all the possible options or combinations until we find the solution. It is as if we used force to get the job done – we do not try any specific clever trick, but test every possible path. This approach is easy to understand and to program, because it does not need complicated algorithmic techniques. We use brute force when there is a small number of possible solutions or when the speed of the program is not important. For example, if there are only a few possible combinations, we can check each of them.
However, for larger problems brute force can become very slow. The number of possible combinations grows quickly as the size of the problem grows, so trying every option becomes inefficient. Brute force then spends a lot of time on unnecessary checks.
Properties of the brute force method:
- It checks all the possible combinations (or results) of a problem.
- It is simple to understand and to implement.
- It works well for a small number of combinations, but becomes inefficient for larger problems.
A brute force example (C++)
For example, to find all the pairs of numbers in an array whose sum equals a given value (target), we can use brute force:
int arr[] = {1, 2, 3, 4};
int n = 4;
int target = 5;
// find pairs whose sum equals target
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (arr[i] + arr[j] == target) {
cout << arr[i] << " + " << arr[j] << " = " << target << endl;
}
}
}
Backtracking
Backtracking is a more advanced method of searching for solutions that builds possible solutions step by step. The idea is that in each step we choose one element and recursively continue. If at some moment we realise that the current combination cannot lead to a solution (e.g. some condition is not met), we take a step back and change the choice. In this way we throw away whole branches of the search for which we know they will not give a solution. This greatly reduces the number of checks compared with an ordinary brute force search.
Backtracking is often used for combinatorial problems or puzzles with extra conditions (e.g. Sudoku, N queens). It lets us quickly reject unnecessary paths and efficiently find all the solutions. Its drawback is that the implementation needs recursion and can be more complex than a simple brute force approach, but it speeds up the search a lot for problems with a large number of possibilities.
Properties of the backtracking method:
- It uses recursion and going back (backtracking) when a combination does not give a solution.
- It rejects unnecessary paths in order to be more efficient.
- It is more efficient than pure brute force for problems with many combinations, but the code is harder to write.
A backtracking example (C++)
A simple example of backtracking is generating all the subsets of a set of numbers:
vector<int> arr = {1, 2, 3};
vector<int> current;
generateSubsets(0, arr, current); // start recursion
void generateSubsets(int idx, vector<int>& arr, vector<int>& current) {
if (idx == arr.size()) {
for (int x : current)
cout << x << " ";
cout << endl;
return;
}
// skip arr[idx]
generateSubsets(idx + 1, arr, current);
// take arr[idx]
current.push_back(arr[idx]);
generateSubsets(idx + 1, arr, current);
current.pop_back();
}
Brute force vs backtracking
Both brute force and backtracking are used to search through all the possible combinations of solutions, but they do it in different ways. Brute force literally tries every possible case without any optimisation. That makes it the simplest to implement, but it quickly loses efficiency when the number of combinations grows. Backtracking, on the other hand, cleverly stops unnecessary paths as soon as it realises they do not lead to a solution. That makes it more efficient for problems with extra conditions and a large number of combinations, although its implementation needs recursion.
In practice, brute force is used when the simplicity of the solution is important or when the number of cases is really small. We use backtracking when we want to speed up the search of a large space of solutions and we can easily detect unsuccessful paths. For example, when solving a sudoku puzzle, backtracking goes back to the previous step as soon as it detects that some number cannot be placed, while brute force would keep trying all the other combinations without stopping.
- Brute force: a simple implementation, it tries all the possibilities, but it can be very slow for larger problems.
- Backtracking: a recursive method that rejects unnecessary paths, more efficient for combinatorial problems with many conditions, but the code is harder to write.
1. A path through a maze
Write a program that checks whether in a rectangular maze you can get from the top left to the bottom right corner.
Input:
From the standard input the dimensions of the maze m and n, separated by a space, are read,
and then m rows of n characters. The cells you can pass through are marked
with the character ., and obstacles with the character x.
Output:
Print yes if a path exists, or no if there is no path.
Example 1:
Input 8 8 .x.....x .x.x.x.x .x.x.x.x .x.x.x.x .x.x.x.x .x.x.x.x .x.x.x.x ...x.x.. Output yes
Example 2:
Input 8 8 .x..x..x .x.x.x.x .x.x.x.x .x.x.x.x .x...x.x .x.x.x.x .x.x.x.x ...x.x.. Output no
Hint:
- Read
mandn, then store the matrixgridof sizem×n. - Make a helper matrix
visited[m][n], initially filled withfalse. - Implement a recursive function
bool dfs(int i, int j)that:- Checks that
(i,j)is inside the borders, thatgrid[i][j]=='.'and that it has not been visited yet. - If
i==m-1 && j==n-1, returnstrue(we have reached the goal). - Marks
visited[i][j]=trueand recursively calls itself for the four neighbouring cells (up, down, left, right). - If any call returns
true, it passestrueupwards. - Otherwise it returns
false.
- Checks that
- In
main()calldfs(0,0)and, depending on the result, printyesorno.
Solution 1: a simple DFS
#include <bits/stdc++.h>
using namespace std;
int m, n;
vector<string> grid;
vector<vector<bool>> visited;
// Helper function: checks whether there is a path from (i,j) to (m-1,n-1)
bool dfs(int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n)
return false;
if (grid[i][j] == 'x' || visited[i][j])
return false;
if (i == m-1 && j == n-1)
return true;
visited[i][j] = true;
if (dfs(i+1, j)) return true;
if (dfs(i-1, j)) return true;
if (dfs(i, j+1)) return true;
if (dfs(i, j-1)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
grid.resize(m);
for (int i = 0; i < m; i++)
cin >> grid[i];
visited.assign(m, vector<bool>(n, false));
bool exists = dfs(0, 0);
cout << (exists ? "yes" : "no") << endl;
return 0;
}
Solution 2: DFS with backtracking
This example sets the visited mark back to false after all the paths from a cell have been examined, so that alternative paths can be seen too.
#include <bits/stdc++.h>
using namespace std;
// The dimensions of the maze
int m, n;
// The map of the maze
vector<string> maze;
// The matrix of visited cells
vector<vector<bool>> visited;
// Directions of movement: the four directions
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};
bool dfs(int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n)
return false;
if (maze[i][j] == 'x' || visited[i][j])
return false;
if (i == m-1 && j == n-1)
return true;
visited[i][j] = true;
for (int dir = 0; dir < 4; dir++) {
int ni = i + di[dir];
int nj = j + dj[dir];
if (dfs(ni, nj))
return true;
}
visited[i][j] = false;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
maze.resize(m);
for (int i = 0; i < m; i++)
cin >> maze[i];
visited.assign(m, vector<bool>(n, false));
bool pathExists = dfs(0, 0);
cout << (pathExists ? "yes\n" : "no\n");
return 0;
}
Explanation
dfs(i,j) first checks whether (i,j) is a valid and passable cell. If it is, and if it is the goal (m-1,n-1), it returns true.
Then it marks that cell as visited and recursively calls itself for the neighbouring cells. If any of those calls returns true, it immediately passes true on. If none of them succeeds, it backtracks (it may clear the visited mark) and returns false.
A DFS implemented like this uses the backtracking principle to try all the possible paths until it finds a successful one, or goes through the whole space and concludes that there is no path.
2. Step sequences
Write a program that prints all the step sequences of length n in lexicographic order.
A sequence is a step sequence if it starts with the number 1 and every next element is either equal to the previous one or greater by one.
Input:
One integer n (1 ≤ n ≤ 18) is entered from the standard input.
Output:
Print all the step sequences of length n, each in its own line, with the elements separated by a space.
Example:
Input 3 Output 1 1 1 1 1 2 1 2 2 1 2 3
Hint:
- Make a recursive function that builds a sequence of length
nstep by step. - The first element must be
1. For every next position first try to repeat the last value, and then to increase it by 1 (if it does not go over index+1). - When we reach
position == n, print the whole sequence and return.
Solution: step sequences (recursion)
#include <iostream>
#include <vector>
using namespace std;
// Recursive function:
// n – the wanted length of the sequence
// current – the vector in which we build the current sequence
// position – the index we are at now (0-based)
// last – the last value put into the sequence
void generateSteps(int n,
vector<int>& current,
int position,
int last)
{
if (position == n) {
for (int x : current) cout << x << ' ';
cout << '\n';
return;
}
// keep the same value
current[position] = last;
generateSteps(n, current, position+1, last);
// try the value +1 if it does not break the rule
if (last + 1 <= position + 1) {
current[position] = last + 1;
generateSteps(n, current, position+1, last+1);
}
}
int main()
{
int n;
cin >> n;
vector<int> seq(n);
// by definition, the first one is 1
seq[0] = 1;
generateSteps(n, seq, 1, 1);
return 0;
}
3. Orders of a robot's steps
From its starting position a robot made a steps to the right and b steps up (as seen on the map),
but we do not know in which order. Write a program that prints all the possible orders of the robot's steps.
If there are more than 1000 different orders, print only the first 1000.
Input:
The first and only line contains two non-negative integers, separated by one space:
a (the number of steps RIGHT) and b (the number of steps UP), both ≤ 100.
Output:
Print the required orders of steps, each in its own line.
Show every order as a sequence of the words RIGHT and UP, separated by a space,
in lexicographic order (RIGHT < UP).
Example 1:
Input 3 2 Output RIGHT RIGHT RIGHT UP UP RIGHT RIGHT UP RIGHT UP RIGHT RIGHT UP UP RIGHT RIGHT UP RIGHT RIGHT UP RIGHT UP RIGHT UP RIGHT RIGHT UP UP RIGHT RIGHT UP RIGHT RIGHT RIGHT UP UP RIGHT RIGHT UP RIGHT UP RIGHT UP RIGHT RIGHT UP UP RIGHT RIGHT RIGHT
Example 2:
Input 0 6 Output UP UP UP UP UP UP
Hint:
- Use recursion (backtracking) to build a sequence of
a+bsteps in total, step by step. - In every call we know how many RIGHT steps (
rightLeft) and UP steps (upLeft) we may still add. - First try to add
RIGHT(ifrightLeft>0), thenUP(ifupLeft>0). This guarantees the lexicographic order. - When
rightLeft==0 && upLeft==0, print the sequence and stop if we have reached the limit of 1000 printed lines.
Solution: orders of steps (backtracking)
#include <iostream>
#include <vector>
using namespace std;
const int MAX_OUTPUT = 1000; // the maximum number of orders to print
int printed = 0; // the counter of orders already printed
vector<int> order; // here we build the sequence: 0=RIGHT, 1=UP
// Recursive function that builds and prints the orders
void search(int rightLeft, int upLeft) {
if (printed >= MAX_OUTPUT) return;
if (rightLeft==0 && upLeft==0) {
// print the current one
for (int i=0; i<order.size(); ++i) {
if (i) cout << ' ';
cout << (order[i]==0? "RIGHT":"UP");
}
cout << '\n';
++printed;
return;
}
// first RIGHT (because "RIGHT" < "UP")
if (rightLeft>0) {
order.push_back(0);
search(rightLeft-1, upLeft);
order.pop_back();
}
if (printed >= MAX_OUTPUT) return;
// then UP
if (upLeft>0) {
order.push_back(1);
search(rightLeft, upLeft-1);
order.pop_back();
}
}
int main() {
int a, b;
cin >> a >> b;
search(a, b);
return 0;
}
4. Binary sequences without too many repetitions
A binary sequence is boring if more than k equal digits appear in it in a row.
A sequence is interesting if it is not boring.
Write a program that prints all the interesting binary sequences of length n in lexicographic order.
Input:
One line with two numbers n and k (1 ≤ n ≤ 20, 1 ≤ k ≤ n).
Output:
All the interesting binary sequences of length n, each in its own line, without spaces between the digits.
Example:
Input 3 2 Output 001 010 011 100 101 110
Hint:
- Use a recursive function
generate(i, last, runLength, seq, n, k)that fills the positioni. - The state:
last– the value of the previous bit (0 or 1),runLength– how many times in a rowlasthas appeared so far.- At every position first try the bit
0, then1(so that the sequences are in lexicographic order). - Adding the same bit is allowed only if
runLength < k; changing the bit always resetsrunLength = 1. - When
i == n, print the sequence and return (the base case).
Solution: generating the interesting sequences
#include <bits/stdc++.h>
using namespace std;
// Recursive function that builds the sequence:
// i – the current position (0..n-1)
// last – the value of the previous bit (0 or 1)
// runLength – how many times in a row 'last' has been repeated
// seq – a vector of length n where we keep the current sequence
// n, k – the length of the sequence and the maximum number of allowed repetitions
void generate(int i, int last, int runLength,
vector<int>& seq, int n, int k) {
if (i == n) {
// we have built the whole sequence
for (int b : seq) cout << b;
cout << "\n";
return;
}
// Try to add 0
if (last != 0) {
// the bit changes → reset the run length
seq[i] = 0;
generate(i+1, 0, 1, seq, n, k);
} else if (runLength < k) {
// the same bit, but we do not allow too many repetitions
seq[i] = 0;
generate(i+1, 0, runLength+1, seq, n, k);
}
// Try to add 1
if (last != 1) {
seq[i] = 1;
generate(i+1, 1, 1, seq, n, k);
} else if (runLength < k) {
seq[i] = 1;
generate(i+1, 1, runLength+1, seq, n, k);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> seq(n);
// Lexicographically '0...' comes before '1...', so we start with 0 first, then with 1
seq[0] = 0;
generate(1, 0, 1, seq, n, k);
seq[0] = 1;
generate(1, 1, 1, seq, n, k);
return 0;
}
5. Sequences of correctly matched brackets
Write a program that prints all the sequences of correctly matched brackets of length n and depth at most d,
in increasing lexicographic order.
Input:
The first line of the standard input contains an even number n (1≤n≤30), and the second line a natural number d (1≤d≤7).
They are chosen so that there are fewer than 2000 solutions in total.
Output:
Print all the required bracket sequences in increasing lexicographic order, each in its own line.
Example:
Input 6 2 Output (()()) (())() ()(()) ()()()
Hint:
- Notice that the sequence must contain
n/2opening andn/2closing brackets. - Keep track of three values while generating:
open– how many opening “(” we have placed;closed– how many closing “)” we have placed;depth=open−closed– the current depth;
- Recursively fill the sequence at the position
pos:- add “(” if
open < n/2anddepth+1 ≤ d; - add “)” if
closed < open;
- add “(” if
- First try the branch with “(” and then “)” to get the lexicographic order.
- Stop branching as soon as the number of printed sequences reaches 2000.
Solution: generating with a depth limit
// we include all the standard headers
#include <bits/stdc++.h>
using namespace std;
// The maximum number of sequences (given as < 2000)
const int MAX_SEQUENCES = 2000;
// The total length of the sequence (an even number) and the allowed depth
int n, d;
// The vector for the currently generated bracket sequence
vector<char> brackets;
// The counter of printed sequences
int printed = 0;
/**
* Recursive function:
* @param pos – the current position in the sequence (0..n-1)
* @param open – the number of '(' so far
* @param closed – the number of ')' so far
* @param depth – the current depth = open - closed
*/
void generate(int pos, int open, int closed, int depth) {
if (printed >= MAX_SEQUENCES) return; // stop if we have already printed the limit
if (pos == n) { // if we have filled the whole sequence
for (char c : brackets) cout << c;
cout << "\n";
++printed;
return;
}
// Try to add '(' if n/2 has not been reached and depth+1 ≤ d
if (open < n/2 && depth+1 <= d) {
brackets[pos] = '(';
generate(pos+1, open+1, closed, depth+1);
}
// Try to add ')' if there are more opening than closing brackets
if (closed < open) {
brackets[pos] = ')';
generate(pos+1, open, closed+1, depth-1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Read n and d
cin >> n >> d;
brackets.resize(n);
// Start the recursion from the beginning of the sequence
generate(0, 0, 0, 0);
return 0;
}
/*
Explanation:
- n must be even (half '(' and half ')').
- d limits the largest difference (open - closed) at any moment.
- The branch with '(' is chosen first so that, lexicographically, sequences with '(' come before those with ')'.
- The counter printed prevents going over 2000 solutions.
*/
6. The maximum safe path
There is an n × m field in which every cell contains either a mine (0) or a non-negative number.
You need to get from any cell of the first column to any cell of the last column along a safe path:
there must be no mine either in a cell of the path or in any of its neighbours (up, down, left, right).
Moving up, down, left and right is allowed, and every cell may be visited at most once.
Calculate the maximum sum of the numbers along such a safe path, or print -1 if there is no path.
Input:
The first line: two numbers m, n (1<m,n≤20).
The next n lines contain m numbers of the matrix each.
Output:
One integer – the maximum sum, or -1 if a safe path does not exist.
Example:
Input 4 4 5 1 2 0 1 2 3 4 2 4 1 1 0 1 1 1 Output 17
Hint:
- Marking the unsafe cells:
the cells with
0and their neighbours are marked in the matrixblocked. - DFS search:
- A recursion is started from every safe cell of the first column.
- The matrix
seenis kept so that we do not go round in a cycle. - In every recursion, when we reach the last column, the global maximum sum is updated – but the search does not stop there, because the path may continue along the last column and collect more points (in the example the path ends with 1 + 1 + 1 in the bottom right corner).
- Backtracking: after exploring every neighbour,
seenis cleared so that other paths are allowed. - The result:
if
besthas stayed-1, there is no path; otherwise that value is printed.
// C++ implementation of the maximal safe path problem
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m, n;
vector<vector<int>> A;
vector<vector<bool>> blocked, seen;
int best = -1;
int dx[4] = {-1, 1, 0, 0},
dy[4] = {0, 0, -1, 1};
bool valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void markBlocked() {
blocked.assign(n, vector<bool>(m, false));
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (A[i][j] == 0) {
blocked[i][j] = true;
for (int d=0; d<4; ++d) {
int ni = i + dx[d], nj = j + dy[d];
if (valid(ni,nj)) blocked[ni][nj] = true;
}
}
}
}
}
void dfs(int x, int y, int sum) {
if (!valid(x,y) || blocked[x][y] || seen[x][y]) return;
if (y == m - 1) {
// the path may end here, but it may also continue along the last column
best = max(best, sum + A[x][y]);
}
seen[x][y] = true;
for (int d=0; d<4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
dfs(nx, ny, sum + A[x][y]);
}
seen[x][y] = false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
A.assign(n, vector<int>(m));
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
cin >> A[i][j];
markBlocked();
seen.assign(n, vector<bool>(m, false));
for (int i=0; i<n; ++i) {
if (!blocked[i][0]) dfs(i, 0, 0);
}
cout << (best==-1?-1:best) << "\n";
return 0;
}
7. A coloured maze
In front of you is an m × n matrix in which every cell is painted in one of four colours: 1 (red), 2 (blue), 3 (yellow) or 4 (green). You must start on a red cell (1), and then you move following the cyclic order of colours 1→2→3→4→1→2…, only in four directions (up, down, left, right), and you may not visit any cell more than once. Check whether there is a path from any cell in the bottom row to any cell in the top row that follows these rules.
Input:
The first line: two numbers m (the number of columns) and n (the number of rows), (1 ≤ m,n ≤ 20).
The next n lines: m digits each, without spaces, that represent the colours of the cells.
Output:
Print yes if such a path exists, or no if it does not exist.
Example:
Input
6 5
143222
414344
323244
124123
343211
Output
yes
Hint:
- DFS/BFS search:
- Start from every cell in the bottom row that is coloured
1(red). - Keep a matrix
visitedso that you do not go round in a cycle. - At every step check the colour of the next cell: if you are on the colour
cnow, the allowed move is to the colour(c % 4) + 1. - If the DFS reaches any cell in the top row (
x == 0), the answer isyes.
- Start from every cell in the bottom row that is coloured
- Backtracking: after every attempt clear
visitedso that all the paths are examined. - The result: if no search succeeds, print
no.
// C++ solution for the coloured maze
#include <iostream>
#include <vector>
using namespace std;
int m, n; // the dimensions of the matrix
vector<vector<int>> colour; // the matrix of colours
vector<vector<bool>> visited; // the visited cells
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 }; // the directions of movement
bool valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
bool dfs(int x, int y) {
if (!valid(x,y) || visited[x][y])
return false;
visited[x][y] = true;
int current = colour[x][y];
int next = (current % 4) + 1;
if (x == 0)
return true; // we have reached the top row
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (valid(nx,ny)
&& colour[nx][ny] == next
&& !visited[nx][ny]) {
if (dfs(nx,ny))
return true;
}
}
visited[x][y] = false; // backtracking
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
colour.assign(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
string row; cin >> row;
for (int j = 0; j < m; ++j)
colour[i][j] = row[j] - '0';
}
visited.assign(n, vector<bool>(m, false));
bool exists = false;
for (int j = 0; j < m; ++j) {
if (colour[n-1][j] == 1) {
if (dfs(n-1, j)) {
exists = true;
break;
}
}
}
cout << (exists ? "yes\n" : "no\n");
return 0;
}
8. A falling ball
A ball is dropped from a height and falls through a space full of obstacles. When there are no obstacles under it, it falls straight down. When there is an obstacle under it, it stops, and then we can push it either left or right to the edge of the obstacle, after which it continues to fall. Write a program that determines whether the ball can reach the bottom.
Input:
A matrix of characters is read from the standard input until the end of the input (all the lines of the standard input have
the same length and represent the rows of the matrix). Neither the length nor the width of the matrix is greater than 16. Obstacles are
marked with the character x, empty cells with the character ., while the starting position of the ball is marked with the character O and
is in the top row.
Output:
Print yes to the standard output if the ball can fall to the bottom, or no if it cannot.
Example 1:
Input O.......x...x xxx.....xx..x xxx....xxx.xx xxxx........x xxxx..xx....x xxxxxxxx.xxxx Output no
Example 2:
Input .O......x...x xxx.....xx..x .......xxx.xx .xxx........x .xxxxx.x....x .xxxxxxx.xxxx Output yes
Hint:
- Reading the matrix:
- All the lines from the standard input are read into a vector of strings
grid. - Determine the number of rows
Rand the number of columnsC(the length of the first line).
- All the lines from the standard input are read into a vector of strings
- Finding the starting position:
- In the first row find the column
startCwhere the characterOis. - Replace that cell with
'.'so that falling is easier to handle.
- In the first row find the column
- Implementing the DFS search (
dfs(r,c)):- We use a two-dimensional array
visited[R][C]so that we do not explore the same state again. - The falling phase:
- Set
rr = rand then move down as long as there is'.'(empty) below. - If
rr + 1 == R(we have reached the last row), returntrue, because a path to the bottom has been found. - If
grid[rr+1][c] == 'x', the ball has stopped at(rr, c). - Finding the left and right edge of the block below:
- Set
left = cand move left as long asgrid[rr+1][left-1] == 'x'and the cellgrid[rr][left-1]in the ball's own row is empty. - Set
right = cand move right as long asgrid[rr+1][right+1] == 'x'andgrid[rr][right+1] == '.'. - Watch out: the ball rolls along its row, so a wall
xin that row stops it (that is why the answer in example 1 isno). - Try to push the ball left and right:
- If
left-1 ≥ 0andgrid[rr][left-1] == '.', recursively calldfs(rr, left-1). - If
right+1 < Candgrid[rr][right+1] == '.', recursively calldfs(rr, right+1). - If either of these recursions returns
true, returntrue. - If no push succeeds, return
false.
- We use a two-dimensional array
- The main flow of the program:
- Initialise
visitedtofalsein all the cells. - Call
dfs(0, startC)and get the resultcanReach. - Print
"yes"ifcanReach == true, otherwise"no".
- Initialise
#include <bits/stdc++.h>
using namespace std;
/*
A falling ball
A matrix of size ≤16×16, with:
- 'O' the starting position of the ball in the top row
- 'x' obstacles
- '.' empty cells
Rules:
1. The ball falls down until it meets an obstacle or the bottom of the matrix.
2. When it stops above an obstacle, it can be pushed left or right to the edge of that block of obstacles,
and then it continues to fall from that new column.
3. The goal: can the ball reach the bottom row?
*/
int R, C;
vector<string> grid;
bool visited[16][16]; // marks the states (row, column) already visited
/*
Recursive function that simulates the ball
starting from the position (r,c).
Returns true if there is a path to the bottom.
*/
bool dfs(int r, int c) {
// If we have already visited this cell, there is no need to do it again
if (visited[r][c]) return false;
visited[r][c] = true;
// Let the ball fall
int rr = r;
while (rr + 1 < R && grid[rr + 1][c] == '.') {
rr++;
}
// If it has reached the bottom
if (rr + 1 == R) return true;
// Now there is an obstacle below, at the position (rr+1,c)
// rr is the row above the block of x's
// Find the left and the right edge of that block of obstacles
int left = c, right = c;
// spread to the left (the ball rolls over the block, so its own row must be empty)
while (left - 1 >= 0 && grid[rr + 1][left - 1] == 'x' && grid[rr][left - 1] == '.') {
left--;
}
// spread to the right
while (right + 1 < C && grid[rr + 1][right + 1] == 'x' && grid[rr][right + 1] == '.') {
right++;
}
// The candidates for a new fall are:
// (rr, left-1) and (rr, right+1), if they are inside the borders and empty
// (if there is a wall 'x' in the ball's row, the ball cannot be pushed that way)
bool ok = false;
if (left - 1 >= 0 && grid[rr][left - 1] == '.') {
ok |= dfs(rr, left - 1);
}
if (right + 1 < C && grid[rr][right + 1] == '.') {
ok |= dfs(rr, right + 1);
}
return ok;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Read the whole matrix while there is input
string line;
grid.clear();
while (getline(cin, line)) {
if (!line.empty()) {
grid.push_back(line);
}
}
R = grid.size();
if (R == 0) return 0;
C = grid[0].size();
// Find the starting column 'O' in the first row
int startC = -1;
for (int j = 0; j < C; j++) {
if (grid[0][j] == 'O') {
startC = j;
break;
}
}
// Mark the starting position as empty to make the work easier
grid[0][startC] = '.';
// Clear visited
memset(visited, 0, sizeof(visited));
// Start the DFS
bool canReach = dfs(0, startC);
cout << (canReach ? "yes" : "no") << "\n";
return 0;
}
/*
Explanation of the algorithm:
1. Reading and preparation:
- All the lines are read into the vector grid.
- The dimensions R (the number of rows) and C (the number of columns) are determined.
- The column startC where 'O' stands in the top row is found.
- That cell is treated as empty '.' because the ball starts falling there.
2. The DFS search (dfs(r,c)):
- If the state (r,c) has already been visited, false is returned.
- visited[r][c] = true is marked.
- The ball falls down by changing rr while there is an empty '.' below.
If rr + 1 == R, we have reached the bottom ⇒ true is returned.
- Otherwise there is an 'x' below, at (rr+1, c).
Then the ball has stopped at (rr, c).
- The left and right edges of the continuous block of 'x' below are found:
left decreases while grid[rr+1][left-1] == 'x' and grid[rr][left-1] == '.'.
right increases while grid[rr+1][right+1] == 'x' and grid[rr][right+1] == '.'.
- The recursion is tried from the positions
(rr, left-1) and (rr, right+1), if they are inside the borders and empty '.'.
If any call returns true, true is returned.
- If none of them succeeds, false is returned.
3. The main flow:
- The array visited is initialised to false.
- dfs(0, startC) is called. If the result is true, "yes" is printed, otherwise "no".
Complexity:
- The size of the matrix is at most 16×16, so the DFS explores a limited number of states (every state is visited at most once).
- The algorithm is fast enough for every input of size ≤ 16×16.
*/
9. Placing n queens on a chessboard
Write a program that finds all the positions of n queens on a chessboard of size n × n such that no two queens attack each other.
Every row must contain exactly one queen, and no two queens may be in the same column or on the same diagonal.
A placement is represented by a sequence of n different numbers from 1 to n, where each value marks the column in which the queen stands in the matching row.
Input:
One natural number n (4 ≤ n ≤ 11).
Output:
All the possible placements of the queens, one placement per line. Every placement is printed as n numbers separated by a space, where the number at the position
i marks the column of the queen in the row i. The order of the solutions can be arbitrary.
Example:
Input 4 Output 2 4 1 3 3 1 4 2
Hint:
- Representing a placement:
the placement is kept in an array
queenCol[1..n], wherequeenCol[i]marks the column in which the queen in the rowistands. - Checking attacks:
when we place a queen in the row
iand the columnk, we check that no queen placed earlier in a rowj < ihas:queenCol[j] == k— the same column;|queenCol[j] - k| == |j - i|— the same diagonal (main or anti-diagonal).
- Backtracking:
- We start from row 1 and try to put the queen in every column from 1 to
n. - If the placement for the row
iis valid, we recursively move on to the rowi+1. - If we reach the row
n+1, it means that we have successfully placed all the queens, and we print the current solution. - After we have tried all the columns for the row
i, we go back (backtrack) to the previous row and change the column of its queen.
- We start from row 1 and try to put the queen in every column from 1 to
- Efficiency: this backtracking algorithm avoids endless checks by immediately rejecting invalid placements (a conflict), which greatly reduces the number of checks compared with "brute force".
#include <iostream>
#include <vector>
using namespace std;
// The size of the board (n ≤ 11)
int n;
// The array that keeps the column of the queen in every row (1..n)
vector<int> queenCol;
// Boolean arrays that record whether a column or a diagonal is taken
vector<bool> columnTaken;
vector<bool> diagonalTaken1; // index i - j + (n - 1)
vector<bool> diagonalTaken2; // index i + j
void printSolution() {
for (int i = 1; i <= n; ++i) {
cout << queenCol[i];
if (i < n) cout << " ";
}
cout << "\n";
}
// Checks whether it is safe to place a queen in the row i and the column k
bool canPlace(int i, int k) {
int idx1 = i - k + (n - 1); // the main diagonal
int idx2 = i + k; // the anti-diagonal
return !columnTaken[k] && !diagonalTaken1[idx1] && !diagonalTaken2[idx2];
}
// Recursive function for placing the queens
void placeQueens(int i) {
if (i > n) {
printSolution(); // a solution has been found
return;
}
for (int k = 1; k <= n; ++k) {
int idx1 = i - k + (n - 1);
int idx2 = i + k;
if (canPlace(i, k)) {
// Place the queen
queenCol[i] = k;
columnTaken[k] = true;
diagonalTaken1[idx1] = true;
diagonalTaken2[idx2] = true;
// Continue recursively
placeQueens(i + 1);
// Remove the marks (backtrack)
columnTaken[k] = false;
diagonalTaken1[idx1] = false;
diagonalTaken2[idx2] = false;
queenCol[i] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// Initialising the arrays
queenCol.assign(n + 1, 0);
columnTaken.assign(n + 1, false);
diagonalTaken1.assign(2 * n, false);
diagonalTaken2.assign(2 * n + 1, false);
placeQueens(1);
return 0;
}
For a detailed explanation of 5 variants of the solution, including code and comments, see the analysis of all 5 solutions of N queens .
10. A Sudoku solver
Write a program that solves a given Sudoku with the backtracking algorithm. A Sudoku is a 9×9 matrix that consists of 9 rows, 9 columns and 9 inner 3×3 squares. The goal is to fill the empty cells (marked with zeros) with the numbers from 1 to 9 so that the numbers do not repeat in any row, any column or any 3×3 square.
Input:
9 rows of 9 numbers, where zero marks an empty cell.
Output:
The filled Sudoku board if a solution exists, or the message No solution if the board cannot be filled.
Example:
Input: 0 0 3 0 2 0 6 0 0 9 0 0 3 0 5 0 0 1 0 0 1 8 0 6 4 0 0 0 0 8 1 0 2 9 0 0 7 0 0 0 0 0 0 0 8 0 0 6 7 0 8 2 0 0 0 0 2 6 0 9 5 0 0 8 0 0 2 0 3 0 0 9 0 0 5 0 1 0 3 0 0 Output: 4 8 3 9 2 1 6 5 7 9 6 7 3 4 5 8 2 1 2 5 1 8 7 6 4 9 3 5 4 8 1 3 2 9 7 6 7 2 9 5 6 4 1 3 8 1 3 6 7 9 8 2 4 5 3 7 2 6 8 9 5 1 4 8 1 4 2 5 3 7 6 9 6 9 5 4 1 7 3 8 2
Hint:
- The Sudoku is solved with a backtracking approach, where the program tries to fill the empty cells one by one.
- For every empty cell it checks whether it is safe to put a number from 1 to 9 there (the check is done for the row, the column and the inner 3×3 square).
- If the number is valid, the program puts it in and recursively moves on to the next empty cell.
- If it gets stuck (no number is possible), the program goes one step back (so-called backtracking) and changes the previous choice.
- When all the cells are filled, the Sudoku is solved.
// C++ solution of the Sudoku problem with the backtracking algorithm
#include <iostream>
#include <vector>
using namespace std;
// Function that checks whether a number can safely be put at the position (r, c)
bool isSafe(vector<vector<int>> &board, int r, int c, int value) {
// Checking the row and the column
for (int i = 0; i < 9; i++) {
if (board[r][i] == value || board[i][c] == value)
return false;
}
// Checking the 3×3 square
int startRow = (r / 3) * 3;
int startCol = (c / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == value)
return false;
}
}
return true;
}
// The main recursive function that tries to solve the Sudoku
bool solveSudoku(vector<vector<int>> &board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == 0) {
for (int value = 1; value <= 9; value++) {
if (isSafe(board, r, c, value)) {
board[r][c] = value;
if (solveSudoku(board))
return true;
board[r][c] = 0; // going back
}
}
return false; // no valid number
}
}
}
return true; // the board is full
}
int main() {
vector<vector<int>> board(9, vector<int>(9));
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> board[i][j];
if (solveSudoku(board)) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << board[i][j] << (j == 8 ? '\n' : ' ');
}
} else {
cout << "No solution" << endl;
}
return 0;
}
