← Back to Projects

Project 006: Gate Puzzle AI Solver

C • State-Space Search • Performance Tuning • Coursework (Individual)

Overview

A C-based AI solver for a “Gate puzzle” (a board-like state-space search problem). The solver reads puzzle instances, enumerates legal actions, searches for a goal state, and outputs a solution path plus runtime statistics (time / nodes / memory).

The report benchmarks three strategies (A1/A2/A3) on two suites: capability1–13 and impassable1–3.

My Role

  • Individual project — implemented all algorithms and data structures in ai.c
  • Built evaluation output (solution + expanded/generated/duplicates/memory)
  • Handled performance bottlenecks (bit-packing + pruning + build flags)

Algorithms (A1 / A2 / A3)

Each algorithm increases scalability by reducing redundant state exploration. The report’s method section describes UCS (A1), duplicate checking (A2), and IW + novelty pruning (A3).

Algorithm A1 hint
A1 — UCS baseline
Algorithm A2 hint
A2 — UCS + duplicate state detection
Algorithm A3 hint
A3 — Iterated Width (IW) + novelty detection (pruning)

Key Results (Screenshots)

These two screenshots are the “most portfolio-worthy” evidence: (1) capability10 shows a clear efficiency improvement from A1 → A2 → A3, and (2) impassable3 demonstrates that A3 can solve the hardest case (93 steps, IW(3)).

capability10 results comparison
capability10 — A1 vs A2 vs A3 (nodes/time/duplicates/memory comparison)
impassable3 solved by A3
impassable3 — solved by A3 (IW(3)), 93-step solution; shows generated/expanded/aux memory statistics

Go to Code Page Download Report (PDF)

Research Report

The report includes methodology, threats to validity, and a full appendix table of results.