The Organic Combination of Generation and Testing - Backtracking

AI Translated from Chinese

Introduction

Brute-force search (also known as exhaustive search, or generate-and-test in computer science) is a “simple and brutal” way to solve problems by enumerating all possibilities and checking if they meet the requirements to find the answer.

But sometimes direct enumeration causes problems: the enumeration amount is too large with many unnecessary enumerations, leading to excessive time complexity (too inefficient). Is there a better method?

Backtracking is a type of brute-force search that organically combines search and testing in recursive construction, thereby reducing the enumeration amount.

Let us experience the charm of backtracking through several classic problems.

N-Queens Problem

This is arguably one of the most classic problems. It’s often used as a criterion for “whether you’ve learned backtracking” (as Teacher Liu says)

How can eight queens be placed on an 8×8 chessboard so that no queen can directly capture another queen? To achieve this, no two queens can be on the same row, column, or diagonal. The N-Queens problem can be generalized to placing n queens on an n×n chessboard. The problem has a solution if and only if n = 1 or n ≥ 4. — From Wikipedia - Eight queens puzzle

And we need to solve the generalized N-Queens problem. But for convenience, the following analysis still uses the Eight Queens problem as an example.

Approach 1: Combination Generation

Enumerate all possible board states and then check if they meet the requirements.

The problem can be transformed into: selecting 8 squares from 64 (i.e., combination generation), ensuring no two squares are on the same row, column, or diagonal.

According to combinatorics, there are $ C_{64}^{8} = 4.426 \times 10^9 $ solutions, which is clearly too complex.

Approach 2: Full Permutation Generation

With a little thought, we can improve the strategy: select exactly one square per row and column, ensuring no two squares are on the same diagonal. This transforms into a full permutation generation problem, reducing the number of solutions to $ 8! = 40320 $, a visible efficiency improvement (lol).

We can use C[x] to represent the column number of the queen in row x. One difficulty is how to determine if queens attack each other diagonally.

Treating the board as a Cartesian coordinate system with the top-left corner as the origin, x-axis going down, y-axis going right, the board’s main diagonal is $ y = x $. Therefore, for cell $(x, y)$, the value $ y-x $ identifies the main diagonal (make sure you understand this!). Similarly, the anti-diagonal is $ y = -x $, and $ x+y $ marks the anti-diagonal. As shown below:

Backtracking

Next, we use backtracking:

所谓的回溯（backtracking）,就是指在递归求解问题时,如果当前步骤没有合法选择,则函数返回上一级递归调用

Simply put, the problem is divided into several steps for recursive solution. When a step doesn’t meet the requirements, we stop and return to the previous step. This greatly reduces computation.

Let’s look at the code.

Basic Backtracking

nqueens_1.cpp

// N-Queens problem: Place n queens on an n×n chessboard so they don't attack each other, find all solutions
#include <iostream>
#include <cstring>
using namespace std;

int C[50], tot = 0, n = 8, nc = 0;
// C[x] represents the column number of the queen in row x
void search(int cur)
{
    nc++;  // Recursion count
    if (cur == n) tot++;  // Recursion boundary. Since we've reached here, all queens are non-conflicting
    // if (cur == n)  // Print solution
    // {
    //     printf("Solution %d: ", tot);
    //     for (int i = 0; i < n; i++)
    //         printf("(%d,%d) ", i, C[i]);
    //     printf("\n");
    // }
    else for (int i = 0; i < n; i++)
    {
        int ok = 1;
        C[cur] = i;  // Try placing the queen in row cur at column i
        for (int j = 0; j < cur; j++)  // Check if it conflicts with previous queens
            // For (x,y), y-x is the main diagonal, y+x is the anti-diagonal
            if (C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j])
                { ok = 0; break; }
        if (ok) search(cur+1);  // If legal, continue recursion
    }
}
int main()
{
    while (cin >> n)
    {
        search(0);
        cout << "Number of solutions: " << tot << endl;
        cout << "Recursion count: " << nc << endl;
        nc = 0; tot = 0; memset(C, 0, sizeof(C));
    }
    return 0;
}

This solves the problem. The number of nodes seems hard to reduce further, but efficiency can still be improved!

