RAT IN A MAZE

Rat in a Maze

Dokumen ini membahas permasalahan Rat in a Maze, yang merupakan salah satu contoh klasik penerapan teknik backtracking. Tujuannya adalah menemukan semua jalur dari titik awal hingga titik tujuan dalam sebuah labirin yang direpresentasikan sebagai matriks.

---

Definisi Masalah

Labirin dinyatakan sebagai matriks dua dimensi di mana:

• 1 menunjukkan bahwa sel dapat dilewati
• 0 menunjukkan bahwa sel merupakan tembok atau tidak dapat dilewati

Tugas algoritma adalah menemukan semua jalur dari sel kiri atas (0, 0) menuju sel kanan bawah (N-1, N-1), tanpa melewati sel yang sama lebih dari satu kali dalam satu jalur.

---

Aturan Pergerakan

• Pergerakan diperbolehkan ke empat arah: atas (U), bawah (D), kiri (L), kanan (R)
• Tikus tidak boleh keluar dari batas matriks
• Tidak boleh mengunjungi sel 0 atau sel yang telah dikunjungi dalam jalur yang sama

---

Contoh Labirin

1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1

Beberapa solusi jalur yang valid:

• DRDDRR
• DDRDRR

---

Ilustrasi Penyelesaian

Algoritma akan memulai dari titik (0,0) dan mencoba semua arah yang valid:

• Mengeksplorasi jalur ke arah bawah terlebih dahulu
• Jika menemui jalan buntu, algoritma akan mundur (backtrack)
• Proses berulang sampai semua jalur ke tujuan ditemukan

---

Implementasi dalam Bahasa C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void solveMaze(vector<vector<int>>& maze, int x, int y, vector<vector<bool>>& visited, string path, vector<string>& res) {
    int n = maze.size();
    if (x == n-1 && y == n-1) {
        res.push_back(path);
        return;
    }

    int dx[] = {1, 0, 0, -1}; // D, L, R, U
    int dy[] = {0, -1, 1, 0};
    char move[] = {'D', 'L', 'R', 'U'};

    for (int i = 0; i < 4; i++) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if (newX >= 0 && newY >= 0 && newX < n && newY < n &&
            maze[newX][newY] == 1 && !visited[newX][newY]) {
            visited[newX][newY] = true;
            solveMaze(maze, newX, newY, visited, path + move[i], res);
            visited[newX][newY] = false;
        }
    }
}

vector<string> findPaths(vector<vector<int>> &maze) {
    int n = maze.size();
    vector<string> res;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    if (maze[0][0] == 1)
        solveMaze(maze, 0, 0, visited, "", res);
    return res;
}

int main() {
    vector<vector<int>> maze = {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {1, 1, 0, 0},
        {0, 1, 1, 1}
    };

    vector<string> paths = findPaths(maze);
    for (string path : paths)
        cout << path << endl;

    return 0;
}

---

Kelebihan dan Kekurangan

Kelebihan:

• Sederhana dan intuitif
• Dapat menemukan semua solusi jalur
• Cocok sebagai ilustrasi konsep backtracking

Kekurangan:

• Kurang efisien untuk ukuran labirin besar
• Risiko stack overflow karena rekursi dalam

---

Aplikasi

• Navigasi robot otomatis
• Sistem pencarian jalur dalam peta
• Simulasi dalam permainan dan pemodelan

---

Kesimpulan

Permasalahan Rat in a Maze merupakan studi kasus yang sangat baik untuk memahami teknik backtracking. Dengan menjelajahi setiap kemungkinan jalur dan mundur ketika menemui hambatan, algoritma ini mencerminkan proses pencarian solusi sistematis dalam ruang kemungkinan yang terbatas.