Pada Bagian 1 kita sudah bisa membuat dan memodifikasi state. Sekarang kita perlu cara untuk “melihat” graph pencarian: dari satu state, state mana saja yang bisa dicapai dengan satu gerakan? Pertanyaan ini dijawab oleh fungsi getNeighbors. Selain itu, kita perlu mekanisme untuk mencatat state yang sudah dikunjungi — agar BFS dan DFS tidak berputar. Sayangnya, std::array tidak punya std::hash default di std::unordered_set, jadi kita harus menulis hasher sendiri. Pada bagian ini kita menyelesaikan dua hal ini sebelum masuk ke implementasi BFS dan DFS di Bagian 3.

Graph State Implisit #

Graph 8-puzzle tidak disimpan eksplisit sebagai adjacency list — terlalu besar (181.440 state reachable). Sebagai gantinya, kita generate tetangga on-the-fly lewat getNeighbors(state). Pendekatan ini disebut implicit graph.

text 
          [1 2 3]
          [4 0 6]      <-- state saat ini
          [7 5 8]
            |
   getNeighbors(state)
            |
   +--------+--------+--------+
   |        |        |        |
[1 0 3]  [1 2 3]  [1 2 3]  [1 2 3]
[4 2 6]  [4 5 6]  [0 4 6]  [4 6 0]
[7 5 8]  [7 . 8]  [7 5 8]  [7 5 8]
   UP      DOWN     LEFT     RIGHT

Setiap state memiliki 2–4 tetangga, tergantung posisi sel kosong di pojok, sisi, atau tengah.

Fungsi getNeighbors #

Kita kemas ulang applyMove dari Bagian 1 menjadi fungsi yang mengembalikan daftar state tetangga valid. Output berupa std::vector<State>.

cpp 
#include <vector>
#include <array>

struct State {
    std::array<int, 9> tiles;
    bool operator==(const State& o) const { return tiles == o.tiles; }
};

enum class Move { UP, DOWN, LEFT, RIGHT };

// (definisi canMove, swapTarget, applyMove seperti Bagian 1)

std::vector<State> getNeighbors(const State& s) {
    std::vector<State> result;
    for (Move m : {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}) {
        State next = applyMove(s, m);
        if (next != s) {                  // berubah = valid
            result.push_back(next);
        }
    }
    return result;
}

Hashing State untuk unordered_set #

std::unordered_set<State> butuh dua hal: operator== (sudah ada di struct) dan std::hash<State>. Karena std::array tidak punya std::hash default, kita tulis hasher sendiri.

Strategi hashing: encode state sebagai satu integer 32-bit. Karena tiap tile bernilai 0–8 (butuh 4 bit), 9 tile × 4 bit = 36 bit. Agar muat di uint32_t, kita pakai hashing yang lebih ringan — XOR dengan rotate, atau multi-way polynomial.

cpp 
#include <cstdint>

struct StateHash {
    std::size_t operator()(const State& s) const {
        std::size_t h = 0;
        for (int i = 0; i < 9; ++i) {
            h = h * 31 + s.tiles[i];   // polynomial rolling hash
        }
        return h;
    }
};

Polynomial rolling hash: h = h * 31 + tiles[i]. Konstanta 31 adalah prima kecil yang umum dipakai di Java String.hashCode. Hasilnya tidak kriptografis — cukup untuk distribusi seragam di hash table.

Program Lengkap Bagian 2 #

Program berikut membangun getNeighbors, StateHash, lalu memverifikasi bahwa unordered_set<State, StateHash> bisa menyimpan dan mencari state dengan benar.

cpp 
#include <iostream>
#include <array>
#include <vector>
#include <unordered_set>
#include <string>
#include <cstdint>

struct State {
    std::array<int, 9> tiles;
    bool operator==(const State& o) const { return tiles == o.tiles; }
    bool operator!=(const State& o) const { return tiles != o.tiles; }
};

const State GOAL{{{1, 2, 3, 4, 5, 6, 7, 8, 0}}};

int findBlank(const State& s) {
    for (int i = 0; i < 9; ++i) if (s.tiles[i] == 0) return i;
    return -1;
}

static int rowOf(int i) { return i / 3; }
static int colOf(int i) { return i % 3; }

enum class Move { UP, DOWN, LEFT, RIGHT };

bool canMove(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return r > 0;
        case Move::DOWN:  return r < 2;
        case Move::LEFT:  return c > 0;
        case Move::RIGHT: return c < 2;
    }
    return false;
}

int swapTarget(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return (r - 1) * 3 + c;
        case Move::DOWN:  return (r + 1) * 3 + c;
        case Move::LEFT:  return r * 3 + (c - 1);
        case Move::RIGHT: return r * 3 + (c + 1);
    }
    return blankIndex;
}

State applyMove(const State& s, Move m) {
    int b = findBlank(s);
    State next = s;
    if (canMove(b, m)) {
        int target = swapTarget(b, m);
        std::swap(next.tiles[b], next.tiles[target]);
    }
    return next;
}

std::vector<State> getNeighbors(const State& s) {
    std::vector<State> result;
    for (Move m : {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}) {
        State next = applyMove(s, m);
        if (next != s) result.push_back(next);
    }
    return result;
}

struct StateHash {
    std::size_t operator()(const State& s) const {
        std::size_t h = 0;
        for (int i = 0; i < 9; ++i) {
            h = h * 31 + s.tiles[i];
        }
        return h;
    }
};

using StateSet = std::unordered_set<State, StateHash>;

void print(const State& s) {
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            int v = s.tiles[r * 3 + c];
            if (v == 0) std::cout << ". ";
            else std::cout << v << " ";
        }
        std::cout << "\n";
    }
}

