Unit 18 — Backtracking

Place N chess queens on an N×N board such that no two queens attack each other. Two queens attack if they share the same row, column, or diagonal. For N=4 there are 2 solutions. For N=8 there are 92 solutions. This is the most famous backtracking problem in computer science.

#include <stdio.h>
#include <stdlib.h>
 
int N;
int queens[20];  /* queens[row] = column where queen is placed in that row */
int solutions = 0;
 
/* check if placing a queen at (row, col) is safe */
int isSafe(int row, int col) {
    int i;
    for (i = 0; i < row; i++) {
        /* same column */
        if (queens[i] == col) return 0;
 
        /* same diagonal — difference in rows equals difference in cols */
        if (abs(queens[i] - col) == abs(i - row)) return 0;
    }
    return 1;  /* safe to place */
}
 
void printBoard() {
    int r, c;
    printf("Solution %d:\n", solutions);
    for (r = 0; r < N; r++) {
        for (c = 0; c < N; c++) {
            printf("%s ", queens[r] == c ? "Q" : ".");
        }
        printf("\n");
    }
    printf("\n");
}
 
/* place queens row by row using backtracking */
void solveNQueens(int row) {
    /* base case: all N queens placed successfully */
    if (row == N) {
        solutions++;
        printBoard();
        return;
    }
 
    int col;
    for (col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            queens[row] = col;       /* CHOOSE: place queen */
            solveNQueens(row + 1);   /* EXPLORE: try next row */
            queens[row] = -1;        /* UNCHOOSE: remove queen (backtrack) */
        }
    }
}
 
int main() {
    N = 4;
    int i;
    for (i = 0; i < N; i++) queens[i] = -1;
 
    solveNQueens(0);
    printf("Total solutions for N=%d: %d\n", N, solutions);  /* 2 */
 
    /* Try N=8 */
    N = 8; solutions = 0;
    for (i = 0; i < N; i++) queens[i] = -1;
    solveNQueens(0);
    printf("Total solutions for N=%d: %d\n", N, solutions);  /* 92 */
 
    return 0;
}

Given an N×N grid where 1 = open cell and 0 = blocked wall, find a path from the top-left corner (0,0) to the bottom-right corner (N-1, N-1). The rat can move right or down only. Print the solution path. Classic backtracking — try a direction, if blocked backtrack and try another.

#include <stdio.h>
 
#define N 4
 
int maze[N][N] = {
    {1, 0, 0, 0},
    {1, 1, 0, 1},
    {0, 1, 0, 0},
    {1, 1, 1, 1}
};
 
int solution[N][N];  /* stores the path — 1 = part of path */
 
int isSafeCell(int row, int col) {
    return (row >= 0 && row < N &&
            col >= 0 && col < N &&
            maze[row][col] == 1 &&
            solution[row][col] == 0);  /* not already visited */
}
 
void printSolution() {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", solution[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
 
int solveMaze(int row, int col) {
    /* base case: reached destination */
    if (row == N-1 && col == N-1) {
        solution[row][col] = 1;
        return 1;  /* found a path */
    }
 
    if (isSafeCell(row, col)) {
        solution[row][col] = 1;  /* CHOOSE: mark cell as visited */
 
        /* EXPLORE: try moving down first */
        if (solveMaze(row + 1, col)) return 1;
 
        /* EXPLORE: try moving right */
        if (solveMaze(row, col + 1)) return 1;
 
        /* UNCHOOSE: neither direction worked — backtrack */
        solution[row][col] = 0;
        return 0;
    }
 
    return 0;  /* this cell is not safe */
}
 
int main() {
    int i, j;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            solution[i][j] = 0;
 
    if (solveMaze(0, 0)) {
        printf("Path found:\n");
        printSolution();
    } else {
        printf("No path exists\n");
    }
 
    return 0;
}

Fill a 9×9 grid with digits 1-9 such that every row, every column, and every 3×3 subgrid contains each digit exactly once. Empty cells are represented by 0. m is the number of empty cells. This is the most complex backtracking problem we cover — but the code structure is identical to N-Queens.

#include <stdio.h>
 
int board[9][9] = {
    {5,3,0,0,7,0,0,0,0},
    {6,0,0,1,9,5,0,0,0},
    {0,9,8,0,0,0,0,6,0},
    {8,0,0,0,6,0,0,0,3},
    {4,0,0,8,0,3,0,0,1},
    {7,0,0,0,2,0,0,0,6},
    {0,6,0,0,0,0,2,8,0},
    {0,0,0,4,1,9,0,0,5},
    {0,0,0,0,8,0,0,7,9}
};
 
/* check if placing num at (row, col) is valid */
int isValid(int row, int col, int num) {
    int i, j;
 
    /* check the row */
    for (i = 0; i < 9; i++) {
        if (board[row][i] == num) return 0;
    }
 
    /* check the column */
    for (i = 0; i < 9; i++) {
        if (board[i][col] == num) return 0;
    }
 
    /* check the 3x3 subgrid */
    int startRow = row - row % 3;  /* top-left row of this subgrid */
    int startCol = col - col % 3;  /* top-left col of this subgrid */
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (board[startRow + i][startCol + j] == num) return 0;
        }
    }
 
    return 1;  /* valid placement */
}
 
