Brute Force and Recursion in C: Solving the Engine Shutdown Problem

Introduction: The Rescue Mission Problem

Imagine you're part of a rescue team on a malfunctioning boat. The engine won't shut down despite emergency switches. You have a set of actions—like spraying foam, cutting air supply, or disconnecting power—each affecting the engine temperature. The catch: the order matters because earlier actions can boost or reduce later ones. Your goal is to find the sequence that maximizes temperature drop. This is exactly the engine shutdown problem from COP3502C Project 3, a classic exercise in brute force recursion in C.

In this tutorial, we'll break down how to approach such problems, write clean recursive code, and optimize for small input sizes (n ≤ 11). We'll also relate it to modern contexts like optimizing AI training schedules or finding the best order of tasks in a game like Among Us to maximize efficiency. Let's dive in.

Understanding the Problem

You are given n actions (1 ≤ n ≤ 11). Each action i has a base temperature change (could be negative, meaning drop). Additionally, if action i is performed after action j, there is an extra temperature change (the synergy or penalty). The total temperature change for the whole sequence is the sum of base changes plus all pairwise contributions for actions that come later. We need to output the order (1-indexed) that gives the maximum total drop (most negative total).

For example, with n=3, base changes: -10, -20, 3; synergy matrix: row i, col j means effect on i when performed after j. The optimal order is 1 3 2, yielding -57 total drop.

This is a permutation optimization problem. Since n is small (≤11), brute force—trying all permutations—is feasible. 11! = 39,916,800, which is manageable in C with careful coding.

Brute Force with Recursion

We'll use recursion to generate all permutations. The recursive function will keep track of:

An array used to mark which actions are already placed.
An array order to store the current permutation.
The current depth (how many actions placed so far).
The current total temperature drop (accumulated so far).

At each step, we try all unused actions, compute the contribution of placing that action next, and recurse. When depth equals n, we have a full permutation; we compare its total with the best found so far and update if better.

Implementation in C

Let's outline the code structure. First, we read n, base changes, and the n×n synergy matrix. We'll store them in global or passed arrays.

#include <stdio.h>
#include <limits.h>

int n;
int base[12];
int synergy[12][12];
int best_order[12];
int best_total = INT_MIN;
int used[12];
int order[12];

void dfs(int depth, int total) {
    if (depth == n) {
        if (total > best_total) {
            best_total = total;
            for (int i = 0; i < n; i++) best_order[i] = order[i];
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            order[depth] = i;
            // Compute contribution: base + sum of synergies from previous actions
            int add = base[i];
            for (int j = 0; j < depth; j++) {
                add += synergy[i][order[j]];
            }
            dfs(depth + 1, total + add);
            used[i] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &base[i]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &synergy[i][j]);
    dfs(0, 0);
    for (int i = 0; i < n; i++) printf("%d ", best_order[i] + 1);
    printf("\n");
    return 0;
}

This code tries all permutations. Note: we add 1 to indices when printing to match 1-indexed output.

Optimization and Pitfalls

For n=11, recursion depth is 11, which is safe. However, 11! ≈ 40 million recursive calls might be borderline in time if not optimized. We can prune if we know the maximum possible remaining contribution, but given constraints, the simple version often passes.

One common mistake: forgetting that base changes are always added, regardless of order. The synergy only applies when action i is after action j. Our code correctly adds base[i] each time we place action i, and adds synergies from all previously placed actions.

Another pitfall: using 0-indexed arrays but outputting 1-indexed. Always convert when printing.

Connecting to Real-World Trends

This brute-force approach mirrors how AI models explore hyperparameter combinations to maximize accuracy. For instance, in training a large language model like GPT-4, the order of training data (curriculum learning) can affect performance. Similarly, in esports, the sequence of power-ups or abilities in a game like League of Legends can determine victory. Even in finance, the order of executing trades can impact profit due to market impact. Understanding recursion and permutation generation is foundational for such optimization tasks.

Testing with Sample Input

Let's test with the first sample:

Our code should output 1 3 2 (or 1 3 2 as indices starting from 1). For the second sample, it should output 1 4 2 3.

Conclusion

Brute force with recursion is a powerful technique for small search spaces. The engine shutdown problem teaches you to model sequential decisions with dependencies, generate permutations systematically, and compute cumulative scores. This skill transfers to many areas: scheduling, logistics, game AI, and even bioinformatics where the order of genetic markers matters. Practice this pattern, and you'll be ready for more complex backtracking problems.

Remember: when n is small (≤11), brute force is your friend. For larger n, you'd need dynamic programming or heuristics, but that's another lesson. Happy coding!