Effective backtracking algorithm

Your program generates all possible permutations and then tests whether the permutation is valid. The test itself involves nested loops. You could try optimize your data structures, so that your checks are more efficient or you could try to find dead ends in the search space early, as Photon suggests.

A more efficient approach might be to design the program so that only valid permutations are created.This reduces the search space and also gets rid of the tests.

If you look at the example in the problem description, the wrie network is an acyclic graph:

                            5          
                            |         
                        1   6
                        |   |
                    0---2---7
                        |   |
                        3   8               
                        |
                        4

If you start with tool 0 and put it in slot 0, the next step is to place a permutation of tool 2 and its "descendants", that is of tools 1, 7 and 3 and its respective connected tools. From the perspective of tool 0, you can turn this into a tree:

                  [1237]
                / /  |  \
              1  2  [34] [678]
                   / |    |  \ \
                  3  4   [56] 7  8
                          | \
                          5  6

Here, the leaves correspond to just a single tool. The branches have several tools. All prumutations of the branches form valid arrangements.

0 (1 2 (3 4) ((5 6) 7 8))

Of course, every permutation of [56] must be combined with every permutation of the other branches. You can achieve this by implementing a kind of odometer that doesn't go through the numbers from 0 to 9 in each space, but through the possible permutations of the branches.

Every generated permutation is valid, but this technique doesn't create all possible permutations yet. Remember that we've fixed tool 0 in slot 0, but that needn't be the case. But the topography of valid layout can be used to generate 8 other layouts by rotating it and putting tool 0 in slots 1, 2, and so on.

This technique reduces you search space from 9! to 9 · 4! · 2! · 3! · 2! or by a factor of 70. And there are no tests, but at the cost of a more complicated data structure.

(The reduction is extreme in your 12-tool example, where the network of wires ir really just a straight line without bifurcations.)

This code implements the described technique:

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



enum {
    N = 16                          // hardcoded max. size
};

struct tool {
    int conn[N - 1];                // wire connections
    int nconn;

    int desc[N];                    // "descendants" of the tree node
    int ndesc;

    int cost[N];                    // row of the cost matrix
    int used;                       // flag for recursive descent
};

struct drill {
    int n;
    struct tool tool[N];

    int root;                       // root node    
    int branch[N];                  // indices of branch nodes
    int nbranch;                    // permutating branches

    int opt;                        // current optimum
};

void swap(int a[], int i, int j)
{
    int s = a[i]; a[i] = a[j]; a[j] = s;
}

void reverse(int a[], int i, int n)
{
    while (i < --n) swap(a, i++, n);
}

/*
 *      Turn an array to the next higher permutation. When the
 *      permutation is already the highest, return 0 and reset the
 *      array to the smalles permutation. Otherwise, return 1.
 */
int next_perm(int a[], int n)
{
    int i = n - 1;
    int k = n - 1;

    if (n < 2) return 0;

    while (k && a[k] < a[k - 1]) k--;
    if (k == 0) {
        reverse(a, 0, n);
        return 0;
    }
    k--;

    while (i > k && a[i] < a[k]) i--;
    swap(a, i, k);
    reverse(a, k + 1, n);

    return 1;
}

/*
 *      Insertion sort for sorting the branches at the beginning.
 */
void sort(int a[], int len)
{
    for (int i = 1; i < len; i++) {
        int k = i;

        while (k > 0 && a[k] < a[k - 1]) {
            swap(a, k, k - 1);
            k--;
        }
    }
}

/*
 *      Determine the list of descendants for each node.
 */
void descend(struct drill *dr, int n)
{
    struct tool *t = dr->tool + n;

    t->ndesc = 1;
    t->desc[0] = n;

    t->used = 1;

    for (int i = 0; i < t->nconn; i++) {
        int m = t->conn[i];

        if (dr->tool[m].used == 0) {
            t->desc[t->ndesc++] = m;
            descend(dr, m);
        }
    }

    if (t->ndesc > 1) {
        sort(t->desc, t->ndesc);
        dr->branch[dr->nbranch++] = n;
    }

    t->used = 0;
}

/*
 *      Fill the array a with the current arrangement in the tree.
 */
int evaluate(struct drill *dr, int a[], int n)
{
    struct tool *t = dr->tool + n;
    int m = 0;

    if (n == dr->root) {
        a[0] = dr->root;
        return 1 + evaluate(dr, a + 1, dr->tool[n].conn[0]);
    }

    for (int i = 0; i < t->ndesc; i++) {
        int d = t->desc[i];

        if (d == n) {
            a[m++] = d;
        } else {
            m += evaluate(dr, a + m, d);
        }
    }

    return m;
}

/*
 *      Evaluate all possible permutations and find the optimum.
 */
void optimize(struct drill *dr)
{
    dr->opt = (1u << 31) - 1;

    for (;;) {
        int i = 0;
        struct tool *t = dr->tool + dr->branch[0];

        for (int j = 0; j < dr->n; j++) {
            int a[2 * N];
            int cost = 0;

            evaluate(dr, a, dr->root);

            for (int i = 0; i < dr->n; i++) {
                int k = (i + j) % dr->n;

                cost += dr->tool[i].cost[a[k]];
            }

            if (cost < dr->opt) dr->opt = cost;
        }

        while (next_perm(t->desc, t->ndesc) == 0) {
            i++;

            if (i == dr->nbranch) return;
            t = dr->tool + dr->branch[i];            
        }
    }
}

/*
 *      Read and prepare drill data, then optimize.
 */
int main(void)
{
    struct drill dr = {0};

    fscanf(stdin, "%d", &dr.n);

    for (int j = 0; j < dr.n; j++) {
        for (int i = 0; i < dr.n; i++) {
            scanf("%d", &dr.tool[j].cost[i]);
        }
    }

    for (int i = 1; i < dr.n; i++) {
        int a, b;

        scanf("%d", &a);
        scanf("%d", &b);

        dr.tool[a].conn[dr.tool[a].nconn++] = b;
        dr.tool[b].conn[dr.tool[b].nconn++] = a;
    }

    while (dr.tool[dr.root].nconn > 1) dr.root++;
    dr.tool[dr.root].used = 1;

    descend(&dr, dr.tool[dr.root].conn[0]);
    optimize(&dr);

    printf("%d\n", dr.opt);

    return 0;
}