Skripsi Skripsi

Latar Belakang 

Word search puzzle merupakan salah satu permainan teka-teki yang cukup populer di masyarakat. Word search puzzle adalah permainan pencarian kata dalam kumpulan huruf yang tersusun secara acak pada sebuah grid yang biasanya berbentuk persegi. Dalam permainan ini pemain harus  menemukan semua kata yang tersembunyi di dalam persegi tersebut. Kata-kata yang tersembunyi dapat ditemukan secara 

horizontal, vertikal dan diagonal. 

Strategi umum yang digunakan oleh pemain untuk menyelesaikan  puzzle ini adalah dengan mencari huruf pertama dari kata yang dicari dalam kumpulan huruf kemudian mencari huruf kedua yang terletak disebelah kanan, kiri, atas, bawah atau diagonal yang cocok dan seterusnya sampai huruf-huruf yang ditemukan membentuk kata yang dicari. Permainan dapat diselesaikan dengan menerapkan strategi tersebut 

namun waktu penyelesaian tergantung pada kecepatan dan ketelitian masing-masing pemain karena adanya kesulitan dalam mencari kata-kata yang tersembunyi dalam kumpulan huruf.  

Seiring berkembangnya pengetahuan dan teknologi, permainan  word search puzzle dapat diselesaikan oleh komputer dengan mengimplementasikan algoritma. Algoritma pencarian  backtracking dapat diterapkan kedalam aplikasi untuk dapat melakukan pencarian kata. Aplikasi yang dibangun diharapkan dapat mengotomasi pencarian kata dalam word search puzzle, sehingga pemain dapat segera mengetahui 

letak kata-kata yang dicari.  

Dalam skripsi ini, aplikasi yang dibangun untuk pencarian kata dalam word search puzzle dilakukan dengan menerapkan algoritma  backtracking. Algoritma backtracking adalah algoritma pencarian dengan cara menelusuri pohon solusi secara DFS (Depth First Search) sampai ditemukan solusi yang layak. Algoritma 

backtracking merupakan perbaikan dari algoritma  bruteforce, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Algoritma  backtracking  banyak  diterapkan untuk  program-program game (permainan). 

Beberapa penelitian yang pernah dilakukan untuk menyelesaikan board games dengan menggunakan backtracking  antara lain untuk penyelesaian permainan anagram (Assat, 2007), masalah Knight Tour (Mumtaz, 2008), dan permainan congklak (Bakri, 2010).  Dengan metode ini, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang

selalu dipertimbangkan. Karena itu waktu pencarian solusi dapat lebih dihemat. 

Perkembangan smart phone/tablet pc berbasis Android sangat pesat beberapa tahun terakhir. Perkembangan tersebut mengakibatkan meningkatnya aplikasi-aplikasi mobile berbasis Android. Untuk itu penulis akan membangun aplikasi yang dapat digunakan di  smart phone/tablet pc  berbasis Android. Dengan memanfaatkan perkembangan Android diharapkan aplikasi yang dibangun dapat lebih bermanfaat 

dan bernilai ekonomis. 

Rumusan Masalah 

Pencarian kata dalam permainan word search puzzle dapat dilakukan secara manual, namun terdapat kesulitan untuk mencari kata-kata dalam grid yang berisi sekumpulan huruf yang tersusun secara acak. Karena itu permasalahan yang akan diselesaikan dalam skripsi ini adalah bagaimana pencarian kata dalam permainan  word search puzzle dapat diautomasi sehingga pemain dapat mengetahui letak kata-kata yang dicari dalam permainan tersebut. 

Batasan Masalah 

Pada skripsi ini dilakukan beberapa batasan masalah sebagai berikut : 

1.  Pada aplikasi yang dibangun permainan dimainkan oleh satu pemain (single-player).   

2.  Kata-kata yang harus dicari oleh pemain di dalam kumpulan huruf disediakan oleh aplikasi. Jumlah kata yang harus dicari dalam satu pemainan adalah 4 kata untuk level 1, 6 kata untuk level 2 dan 8 kata untuk level 3. 

3.  Ukuran grid yang berisi kumpulan huruf dalam permainan berukuran 10 x 10 sehingga jumlah huruf dalam grid adalah 100 huruf. 

4.  Dalam aplikasi yang dibangun, kata-kata yang tersembunyi dalam puzzle dapat ditemukan dengan kemungkinan delapan jalur, yaitu : 

a.  Horizontal ke kanan 

b.  Horizontal ke kiri 

c.  Vertikal ke atas 

d.  Vertikal ke bawah 

e.  Diagonal ke kanan-atas 

f.  Diagonal ke kanan-bawah 

g.  Diagonal ke kiri-atas 

h.  Diagonal ke kiri-bawah 

5.  Aplikasi yang dibangun menggunakan bahasa pemrograman C++. File-file program akan dikonversi menjadi  library  yang dapat digunakan pada pemrograman Java di Eclipse, sehingga program dapat di-compile  sebagai Android application. 

6.  Aplikasi dapat dijalankan pada  tablet pc dengan sistem operasi Android versi 2.2 (Froyo) dengan tampilan terbaik pada Samsung Galaxy Tab GT-P1000. 

 Tujuan Penelitian 

Adapun tujuan dari penulisan skripsi ini adalah untuk membangun suatu aplikasi yang dapat menemukan solusi permainan word search puzzle dengan menerapkan algoritma backtracking. 

Manfaat Penelitian 

Manfaat yang diharapkan dari penelitian ini adalah menerapkan ilmu pengetahuan yang didapatkan penulis di masa kuliah serta menambah wawasan ilmu dan pemahaman kepada penulis dan pembaca tentang penggunaan algoritma backtracking dalam menyelesaikan permainan word search puzzle. Selain itu, dengan membangun aplikasi berbasis mobile yang dapat digunakan pada  tablet pc  berbasis android diharapkan aplikasi ini dapat digunakan masyarakat secara luas dan bernilai ekonomis. 

Credit:  Ishri Ifdhillah Marbun