Skip to content

Backtracking

This page provides a brief introduction to the concept and applications of backtracking.

Introduction

Backtracking is a technique often used in Depth-First Search (DFS) and Breadth-First Search (BFS).

Its essence is: if a path is blocked, turn back.

Process

  1. Construct the state space tree;
  2. Traverse the tree;
  3. If a boundary condition is encountered, stop searching further down that branch and switch to another branch;
  4. When the target condition is met, output the result.

Example Problems

USACO 1.5.4 Checker Challenge

Consider a \(6 \times 6\) checkerboard with six pieces placed such that each row, each column, and each diagonal (including both main diagonals and all other diagonals) contains at most one piece.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
0   1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

The above layout can be described by the sequence \(\{2,4,6,1,3,5\}\), where the \(i\)-th number indicates that there is a piece in column \(a_i\) of row \(i\), as shown below:

Row index \(i\): \(\{1,2,3,4,5,6\}\)

Column index \(a_i\): \(\{2,4,6,1,3,5\}\)

This is just one possible arrangement. Write a program to find all such arrangements and output them using the above serialization method, sorted in lexicographical order. You only need to output the first \(3\) solutions and print the total number of solutions on the last line. Special attention: you need to optimize your program to ensure efficiency for larger board sizes.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// This code is a DFS implementation of the backtracking method
#include <iostream>
using namespace std;
int ans[14], check[3][28] = {0}, sum = 0, n;

void eq(int line) {
  if (line > n) {  // If n rows have been searched
    sum++;
    if (sum > 3)
      return;
    else {
      for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
      cout << '\n';
      return;
    }
  }
  for (int i = 1; i <= n; i++) {
    if ((!check[0][i]) && (!check[1][line + i]) &&
        (!check[2][line - i + n])) {  // Determine if placing at a certain position is legal
      ans[line] = i;
      check[0][i] = 1;
      check[1][line + i] = 1;
      check[2][line - i + n] = 1;
      eq(line + 1);
      // Backtrack after recursion to facilitate the next round of recursion
      check[0][i] = 0;
      check[1][line + i] = 0;
      check[2][line - i + n] = 0;
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  eq(1);
  cout << sum;
  return 0;
}
Maze

Given a maze of size \(N \times M\) with \(T\) obstacles (which cannot be passed through), start coordinates and end coordinates, and the condition that each cell can be visited at most once, find the number of distinct paths from the start to the end. Movement in the maze is allowed in four directions: up, down, left, and right, one cell at a time. It is guaranteed that the starting cell has no obstacle.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// This code is a BFS implementation using backtracking
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int n, m, k, x, y, a, b, ans;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};  // Four directions
bool vis[6][6];

struct oo {
  int x, y, used[6][6];
};

oo sa;

void bfs() {
  queue<oo> q;
  sa.x = x;
  sa.y = y;
  sa.used[x][y] = 1;
  q.push(sa);
  while (!q.empty()) {  // BFS queue
    oo now = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {  // Enumerate moving in four directions
      int sx = now.x + dx[i];
      int sy = now.y + dy[i];
      if (now.used[sx][sy] || vis[sx][sy] || sx == 0 || sy == 0 || sx > n ||
          sy > m)
        continue;
      if (sx == a && sy == b) {
        ans++;
        continue;
      }
      sa.x = sx;
      sa.y = sy;
      memcpy(sa.used, now.used, sizeof(now.used));
      sa.used[sx][sy] = 1;
      q.push(sa);  // Assume moving in this direction, push into BFS queue
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> k;
  cin >> x >> y >> a >> b;
  for (int i = 1, aa, bb; i <= k; i++) {
    cin >> aa >> bb;
    vis[aa][bb] = true;  // Obstacle positions are impassable
  }
  bfs();
  cout << ans;
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用