Proyek: Pemecah Puzzle dengan Search

8-puzzle adalah klasik dalam pembelajaran AI dan struktur data: grid 3×3 berisi angka 1–8 dan satu sel kosong (ditandai 0). Tujuan: dari konfigurasi awal, capai konfigurasi target dengan jumlah gerakan minimum. Walaupun soal terlihat sederhana, ruang state mencapai 9!/2 = 181.440 state yang reachable — cukup besar untuk menguji strategi pencarian. Pada proyek ini kita membangun solver 8-puzzle dengan tiga algoritma: BFS untuk solusi optimal bobot seragam, DFS untuk eksplorasi cepat (sub-optimal), dan A* dengan heuristic Manhattan distance sebagai puncak optimasi. Setiap bagian membangun di atas bagian sebelumnya, dari pemodelan state sampai benchmark BFS vs A*.

Tool yang akan kita bangun memiliki cakupan berikut:

• memodelkan state 8-puzzle sebagai array 9 elemen dengan sel kosong bernilai 0,
• men generate tetangga melalui operator swap (atas, bawah, kiri, kanan),
• menjalankan BFS untuk solusi optimal (minimum gerakan),
• menjalankan DFS untuk komparasi eksplorasi depth-first,
• menjalankan A* dengan priority queue dan heuristic Manhattan distance,
• merekonstruksi urutan gerakan dari start ke goal,
• mencetak grid sebelum dan sesudah, plus jalur solusi,
• membandingkan jumlah node yang dikunjungi tiap algoritma.

Tampilan Akhir Tool #

Berikut contoh input state awal, state goal, dan jalur solusi yang ditemukan A*:

State awal:
1 2 3
4 0 6
7 5 8

State goal:
1 2 3
4 5 6
7 8 0

Jalur solusi (4 langkah):
1 2 3      1 2 3      1 2 3      1 2 3      1 2 3
4 0 6  ->  4 5 6  ->  4 5 6  ->  4 5 6  ->  4 5 6
7 5 8      7 0 8      7 8 0      7 8 0      7 8 0
           (down 5)   (right 8)  ...        ...

A* mengunjungi 12 node untuk menemukan solusi optimal.

Pada Bagian 4, kita membandingkan kinerja BFS, DFS, dan A* pada puzzle yang sama, serta melihat bagaimana heuristic memangkas ruang pencarian secara dramatis.

Tujuan Pembelajaran #

Setelah menyelesaikan proyek ini, kita mampu:

• memodelkan state puzzle sebagai struktur data yang hashable dan comparable,
• membangun graph state implisit melalui operator swap (tanpa adjacency list eksplisit),
• mengimplementasikan BFS dengan queue dan visited set untuk solusi optimal,
• mengimplementasikan DFS dengan stack sebagai pembanding eksplorasi,
• mengimplementasikan A* dengan priority queue dan heuristic admissible,
• merekonstruksi jalur dari start ke goal melalui parent map,
• membandingkan kompleksitas waktu dan memori ketiga algoritma pada kasus uji yang sama.

Prasyarat #

Proyek ini memanfaatkan materi yang sudah dibahas pada Section sebelumnya:

• Breadth-First Search — algoritma inti pada Bagian 3,
• Depth-First Search — pembanding eksplorasi pada Bagian 3,
• Greedy & A* — konsep heuristic admissible pada Bagian 4,
• Priority Queue dan Heap — std::priority_queue dengan custom comparator,
• STL Containers — std::array, std::unordered_set, std::unordered_map.

Tahapan Pengerjaan #

Proyek dikerjakan dalam empat bagian berurutan:

1. Bagian 1: Pemodelan Puzzle — merepresentasikan state 3×3 sebagai std::array<int, 9>, menulis fungsi print, isGoal, dan operator swap.
2. Bagian 2: State Space Search — membangun graph state implisit via getNeighbors, hashing state untuk unordered_set.
3. Bagian 3: Implementasi BFS dan DFS — BFS dengan std::queue untuk solusi optimal; DFS dengan std::stack sebagai pembanding.
4. Bagian 4: Optimasi Pencarian — A* dengan priority queue diurutkan berdasarkan f = g + h; h adalah Manhattan distance; benchmark BFS vs A*.

Mulailah dari Bagian 1 dan kerjakan secara berurutan. Setiap bagian membangun di atas berkas bagian sebelumnya — struktur data dan helper yang ditulis di Bagian 1 akan dipakai sampai Bagian 4.

Pilihan State Awal untuk Pengujian #

Tidak semua konfigurasi 8-puzzle solvable. State awal harus memiliki paritas inversi yang sama dengan state goal. Untuk pengujian, gunakan state yang jarak solusinya pendek (2–8 langkah) agar eksperimen cepat selesai:

Pada Bagian 4, kita akan melihat bahwa BFS dan A* sama-sama menemukan solusi optimal untuk kasus Easy, tetapi A* mengunjungi jauh lebih sedikit node — bukti nyata kekuatan heuristic admissible.