AIOJ

This page briefly introduces 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: go back when the path does not work.

Process

Construct the state-space tree;
Traverse it;
When a boundary condition is encountered, stop searching downward and search another branch;
When the target condition is reached, output the result.

Examples

USACO 1.5.4 Checker Challenge

There is a $6 \times 6$ checkerboard as follows. Six pieces are placed on the board so that each row, each column, and each diagonal (including all diagonals of the two main diagonals) contains at most one piece.

0   1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

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

Row number $i$ : $\{1,2,3,4,5,6\}$

Column number $a_i$ : $\{2,4,6,1,3,5\}$

This is only one way to place the pieces. Write a program to find all solutions, serialize and output them using the method above, in lexicographic order. You only need to output the first $3$ solutions and output the total number of solutions on the last line. Pay special attention: you need to optimize your program to ensure efficiency for larger board sizes.

Reference Code

// This code is a DFS implementation of backtracking
#include <iostream>
using namespace std;
int ans[14], check[3][28] = {0}, sum = 0, n;

void eq(int line) {
  if (line > n) {  // If all 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])) {  // Check whether placing here is valid
      ans[line] = i;
      check[0][i] = 1;
      check[1][line + i] = 1;
      check[2][line - i + n] = 1;
      eq(line + 1);
      // Backtrack after recursing downward for the next 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

There is an $N \times M$ maze with $T$ obstacles; obstacle cells cannot be traversed. Given the start and endpoint coordinates, and with each square allowed to be visited at most once, how many ways are there to move from the start coordinates to the endpoint coordinates? Movement in the maze has four directions—up, down, left, and right—and each move can advance only one square. The start position is guaranteed not to contain an obstacle.

Reference Code

// This code is a BFS implementation of 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 the 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 and put it into the 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 cannot be traversed
  }
  bfs();
  cout << ans;
  return 0;
}