Naive Brute Force Implementation

The initial approach involves utilizing nested loops to generate all possible permutations of the digits 1 through 9. This method iterates through every possible assignment for the nine variables representing the equation ABC + DEF = GHI. For each permutation, it checks if all digits are unique and if the arithmetic condition holds true.

#include <stdio.h>

int main() {
    int digits[9];
    int used[10] = {0}; // Array to track digit usage
    int solution_count = 0;
    int val1, val2, sum_val;

    // Nine nested loops to traverse every permutation
    for (digits[0] = 1; digits[0] <= 9; digits[0]++) {
        for (digits[1] = 1; digits[1] <= 9; digits[1]++) {
            for (digits[2] = 1; digits[2] <= 9; digits[2]++) {
                for (digits[3] = 1; digits[3] <= 9; digits[3]++) {
                    for (digits[4] = 1; digits[4] <= 9; digits[4]++) {
                        for (digits[5] = 1; digits[5] <= 9; digits[5]++) {
                            for (digits[6] = 1; digits[6] <= 9; digits[6]++) {
                                for (digits[7] = 1; digits[7] <= 9; digits[7]++) {
                                    for (digits[8] = 1; digits[8] <= 9; digits[8]++) {
                                        
                                        // Reset usage tracker
                                        for (int k = 1; k < 10; k++) used[k] = 0;
                                        
                                        // Mark current digits
                                        int is_valid = 1;
                                        for (int k = 0; k < 9; k++) {
                                            if (used[digits[k]] == 1) {
                                                is_valid = 0;
                                                break;
                                            }
                                            used[digits[k]] = 1;
                                        }

                                        if (is_valid) {
                                            val1 = digits[0] * 100 + digits[1] * 10 + digits[2];
                                            val2 = digits[3] * 100 + digits[4] * 10 + digits[5];
                                            sum_val = digits[6] * 100 + digits[7] * 10 + digits[8];

                                            if (val1 + val2 == sum_val) {
                                                printf("%d + %d = %d\n", val1, val2, sum_val);
                                                solution_count++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    printf("Total solutions found: %d\n", solution_count);
    return 0;
}

Eliminating Commutative Duplicates

The brute force method produces duplicate solutions due to the commutative property of addition (e.g., A + B = C is identical to B + A = C). To resolve this, a 2D boolean array is introduced to track processed pairs, ensuring that only the first instance of a commutative pair is printed.

#include <stdio.h>

int history[1000][1000]; // Tracks seen pairs to prevent duplicates

int main() {
    int digits[9];
    int used[10] = {0};
    int solution_count = 0;
    int val1, val2, sum_val;

    for (digits[0] = 1; digits[0] <= 9; digits[0]++) {
        for (digits[1] = 1; digits[1] <= 9; digits[1]++) {
            // ... (Intermediate loops omitted for brevity) ...
            for (digits[8] = 1; digits[8] <= 9; digits[8]++) {
                
                // Check uniqueness of digits
                for (int k = 1; k < 10; k++) used[k] = 0;
                int is_unique = 1;
                for (int k = 0; k < 9; k++) {
                    if (used[digits[k]]) { is_unique = 0; break; }
                    used[digits[k]] = 1;
                }

                if (is_unique) {
                    val1 = digits[0] * 100 + digits[1] * 10 + digits[2];
                    val2 = digits[3] * 100 + digits[4] * 10 + digits[5];
                    sum_val = digits[6] * 100 + digits[7] * 10 + digits[8];

                    if (val1 + val2 == sum_val && history[val1][val2] == 0) {
                        printf("%d + %d = %d ", val1, val2, sum_val);
                        solution_count++;
                        
                        // Mark pair as seen
                        history[val1][val2] = 1;
                        history[val2][val1] = 1;
                        
                        if (solution_count % 5 == 0) printf("\n");
                    }
                }
            }
            // ... 
        }
    }
    printf("\nTotal unique solutions: %d\n", solution_count);
    return 0;
}

Recursive Backtracking Approach

To significantly reduce the search space, a recursive depth-first search (DFS) algorithm is employed. This method builds the numbers digit by digit, backtracking immediately when a digit is reused. This approach reduces the time complexity by avoiding the full 9-level loop nesting and checks validity during the construction of the solution.

#include <stdio.h>

int digits[10];
int visited[10];     // Tracks which digits are currently in use
int seen[1000][1000]; // Tracks commutative pairs
int total_solutions = 0;

void search(int depth) {
    if (depth == 7) {
        // Calculate values for the first two 3-digit numbers
        int n1 = digits[1]*100 + digits[2]*10 + digits[3];
        int n2 = digits[4]*100 + digits[5]*10 + digits[6];
        int sum = n1 + n2;
        int temp_sum = sum;

        // Check if the digits of the sum are unique and unused
        do {
            int r = temp_sum % 10;
            if (r == 0 || visited[r] != 0) {
                return; // Invalid sum digit
            }
            visited[r]++; // Temporarily mark sum digits
            temp_sum /= 10;
        } while (temp_sum != 0);

        // Ensure sum is a 3-digit number
        if (sum > 999) {
             // Cleanup and return if overflow
             temp_sum = sum;
             do { visited[temp_sum % 10]--; temp_sum /= 10; } while(temp_sum);
             return;
        }

        if (seen[n1][n2] == 0) {
            printf("%d + %d = %d ", n1, n2, sum);
            total_solutions++;
            seen[n1][n2] = 1;
            seen[n2][n1] = 1;
            if (total_solutions % 5 == 0) printf("\n");
        }

        // Backtrack: unmark sum digits
        temp_sum = sum;
        do { visited[temp_sum % 10]--; temp_sum /= 10; } while(temp_sum);
        return;
    }

    for (int i = 1; i <= 9; i++) {
        if (visited[i] == 0) {
            digits[depth] = i;
            visited[i] = 1;
            search(depth + 1);
            visited[i] = 0; // Backtrack
        }
    }
}

int main() {
    visited[0] = 1; // Prevent 0 from being used
    search(1);
    printf("\nTotal: %d", total_solutions);
    return 0;
}