Bagian 1: Pemodelan Puzzle

Sebelum menjalankan algoritma pencarian, kita harus terlebih dulu menentukan cara menyimpan state puzzle dalam memori. Pilihan struktur data menentukan kemudahan hashing, kecepatan copy, dan keterbacaan kode. Pada bagian ini kita menetapkan konvensi: state disimpan sebagai std::array<int, 9> — array statis berisi 9 integer, indeks 0–8 dipetakan ke grid 3×3 secara row-major. Nilai 0 mewakili sel kosong. Konvensi ini menjadi fondasi untuk semua bagian selanjutnya.

Konvensi State #

Grid 3×3 disimpan sebagai array 1D dengan urutan row-major. Pemetaan posisi grid (row, col) ke indeks array adalah index = row * 3 + col.

text
Grid:           Array:
1 2 3           [1, 2, 3,
4 0 6            4, 0, 6,
7 5 8            7, 5, 8]

index 0 = (0,0) = 1     index 4 = (1,1) = 0  (sel kosong)
index 1 = (0,1) = 2     index 5 = (1,2) = 6
index 2 = (0,2) = 3     index 6 = (2,0) = 7
index 3 = (1,0) = 4     index 7 = (2,1) = 5
                          index 8 = (2,2) = 8

State goal yang kita pakai sepanjang proyek ini adalah 1 2 3 4 5 6 7 8 0. Posisi sel kosong ada di pojok kanan bawah (indeks 8).

Struct `State` dan Operator Dasar #

Kita bungkus std::array<int, 9> dalam struct State agar operator perbandingan dan helper bisa didefinisikan terpisah dari std::array. Operator == dan != dipakai untuk pengecekan isGoal; kita juga menulis print untuk visualisasi grid.

cpp
#include <iostream>
#include <array>
#include <string>

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}}};

bool isGoal(const State& s) {
    return s == GOAL;
}

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

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";
    }
}

Operator Swap: Empat Arah Gerakan #

Dari state manapun, sel kosong dapat berpindah ke atas, bawah, kiri, atau kanan — selama tidak keluar grid. Kita implementasikan sebagai fungsi applyMove yang menerima state dan salah satu dari empat arah, mengembalikan state baru (bisa sama bila gerakan invalid).

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

// row, col untuk tiap indeks
static int rowOf(int i) { return i / 3; }
static int colOf(int i) { return i % 3; }

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;                  // copy
    if (canMove(b, m)) {
        int target = swapTarget(b, m);
        std::swap(next.tiles[b], next.tiles[target]);
    }
    return next;
}

Program Lengkap Bagian 1 #

Program berikut menggabungkan struct, operator, dan fungsi print. Kita uji dengan state awal dan jalankan empat gerakan untuk memverifikasi operator swap bekerja.

cpp
#include <iostream>
#include <array>
#include <string>

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}}};

bool isGoal(const State& s) { return s == GOAL; }

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

void print(const State& s, const std::string& label) {
    std::cout << label << ":\n";
    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";
    }
}

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

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

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::string moveName(Move m) {
    switch (m) {
        case Move::UP:    return "UP";
        case Move::DOWN:  return "DOWN";
        case Move::LEFT:  return "LEFT";
        case Move::RIGHT: return "RIGHT";
    }
    return "?";
}

int main() {
    State start{{{1, 2, 3, 4, 0, 6, 7, 5, 8}}};
    print(start, "State awal");
    std::cout << "isGoal: " << (isGoal(start) ? "true" : "false") << "\n";
    std::cout << "blankIndex: " << findBlank(start) << "\n\n";

    // Tes tiap arah dari state awal
    Move moves[] = {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT};
    for (Move m : moves) {
        State next = applyMove(start, m);
        std::cout << "Setelah " << moveName(m) << ":\n";
        print(next, "  ");
        std::cout << "\n";
    }

    // Verifikasi state goal
    print(GOAL, "State goal");
    std::cout << "isGoal(GOAL): " << (isGoal(GOAL) ? "true" : "false") << "\n";
    return 0;
}

Output yang Dihasilkan:

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

Setelah UP:
  :
1 . 3 
4 2 6 
7 5 8 

Setelah DOWN:
  :
1 2 3 
4 5 6 
7 . 8 

Setelah LEFT:
  :
1 2 3 
. 4 6 
7 5 8 

Setelah RIGHT:
  :
1 2 3 
4 6 . 
7 5 8 

State goal:
1 2 3 
4 5 6 
7 8 . 
isGoal(GOAL): true

Bedah Kode Baris-per-Baris #

struct State { std::array<int, 9> tiles; ... }: wrapper di sekitar std::array. Kita pakai struct (bukan typedef) agar bisa menambah method atau field lain di bagian proyek selanjutnya tanpa mengubah tipe.
const State GOAL{{{1, 2, 3, 4, 5, 6, 7, 8, 0}}}: konstanta global. Triple-brace karena: brace luar untuk inisialisasi struct, brace tengah untuk std::array, brace dalam untuk elemen array. const menjamin tidak ada kode yang mengubahnya.
return s == GOAL: memakai operator== yang didefinisikan di struct. Karena std::array punya operator== element-wise, perbandingan langsung benar.
for (int i = 0; i < 9; ++i) if (s.tiles[i] == 0) return i: linear search untuk menemukan blank. O(9) = O(1) praktis; tidak perlu struktur tambahan.
enum class Move { UP, DOWN, LEFT, RIGHT }: scoped enum. Lebih aman daripada enum biasa karena nama UP tidak bocor ke namespace global.
switch (m) { case Move::UP: return r > 0; ... }: validasi gerakan berdasarkan posisi blank. UP valid bila r > 0 (tidak di baris atas); DOWN valid bila r < 2 (tidak di baris bawah); dst.
State next = s: copy state. std::array melakukan deep copy secara default — aman. Setelah copy, kita modifikasi next tanpa menyentuh s.
std::swap(next.tiles[b], next.tiles[target]): tukar nilai blank dengan target. Inilah inti dari gerakan puzzle — nilai pada target pindah ke posisi blank, sebaliknya.
Move moves[] = {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}: array C-style berisi enum. Loop for (Move m : moves) pakai range-based for yang efisien untuk array statis.

Verifikasi State Goal #

State goal kita, 1 2 3 4 5 6 7 8 0, dipakai konsisten sepanjang proyek. Pengujian di main() memverifikasi bahwa isGoal(GOAL) mengembalikan true — guard terhadap typo saat refactor di bagian berikutnya.

Menampilkan State sebagai Grid #

Fungsi print menerima label sebagai string, lalu mencetak grid 3×3 dengan sel kosong ditandai .. Format ini akan kita pakai ulang di Bagian 3 dan 4 untuk menampilkan jalur solusi.

Kompilasi dan Pengujian #

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

Verifikasi bahwa Setelah DOWN menghasilkan state yang lebih dekat ke goal (hanya butuh swap 8 ke bawah). Pada Bagian 2, kita akan menulis getNeighbors yang menghasilkan semua state valid dari satu state — fondasi untuk BFS dan DFS.

Konvensi State #

Struct State dan Operator Dasar #

Operator Swap: Empat Arah Gerakan #

Program Lengkap Bagian 1 #

Bedah Kode Baris-per-Baris #

Verifikasi State Goal #

Menampilkan State sebagai Grid #

Kompilasi dan Pengujian #

Struct `State` dan Operator Dasar #