void printBoard() {
    int i, j;
    for (i = 0; i < 9; i++) {
        if (i % 3 == 0 && i != 0) printf("------+-------+------\n");
        for (j = 0; j < 9; j++) {
            if (j % 3 == 0 && j != 0) printf("| ");
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}
 
int solveSudoku() {
    int row, col, num;
 
    /* find the next empty cell */
    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
 
                /* try digits 1 to 9 */
                for (num = 1; num <= 9; num++) {
                    if (isValid(row, col, num)) {
                        board[row][col] = num;   /* CHOOSE */
 
                        if (solveSudoku()) return 1; /* EXPLORE — solved! */
 
                        board[row][col] = 0;     /* UNCHOOSE — backtrack */
                    }
                }
 
                return 0; /* no valid digit found — backtrack further */
            }
        }
    }
 
    return 1;  /* no empty cells left — puzzle solved */
}
 
int main() {
    printf("Solving sudoku...\n\n");
 
    if (solveSudoku()) {
        printBoard();
    } else {
        printf("No solution exists\n");
    }
 
    return 0;
}

Given a set of numbers and a target sum, find all subsets that add up to the target. Set: {3, 1, 4, 2}, Target: 5. Valid subsets: {3,2} and {1,4}. This generalises to many real problems — portfolio selection, partition problems, resource allocation.

#include <stdio.h>
 
int arr[] = {3, 1, 4, 2};
int n = 4;
int target = 5;
int subset[10];
int subsetSize = 0;
int solutionsFound = 0;
 
void printSubset() {
    int i;
    printf("  { ");
    for (i = 0; i < subsetSize; i++) printf("%d ", subset[i]);
    printf("}\n");
}
 
void findSubsets(int index, int currentSum) {
    /* base case: found a valid subset */
    if (currentSum == target) {
        solutionsFound++;
        printSubset();
        return;
    }
 
    /* pruning: sum already exceeds target — stop this path */
    if (currentSum > target || index == n) return;
 
    /* CHOICE 1: include arr[index] */
    subset[subsetSize++] = arr[index];       /* CHOOSE */
    findSubsets(index + 1, currentSum + arr[index]); /* EXPLORE */
    subsetSize--;                             /* UNCHOOSE */
 
    /* CHOICE 2: exclude arr[index] */
    findSubsets(index + 1, currentSum);      /* EXPLORE without this element */
}
 
int main() {
    printf("Subsets of {3,1,4,2} that sum to %d:\n", target);
    findSubsets(0, 0);
    printf("Total: %d subset(s) found\n", solutionsFound);
    /* Output:
       { 3 2 }
       { 1 4 }
       Total: 2 subset(s) found
    */
    return 0;
}

Generate all possible arrangements of characters in a string. "ABC" has 6 permutations: ABC, ACB, BAC, BCA, CAB, CBA. Used in: password recovery, anagram generation, combinatorics problems.

#include <stdio.h>
#include <string.h>
 
void swap(char *a, char *b) {
    char t = *a; *a = *b; *b = t;
}
 
void permutations(char str[], int start, int end) {
    /* base case: single character remaining — print the permutation */
    if (start == end) {
        printf("%s\n", str);
        return;
    }
 
    int i;
    for (i = start; i <= end; i++) {
        swap(&str[start], &str[i]);       /* CHOOSE: bring char i to front */
        permutations(str, start + 1, end); /* EXPLORE: permute the rest */
        swap(&str[start], &str[i]);       /* UNCHOOSE: restore original order */
    }
}
 
int main() {
    char str[] = "ABC";
    int n = strlen(str);
 
    printf("All permutations of '%s':\n", str);
    permutations(str, 0, n - 1);
    /* Output:
       ABC  ACB  BAC  BCA  CBA  CAB
    */
    return 0;
}