int main() {
    State start{{{1, 2, 3, 4, 0, 6, 7, 5, 8}}};

    std::cout << "State awal:\n";
    print(start);
    std::cout << "blankIndex: " << findBlank(start) << "\n\n";

    auto neighbors = getNeighbors(start);
    std::cout << "Jumlah tetangga: " << neighbors.size() << "\n\n";
    for (size_t i = 0; i < neighbors.size(); ++i) {
        std::cout << "Tetangga " << (i + 1) << ":\n";
        print(neighbors[i]);
        std::cout << "\n";
    }

    // Uji unordered_set dengan StateHash
    StateSet visited;
    visited.insert(start);
    for (const auto& nb : neighbors) {
        visited.insert(nb);
    }

    std::cout << "Ukuran visited set: " << visited.size() << "\n";
    std::cout << "start in visited: " << (visited.count(start) ? "yes" : "no") << "\n";
    std::cout << "goal in visited: " << (visited.count(GOAL) ? "yes" : "no") << "\n";

    // Verifikasi: state yang baru dibuat dengan nilai sama harus ditemukan
    State copyOfStart{{{1, 2, 3, 4, 0, 6, 7, 5, 8}}};
    std::cout << "copyOfStart in visited: "
              << (visited.count(copyOfStart) ? "yes" : "no") << "\n";

    // Tetangga goal: harus 2 (pojok kanan bawah)
    auto goalNeighbors = getNeighbors(GOAL);
    std::cout << "\nTetangga GOAL: " << goalNeighbors.size() << "\n";
    for (const auto& nb : goalNeighbors) {
        print(nb);
        std::cout << "---\n";
    }

    return 0;
}

Output yang Dihasilkan:

text 
State awal:
1 2 3 
4 . 6 
7 5 8 
blankIndex: 4

Jumlah tetangga: 4

Tetangga 1:
1 . 3 
4 2 6 
7 5 8 

Tetangga 2:
1 2 3 
4 5 6 
7 . 8 

Tetangga 3:
1 2 3 
. 4 6 
7 5 8 

Tetangga 4:
1 2 3 
4 6 . 
7 5 8 

Ukuran visited set: 5
start in visited: yes
goal in visited: no
copyOfStart in visited: yes

Tetangga GOAL: 2
1 2 3 
4 5 . 
7 8 6 
---
1 2 3 
4 5 6 
7 . 8 
---

Bedah Kode Baris-per-Baris #

  1. std::vector<State> getNeighbors(const State& s): kembalikan vector berisi semua tetangga valid. Karena tiap state maksimum punya 4 tetangga, vector pendek — tidak perlu reserve.
  2. for (Move m : {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}): range-based for over braced init-list. Ringkas untuk iterasi konstanta enum.
  3. if (next != s) result.push_back(next): cek apakah gerakan valid dengan membandingkan state. Bila applyMove tidak mengubah apa pun (gerakan invalid), next == s dan kita skip.
  4. struct StateHash { std::size_t operator()(const State& s) const { ... } }: functor hash. operator() dipanggil oleh unordered_set saat butuh hash. const di akhir menjamin tidak memodifikasi state saat hashing.
  5. h = h * 31 + s.tiles[i]: polynomial rolling hash. Setiap iterasi: h di-skala 31, lalu ditambah tile. Bila dua state berbeda hanya di tile akhir, hash-nya akan berbeda karena kontribusi tile akhir tidak di-cancel.
  6. using StateSet = std::unordered_set<State, StateHash>: type alias. Lebih ringkas daripada menulis tipe penuh setiap deklarasi. Mengganti set di seluruh proyek hanya butuh satu baris.
  7. visited.insert(start): insert state ke set. Bila sudah ada, unordered_set tidak menyimpan duplikat.
  8. visited.count(start): cek keanggotaan. Mengembalikan 0 atau 1 (untuk unordered_set). Lebih efisien daripada find + perbandingan dengan end().
  9. visited.count(copyOfStart): kunci pengujian hasher. copyOfStart adalah state berbeda (instance berbeda di memori) tetapi nilai tiles sama. Bila hasher dan operator== benar, count mengembalikan 1.
  10. getNeighbors(GOAL): verifikasi edge case. Goal punya blank di pojok kanan bawah (indeks 8), jadi hanya 2 tetangga valid: UP (swap dengan indeks 5) dan LEFT (swap dengan indeks 7).

Visited Set untuk Path Reconstruction #

Selain unordered_set, kita akan butuh unordered_map<State, ParentInfo, StateHash> di Bagian 3 untuk menyimpan jejak parent. Polanya sama: tulis hasher, pakai sebagai parameter ke-3 di template. Kita bisa menyimpan ParentInfo berisi parent state + move yang dipakai, agar bisa merekonstruksi jalur gerakan dari start ke goal.

Kompleksitas getNeighbors #

AspekKompleksitasCatatan
Pencarian blankO(9) = O(1)tetap konstan
Loop 4 arahO(4) = O(1)tetap konstan
Swap tileO(1)operasi elementer
Hashing stateO(9) = O(1)9 elemen, sekali per state
Insert unordered_setO(1) rata-rataO(n) worst case bila banyak kolisi

Total per state: O(1). Karena BFS mengunjungi setiap state maksimum sekali, total kompleksitas BFS di 8-puzzle adalah O(V) = O(181.440) pada worst case.

Kompilasi dan Pengujian #

bash 
g++ -std=c++17 -O2 -Wall -Wextra -o puzzle_part2.bin puzzle_part2.cpp
./puzzle_part2.bin

Verifikasi bahwa visited.count(copyOfStart) mengembalikan yes. Bila no, ada bug di hasher atau operator==. Pada Bagian 3, kita akan memakai fondasi ini untuk menjalankan BFS dan DFS.