Optimized Backtracking

Using a 2D array vis[2][] to store states, we can directly check if the current attempted queen’s column and two diagonals already have other queens. Since $ y-x $ can be negative, we add n when storing (array indices cannot be negative).

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int C[50], vis[3][50], tot = 0, n = 8, nc = 0;
// Use 2D array vis[2][] to directly check if the column and diagonals of the current attempted queen have other queens
void search(int cur)
{
    int i;
    nc++;
    if (cur == n) tot++;
    // if(cur == n)
    // {
    //     printf("Solution %d: ", tot);
    //     for (int i = 0; i < n; i++)
    //         printf("(%d,%d) ", i, C[i]);
    //     printf("\n");
    // }
    else for(i = 0; i < n; i++)
    {
        if (!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n])
        {
            C[cur] = i;  // If not printing solutions, the entire C array can be omitted
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;  // Visit flag
            search(cur+1);
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;  // Restore in time!
        }
    }
}

int main()
{
    while (cin >> n)
    {
        memset(vis, 0, sizeof(vis));
        search(0);
        cout << "Number of solutions: " << tot << endl;
        cout << "Recursion count: " << nc << endl;
        tot = 0; nc = 0;
    }
    return 0;
}

Pay attention to setting visit flags, i.e., modifying auxiliary global variables (array vis), and restoring them in time after finishing the visit!

Generate-Test Method

For comparison, let’s see the efficiency of the generate-test method.

nqueens_3.cpp

#include <iostream>
#include <cstring>
using namespace std;

int C[50], tot = 0, n = 8;
long long nc = 0;
// First generate the board, then check
void search(int cur)
{
    int i, j;
    nc++;
    if(cur == n)
    {
        for(i = 0; i < n; i++)
            for(j = i+1; j < n; j++)
                if(C[i] == C[j] || i-C[i] == j-C[j] || i+C[i] == j+C[j]) return;
        tot++;
    }
    else for(i = 0; i < n; i++)
    {
        C[cur] = i;
        search(cur+1);
    }
}

int main()
{
    while (cin >> n)
    {
        memset(C, 0, sizeof(C));
        search(0);
        cout << "Number of solutions: " << tot << endl;
        cout << "Recursion count: " << nc << endl;
        tot = 0; nc = 0;
    }
    return 0;
}

Let’s compare the efficiency of these programs (test device CPU: i9-12900H):

Recursion Count

Time (seconds)

When $ n \leq 13 $, backtracking and optimized backtracking have good efficiency; when $ n > 13 $, optimized backtracking is significantly more efficient.

The generate-test method has significantly higher complexity; at $ n = 10 $, it takes about a minute and a half, and the recursion count far exceeds the range of INT type.

Python Code

nqueen.py

def print_solve():
    global tot, n, C
    print(f"Solutions: {tot}")
    for i in range(n):
        print(f"({i},{C[i]})", end=" ")
    print()


def search(cur):
    global C, vis, tot, n, nc
    nc += 1
    if cur == n:
        tot += 1
        if cur == n:
            print_solve()
    else:
        for i in range(n):
            if vis[0][i] == 0 and vis[1][cur+i] == 0 and vis[2][cur-i+n] == 0:
                C[cur] = i
                vis[0][i] = 1
                vis[1][cur+i] = 1
                vis[2][cur-i+n] = 1
                search(cur+1)
                vis[0][i] = 0
                vis[1][cur+i] = 0
                vis[2][cur-i+n] = 0


while 1:
    C = [0]*30
    vis = [[0]*30 for _ in range(3)]
    tot = 0
    n = 0
    nc = 0
    try:
        n = int(input())
    except:
        print("error.")
    search(0)
    print(f"Number of solutions: {tot}")
    print(f"Recursion count: {nc}")

Efficiency improvement is dramatic! Go try it!

(To be continue…)

Added some math formulas (finally learned how to use LaTeX) — 2023/01/12

Appendix

References

1. Liu Rujia “Algorithm Competition Introduction Classic (2nd Edition)”
2. Wikipedia - Brute-force search
3. Wikipedia - Backtracking
4. Wikipedia - Eight queens puzzle