Analisis Efisiensi dan Kompleksitas Algoritma Backtracking dalamPermainan Math Maze

Abstract

Kemajuan teknologi informasi saat ini mendorong kebutuhan akan metode pencarian solusi yang efisien dan optimal dalam berbagai aplikasi, termasuk permainan edukatif. Penelitian ini bertujuan untuk mengevaluasi efisiensi dan kompleksitas algoritma backtracking dalam permainan Math Maze. Permainan ini mengusung konsep labirin berbasis angka, di mana pemain harus menemukan jalur yang benar berdasarkan angka panduan di sisi grid. Metode yang digunakan adalah implementasi algoritma backtracking dengan pendekatan Depth-First Search (DFS) untuk membangun dan menyelesaikan labirin.Hasil penelitian menunjukkan bahwa algoritma backtracking mampu membangkitkan maze dengan solusi yang valid dan unik. Waktu rata-rata yang dibutuhkan untuk membentuk maze berukuran 10x10 adalah sekitar 0,5 detik, dengan peningkatan waktu seiring bertambahnya ukuran grid. Keunggulan utama dari algoritma ini mencakup keberhasilan 100% dalam menemukan jalur solusi, pencegahan loop atau ruang kosong yang tidak terpakai, serta kemampuan meminimalkan eksplorasi jalur yang tidak relevan. Penelitian ini menyimpulkan bahwa algoritma backtracking efektif dan efisien dalam menyelesaikan masalah eksplorasi jalur pada permainan Math Maze. Dengan solusi yang optimal serta struktur maze yang terarah, permainan ini menawarkan tantangan logis yang edukatif dan menarik bagi pemain.