What I modified

The assignment provides most scaffolding (map reading, helpers, gameplay utilities). My main work is concentrated in ai.c (all algorithms + data structures) and Makefile (build/runtime optimisation).

Downloads

Download ai.c Download Makefile Download Report (PDF)

Key Technical Highlights

• Correctness + memory safety: deep-copying states and freeing maps/solutions properly
• Compact state encoding: bit-packing puzzle state to speed hashing/comparison
• A2 duplicate detection: radix-tree-based visited checking to avoid revisits
• A3 IW + novelty: iterated width with novelty pruning using per-width radix trees
• Build optimisation: using -O2 -DNDEBUG to improve runtime in hard tests (impassable)

Representative Code Excerpts

1) Deep copy a state (duplicate_state)

gate_t* duplicate_state(gate_t* gate, bool is_init) {
    gate_t* duplicate = (gate_t*)malloc(sizeof(gate_t));
    assert(duplicate);
    duplicate->lines = gate->lines;
    duplicate->num_chars_map = gate->num_chars_map;
    duplicate->num_pieces = gate->num_pieces;
    ...
    for (int i = 0; i < gate->lines; i++) {
        size_t len = strlen(gate->map[i]);
        duplicate->map[i] = malloc(len+1);
        duplicate->map_save[i] = malloc(len+1);
        memcpy(duplicate->map[i], gate->map[i], len+1);
        memcpy(duplicate->map_save[i], gate->map_save[i], len+1);
    }
    ...
}

From ai.c — safe copying of dynamic map data.

2) Bit-packing the state (packMap)

void packMap(gate_t *gate, unsigned char *packedMap) {
    int pBits = calcBits(gate->num_pieces);
    int hBits = calcBits(gate->lines);
    int wBits = calcBits(gate->num_chars_map / gate->lines);
    int bitIdx = 0;
    for(int i = 0; i < gate->num_pieces; i++) {
        ...
        for(int j = 0; j < hBits; j++) { ... }
        for(int j = 0; j < wBits; j++) { ... }
    }
}

From ai.c — compact encoding used for visited/novelty checks.

3) A2: duplicate detection with radix tree

packMap(new, packedMap);

if (checkPresent(radixTree, packedMap, num_pieces)) {
    duplicatedNodes++;
    free_state(new, NULL);
    continue;
}

insertRadixTree(radixTree, packedMap, num_pieces);
enqueue(queue, new);

From ai.c — avoids repeated expansions in UCS.

4) A3: IW + novelty (iterating w, pruning by novelty)

for (int w = 1; w <= n + 1 && !has_won; w++) {
    bool final_bfs = (w == n + 1);
    int kmax = final_bfs ? 0 : (w < n ? w : n);

    ...
    packMap(child, packedMap);

    bool novel = false;
    for (int s = 1; s <= kmax; s++) {
        if (checkPresentnCr(rts[s], packedMap, s) == NOTPRESENT) {
            insertRadixTreenCr(rts[s], packedMap, s);
            novel = true;
            break;
        }
    }

    if (novel) enqueue(q, child);
    else { duplicatedNodes++; free_state(child, NULL); }
}

From ai.c — novelty pruning is the key to scaling on impassable cases.

Build Optimisation (Makefile)

The Makefile uses -O2 -DNDEBUG in CFLAGS. This was a practical “engineering win”: it improved runtime enough to help pass hard cases like impassable3 after algorithmic pruning was in place.

CFLAGS = -Wall -Wextra -O2 -DNDEBUG -I./include/