Reconstructing Flight Paths

The objective is to organize a list of tickets represented as [from, to] pairs into a single valid itinerary starting from JFK. All tickets must be used exactly once. If multiple valid routes exist, the lexicographically smallest one is required.

This problem involves traversing a graph where nodes are airports and edges are flights. Since we must use every edge exactly once, this resembles finding an Eulerian path. However, backtracking allows us to explore possible paths systematical.

Addressing Cyclic Dependencies To avoid infinite loops caused by cycles in the flight graph, we must track visited flights. A simple set might work, but since we need to handle multiple tickets between the same airports (multigraph), using counts is more efficient.

Data Structure Strategy Instead of removing elements from a container wich invalidates iterators, we can maintain a counter for each destination. Using std::map ensures destinations are processed in alphabetical order naturally.

class Solution {
private:
    std::unordered_map<std::string, std::map<std::string, int>> flight_connections;

    // Traverses connections to build the route
    bool dfs_traverse(int total_tickets, std::vector<std::string>& path) {
        if (path.size() == total_tickets + 1) {
            return true;
        }

        const std::string& current_airport = path.back();
        auto& next_destinations = flight_connections[current_airport];

        for (auto& [dest, count] : next_destinations) {
            if (count > 0) {
                path.push_back(dest);
                flight_connections[current_airport][dest]--;
                
                if (dfs_traverse(total_tickets, path)) return true;
                
                path.pop_back();
                flight_connections[current_airport][dest]++;
            }
        }
        return false;
    }

public:
    std::vector<std::string> find_itinerary(std::vector<std::vector<string>>& tickets) {
        flight_connections.clear();
        std::vector<std::string> current_path;
        
        for (const auto& ticket : tickets) {
            flight_connections[ticket[0]][ticket[1]]++;
        }
        
        current_path.push_back("JFK");
        dfs_traverse(tickets.size(), current_path);
        
        return current_path;
    }
};

Solving the N-Queens Problem

Place n queens on an n×n board such that no two queens attack each other. Constraints include unique rows, columns, and diagonals.

Search Space Visualization The solution space forms a tree where each level represents a row and branches represent column positions. Once a leaf node is reached with all queens placed safely, a solution is found.

Constraint Validation Before placing a queen at (row, col), verify:

1. No other queen exists in the same column above.
2. No other queen exists on the main diagonal (top-left).
3. No other queen exists on the anti-diagonal (top-right).

class Solution {
private:
    std::vector<std::vector<std::string>> final_solutions;

    // Checks safety of position based on constraints
    bool check_placement(int r, int c, int size, const std::vector<std::string>& board) {
        // Check vertical column
        for (int i = 0; i < r; ++i) {
            if (board[i][c] == 'Q') return false;
        }
        
        // Check upper-left diagonal
        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') return false;
        }
        
        // Check upper-right diagonal
        for (int i = r - 1, j = c + 1; i >= 0 && j < size; --i, ++j) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }

    void place_queens(int n, int current_row, std::vector<std::string>& layout) {
        if (current_row == n) {
            final_solutions.push_back(layout);
            return;
        }

        for (int col = 0; col < n; ++col) {
            if (check_placement(current_row, col, n, layout)) {
                layout[current_row][col] = 'Q';
                place_queens(n, current_row + 1, layout);
                layout[current_row][col] = '.'; // Backtrack
            }
        }
    }

public:
    std::vector<std::vector<std::string>> solve_n_queens(int n) {
        final_solutions.clear();
        std::vector<std::string> chess_board(n, std::string(n, '.'));
        place_queens(n, 0, chess_board);
        return final_solutions;
    }
};

Sudoku Solver Implementation

Fill a 9×9 grid with digits 1-9 so each row, column, and 3×3 subgrid contains unique numbers. Empty spots are marked with ..

Algorithm Logic Unlike N-Queens, every cell must be filled. The recursion iterates through every cell in the grid. For empty cels, try digits 1-9. If valid, recurse to the next cell. If the recursion returns false (dead end), backtrack.

Optimization via Early Return The recursive function returns a boolean. If a complete valid configuration is found, propagate true immediately up the call stack to stop further search.

class Solution {
private:
    // Validates if placing 'val' at (r, c) violates rules
    bool validate_move(int r, int c, char val, std::vector<std::vector<char>>& grid) {
        for (int i = 0; i < 9; ++i) {
            if (grid[r][i] == val || grid[i][c] == val) return false;
        }
        
        int start_r = (r / 3) * 3;
        int start_c = (c / 3) * 3;
        
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (grid[start_r + i][start_c + j] == val) return false;
            }
        }
        return true;
    }

    bool fill_grid(std::vector<std::vector<char>>& grid) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (grid[i][j] == '.') {
                    for (char k = '1'; k <= '9'; ++k) {
                        if (validate_move(i, j, k, grid)) {
                            grid[i][j] = k;
                            if (fill_grid(grid)) return true;
                            grid[i][j] = '.'; // Undo move
                        }
                    }
                    return false; // Cannot fill this cell
                }
            }
        }
        return true; // All cells filled successfully
    }

public:
    void solve_sudoku(std::vector<std::vector<char>>& board) {
        fill_grid(board);
    }
};

Applicability of Backtracking Techniques

These examples demonstrate specific patterns suitable for backtracking:

• Permutations & Arrangements: Organizing items where order matters (Itinerary).
• Constraint Satisfaction: Filling structures under strict rules without overlap (N-Queens, Sudoku).
• Subset Generation: Selecting combinations that meet criteria.

When facing problems involving exhaustive search within constraints, consider breaking the state down recursively and undoing choices when dead ends are encountered.