Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin

## Penerapan Algoritma Booyer Moore Pada Aplikasi Teka Teki Silang (TTS)

## M Ibnu Ramadhan
Program Studi Teknik Informatika, Universitas Budi Darma, Medan, Indonesia Email: yuuklibnuu@gmail.com
Abstrak− Teka-teki  silang  atau  disingkat  dengan  TTS  adalah  suatu  permainan  untuk  mengisi  ruang-ruang  kosong  (berbentuk  kotak putih) dengan huruf-huruf yang membentuk sebuah kata berdasarkan petunjuk yang diberikan. Pada perkembangan selanjutnya, teka-teki ini juga ditujukan untuk soal-soal yang harus diisikan dengan angka. Untuk mengisi huruf pada setiap kotak maka diberikan petunjuk yang  dibagi  ke  dalam  kategori  "mendatar"  dan  "menurun".  Kecepatan  dalam  menyelesaikan  permaianan  teka-teki  silang,  sangat bergantung kepada kosa kata yang dimiliki oleh pemain. Hal tersebut dikarenakan permaianan harus mampu menyusun kata kata yang hurufnya saling berkaitan yang disusun secara hortizontal dan vertical, Adapun kata-kata tersebut harus sesuai dengan tema pertanyaan yang  telah  disediakan  permainan  tersebut.  Algoritma  Boyer  Moore  adalah  algoritma  pencarian  string  yang  paling  efisien  dan  sudah menjadi standar dari sistem pencarian string. Algoritma ini melakukan pendeteksian pola dalam string dengan melakukan perband ingan karakter pada deretan yang berbeda. Proses ini dinamakan Shift, dan aturan shift dihitung dengan menerapkan 2 aturan, yaitu aturan bad character  dan  aturan  good  suffix.  Nilai  maksimum  dari  panjang  shift  yang  dapat  dilakukan  dihitung  dengan  aturan  ini,  kemudian pencarian karakter dilakukan dari awal sampai dengan pergeseran shift sebanyak panjang shift..

## Kata Kunci : Teka Teki Silang; Algoritma Boyer Moore; Android
Abstract− Crossword or abbreviated with TTS is a game to fill the empty spaces (in the form of white boxes) with letters that form a word based on the instructions given. In further developments, this puzzle is also intended for problems that must be filled with numbers. To fill in the letters in each box, instructions are given that are divided into "horizontal" and "downward" categories. The speed at which to play the crossword game depends greatly on the vocabulary possessed by the player. That is because the game must be able t o arrange words  whose  letters  are  interrelated  arranged  vertically  and  vertically,  the  words  must  be  in  accordance  with  the  theme  of  questions provided by the game. Boyer Moore's algorithm is the most efficient string search algorithm and has become the standard of the string search system. This algorithm detects patterns in strings by comparing characters in different sequences. This process is called Shift, and shift rules are calculated by applying 2 rules, namely bad character rules and good suffix rules. The maximum value of the sh ift length that can be done is calculated by this rule, then the character search is carried out from the beginning until the shift is as long as the shift length.
Keywords : Crossword Puzzle; Boyer Moore Algorithm; Android

## 1. PENDAHULUAN
G ame atau  permainan  merupakan  hal  yang  sangat  sering  kita  dengar  dan  banyak  diminati  dari  berbagai  kalangan  usia, mulai  dari  anak-anak,  remaja,  hingga  orangtua.  Pada  mulanya  game  atau  permainan  hanya  bersifat  tradisional  yaitu menggunakan  tumbuhan  atau  sebatang  kayu,  namun  seiring  berjalannya  waktu  game  mengalami  perubahan  media  yang digunakan seperti kertas, bahan-bahan plastik hingga akhirnya berbentuk elektronik. Pengguna game pada umumnya hanya sebagai  pengisi  waktu  senggang  atau  sekedar  mencari  hiburan  di  tengah  kesibukan,  namun  game  atau  permainan  kini berkembang menjadi media pembelajaran yang sering disebut game education .
Teka-teki silang atau disingkat dengan TTS adalah suatu permainan untuk mengisi ruang-ruang kosong (berbentuk kotak putih) dengan huruf-huruf yang membentuk sebuah kata berdasarkan petunjuk yang diberikan. Pada perkembangan selanjutnya, teka-teki ini juga ditujukan untuk soal-soal yang harus diisikan dengan angka. Untuk mengisi huruf pada setiap kotak maka diberikan petunjuk  yang dibagi ke dalam kategori "mendatar" dan "menurun"[1].
Kecepatan  dalam  menyelesaikan  permaianan  teka-teki  silang,  sangat  bergantung  kepada  kosa  kata  yang  dimiliki oleh pemain. Hal tersebut dikarenakan permaianan harus mampu menyusun kata kata yang hurufnya saling berkaitan yang disusun  secara  hortizontal  dan  vertical,  Adapun  kata-kata  tersebut  harus  sesuai  dengan  tema  pertanyaan  yang  telah disediakan permainan tersebut.
Algoritma boyer moore adalah algoritma pencarian string yang paling efisien dan sudah menjadi standar dari sistem pencarian string. Algoritma ini melakukan pendeteksian pola dalam string dengan melakukan perbandingan karakter pada deretan yang berbeda. Proses ini dinamakan shift, dan aturan shift dihitung dengan menerapkan 2 aturan, yaitu aturan bad character dan  aturan good  suffix .  Nilai  maksimum  dari  panjang  shift  yang  dapat  dilakukan  dihitung  dengan  aturan  ini, kemudian pencarian karakter dilakukan dari awal sampai dengan pergeseran shift sebanyak panjang shift[2].
Berdasarkan  penjelasan  sebelumnya  penulis  menyimpulkan  bahwa  permainan  Teka  Teki  Silang  dapat  diterapkan algoritma Boyer Moore dalam melakukan pencocokan kata berdasarkan dari penelitian yang dilakukan oleh “Mohammad Sholeh  Syukur,  Wijanarto”  dengan  judul  “ Generator Teka-Teki  Silang  Menggunakan  Algoritma Backtracking  dan  Brute Force[3]. Untuk  melakukan  pencarian  hasil  inputan  untuk  pencocokan string /  kata  antara  inputan  pengguna  dan  huruf- huruf yang ada di kotak Teka Teki Silang dengan menggunakan Algoritma Backtracking dan Brute Force ” menyimpulkan bahwa game Teka Teki Silang dapat  menggunakan algoritma Backtracking dan Brute Force . untuk mencocokan  jawaban dengan kata  kunci pada  game  Teka  Teki  Silang, dan  dari  penelitian  yang  kedua  yang  dilakukan  oleh  “Rizky  Ivan Darmawan, Anif Hanifa Setianingrum, Arini ” dengan judul “Implementasi Algoritma Boyer Moore Pada Aplikasi Kamus Istilah Kebidanan Berbasis Web“  menyimpulkan bahwa  Algoritma Boyer Moore dapat  diterapkan di  aplikasi  permainan Teka Teki Silang dalam melakukan pencocokan kata[4].
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin
Dari penjelasan di atas maka penyusun ingin menerapkan algoritma boyer moore pada game teka-teki silang dalam melakukan  pencocokan  kata.  Adapun  game  tersebut  penulis  bangun  dalam  sebuah  aplikasi  android  karena  sistem  oprasi android merupakan sistem operasi yang sangat umum digunakan oleh kalangan remaja.

## 2. METODOLOGI PENELITIAN

## 2.1 String Matching
String  Matching adalah  proses  pencarian  semua  kemunculan query yang  selanjutnya  disebut attern kedalam  string  yang lebih  pajang  (teks). Pattern di  lambangkan  dengan x=x[0..m-1] dan  panjangnya  adalah m .  Teks  dilambangkan  dengan y=y[0…n-1] dan  panjangnya  adalah n .  Kedua string terdiri  dari  sekumpulan  karakter  yang  disebut    alfabet  yang dilambangkan    dengan  ∑  dan  mempunyai  ukuran  σ. String  matching dibagi  menjadi  dua,  yakni exact  matching dan heuristic atau statistical matching [2].

## 2.2 Teka-teki Silang
Teka-teki silang merupakan suatu permainan yang mengandalkan pengetahuan dan ketelitian dengan mengisikan kotak- kotak kosong yang telah disediakan dengan menggunakanhuruf sehingga membentuk sebuah jawaban yang sesuai dengan pertanyaan atau petunjuk[3].

## 2.3 Algoritma Boyer Moore
Algoritma  Boyer-Moore  adalah  salah  satu  algoritma  pencarian  string  yang  dipublikasikan  oleh  Robert  S.  Boyer  dan  J. Strother Moore pada tahun 1977. Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi yang umum tidak  seperti  algoritma  pencarian  string  lain,  algoritma  Boyer-Moore  mulai  mencocokkan  karakter  dari  sebelah  kanan pattern.  Ide  dibalik  algoritma  ini  adalah  bahwa  dengan  memulai  pencocokkan  karakter  dari  kanan,  dan  bukan  dari  kiri, maka  akan  lebih  banyak  informasi  yang  didapat.  Secara  sistematis,  langkah-langkah  yang  dilakukan  algoritma Boyer Moore pada saat mencocokkan string [4]–[9] , adalah :
1. Algoritma Boyer-Moore mulai mencocokkan pattern pada awal teks.
2. Dari  kanan  ke  kiri,  algoritma  ini  akan  mencocokkan  karakter  per  karakter  pattern  dengan  karakter  di  teks  yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
a.  Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
b.  Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad- character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

## 3. HASIL DAN PEMBAHASAN
Teka  Teki  Silang  ini  sebuah  permainan  menyusun  huruf-huruf  untuk  membentuk  sebuah  kata  yang  benar  dalam  Bahasa Indonesia, maka didalam permainan ini memiliki penyimpan data (database) kata yang benar, sehingga huruf yang diacak pada kotak yang telah ditentukan dapat  disusun oleh pemain sehingga menjadi  sebuah kata dalam Bahasa Indonesia, lalu dapat dibandingkan jawaban tersebut dengan yang ada pada tabel teka teki silang dalam database, setelah dibanding dengan data  kata  yang  ada  di  database,  apabila  terjadi  kecocokan  antara  jawaban  pemain  dan  database  maka  jawaban  pemain dinyatakan  benar,  tetapi  jika  jawaban  pemain  tidak  cocok  dengan  database  yang  ada  maka  jawaban  pemain  dinyatakan salah dan harus menyusunnya kembali sampai sesuai dengan yang ada didalam database tersebut .
Penulis menerapkan algoritma Boyer Moore pada permaian teka teki silang untuk  melakukan proses perbandingan jawaban pemain dengan kata yang sebenarnya. Dalam proses pencocokan tersebut algoritma boyer moore menggunakan 2 heuristic  yaitu  match  heuristic  dan  bad  character  heuristic  untuk  menentukan  sejauh  mana  dilakukan  pergeseran  dalam proses  pencocokannya.  Sebelum  melakukan  pencocokan  pada  game  teka  teki  silang  penulis  mempersiapkan  database jawaban seperti yang telah dijelaskan. Berikut contoh database kata yang disediakan unruk  game teka teki silang.
Tabel 1. Database Kata Teka Teki Silang Index Kata 1 Buaya 2 Ayam 3 Angsa 4 Gajah 5 Jerapah 6 Rubah 7 Harimau 8 Musang 9 Lintah 10 Ikan
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin
Index Kata 11 Nyamuk 12 Babi

## 3.2 Penerapan Algoritma Boyer Moore
Implementasi algoritma Boyer Moore pada penelitian ini yaitu untuk mendapatkan hasil pencocokan kata pada Game Teka Teki  Silang.  Penerapan  algoritma  Boyer  Moore  yang  pertama  yaitu  pencocokan  karakter pattern SUMANG  pada text MUSANG,  kata  sumang  diasumsikan  sebagai  sebagai  teks  yang  diisi  pada  teka  teki  silang  index  8.  Proses  selanjutnya adalah pengecekan teks teka teki silang index 8 apakah ada di dalam database. Bila teks index tersebut ada, maka jawaban yang diisi benar, bila tidak sama maka salah.
Tabel 2. Nilai OH dan MH pada pattern penyelesaian :
Pattern (P) S U M A N G Occurrence Heuristic (OH) 5 4 3 2 1 0 MacthHeuristik (MH) 5 5 5 5 5 1
Tahapan pencocokan string untuk pencarian karakter pattern SUMANG pada text MUSANG adalah sebagai berikut ini : 1. Tahap Pertama
Pada tahap pertama, pencocokan string pattern dimulai dengan deretan string text yang pertama “G“.
Tabel 3. Processing Tahap Pertama
1 2 3 4 5 6 M  U S A N G S U M  A N G
Pada  tahap  ini  karakter  G pattern dengan  karakter  G text yang  sejajar  sesuai  maka  dapat  dilanjutkan  ketahap berikutnya.
2. Tahap Kedua
Pada tahap kedua, terjadi perbandingan karakter “N” pada text dengan karakter “N” pada pattern.
Tabel 4. Processing Tahap Kedua
1 2 3 4 5 6 M  U S A N G S U M  A N G
Pada tahap ini pattren N dengan text N sesuai maka dapat dilanjutkan ketahap berikutnya. 3. Tahap Ketiga
Pada tahap ketiga, terjadi perbandingan karakter “A” pada text dengan karakter “A” pada pattern.
Tabel 5. Processing Tahap Ketiga
1 2 3 4 5 6 M U S A N G S U  M  A N G
Pada tahap ini karakter pattern A sesuai dengan karakter text A maka dapat dilanjutkan ketahap berikutnya. 4. Tahap Keempat
Pada tahap keenam, terjadi perbandingan karakter “S” pada text dengan karakter “M” pada pattern.
Tabel 6. Processing Tahap Keenam
1 2 3 4 5 6
M  U S A N G
S U M  A N G
Pada tahap ini karakter pattern M tidak sesuai dengan karakter text S maka proses pencocokan tidak dapat dilanjutkan ketahap berikutnya.
Keterangan: jadi pada percobaan pencocokan karekter string diatas dinyatakan salah.
Penerapan  algoritma  boyer  moore  yang  kedua  yaitu  pencocokan  karakter pattern MUSANG  pada text MUSANG, kata musang diasumsikan sebagai teks yang diisi pada teka teki silang index 8. Proses selanjutnya adalah pengecekan teks teka teki silang index 8 apakah ada di  dalam database. Bila teks index tersebut  ada, maka jawaban yang diisi  benar, bila tidak sama maka salah.
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin
Tabel 7. Nilai OH dan MH pada pattern penyelesaian : Pattern (P) M U S A N G Occurrence Heuristic (OH) 5 4 3 2 1 0 MacthHeuristik (MH) 5 5 5 5 5 1
Tahapan pencocokan string untuk pencarian karakter pattern MUSANG pada text MUSANG adalah sebagai berikut ini : 1. Tahap Pertama
Pada tahap pertama, pencocokan string pattern dimulai dengan deretan string text yang pertama “G“.
Tabel 8. Processing Tahap Pertama 1 2 3 4 5 6 M  U S A N G M  U S A N G
Pada  tahap  ini  karakter  G pattern dengan  karakter  G text yang  sejajar  sesuai  maka  dapat  dilanjutkan  ketahap berikutnya.
2. Tahap Kedua
Pada tahap kedua, terjadi perbandingan karakter “N” pada text dengan karakter “N” pada pattern.
Tabel 9. Processing Tahap Kedua
1 2 3 4 5 6 M  U S A N G M  U S A N G
Pada tahap ini pattren N dengan text N sesuai maka dapat dilanjutkan ketahap berikutnya.
3. Tahap Ketiga
Pada tahap ketiga, terjadi perbandingan karakter “A” pada text dengan karakter “A” pada pattern.
Tabel 10. Processing Tahap Ketiga
1 2 3 4 5 6 M  U S A N G M  U S A N G
Pada tahap ini karakter pattern A sesuai dengan karakter text A maka dapat dilanjutkan ketahap berikutnya. 4. Tahap Keempat
Pada tahap keempat, terjadi perbandingan karakter “S” pada text dengan karakter “S” pada pattern.
Tabel  11. Processing Tahap Keempat
1 2 3 4 5 6 M  U S A N G M  U S A N G
Pada tahap ini karakter pattern S sesuai dengan karakter text S maka dapat dilanjutkan ketahap berikutnya. 5. Tahap Kelima
Pada tahap kelima, terjadi perbandingan karakter “U” pada text dengan karakter “U” pada pattern.
Tabel 12. Processing Tahap Kelima
1 2 3 4 5 6 M  U S A N G M  U S A N G
Pada tahap ini karakter pattern U sesuai dengan karakter text U maka proses pencocokan dapat dilanjutkan. 6. Tahap Keenam
Pada tahap keenam, terjadi perbandingan karakter “M” pada text dengan karakter “M” pada pattern.
Tabel 13. Processing Tahap Kedelapan
1 2 3 4 5 6
M  U S A N G M  U S A N G
Pada  tahap  ini  karakter pattern M sesuai  dengan  karakter text M  maka  proses  pencocokan  selesai  karena  semua karakter berhasil dicocokan.
Keterangan: pada percobaan pencocokan karekter string diatas dinyatakan benar.
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin

## 3.3 Tampilan Program
Tampilan  program  adalah  tampilan  aplikasi  permainan  Teka  Teki  Silang yang  diimplementasikan  pada  penelitian  ini. Tampilan program  berfungsi  sebagai  media komunikasi  antara user atau pengguna dengan aplikasi permainan  Teka Teki Silang pada penelitian ini.
1. Form Menu Utama
Form menu utama merupakan media penghubung pengguna aplikasi dengan aplikasi permainan Teka Teki Silang. Pada menu  utama  ini  terdapat  3  sub  menu  yakni  Play,  Update,  dan  Exit.  Menu  utama  pada  aplikasi  permainan  Teka  Teki Silang pada penelitian ini seperti gambar berikut :
Gambar 1. Form Menu Utama
2. Form Tampilan Halaman Permainan
Halaman  permainan  akan  ditampilkan  setelah  pemain  menekan  tombol  play    pada  halaman  menu  utama.  Halaman permainan menampilkan  point, level ,  score,  help, dan check. Tampilan  halaman permainan Teka Teki  Silang yang dibangun oleh penulis pada penelitian ini seperti gambar berikut :
Gambar 2. Form Tampilan Halaman Permainan
Selanjutnya tampilan menu help yang berfungsi sebagai bantuan permainan dari sistem yang menggunakan algoritma Boyer Moore sebagai metodenya. Apabila mengklik tombol help maka sistem akan membantu pemain dalam mencari
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin
kata  yang  tepat  dalam  mencari  sebuah  kata  dalam  salah  satu    kolom  kosong  yang  ada.  Berikut  tampilan  apabila memilih menu help pada permainan Teka Teki Silang pada penelitian ini seperti gambar berikut :
Gambar 3. Form Tampilan Menekan Tombol Help 3. Form Tampilan Score
Tampilan  score  merupakan  hasil  akhir  dari  permainan  Teka  Teki  Silang karena  pemain  dapat  menyelesaikan menyusun huruf menjadi kata yang benar. Berikut tampilan score pada permainan Teka Teki Silang :
Gambar 4. Form Tampilan Score

## 4. KESIMPULAN
Berdasarkan  hasil  akhir  pemecahan  masalah  permainan  Teka  Teki  Silang  pada  penelitian  maka  penulis  menguraikan beberapa  kesimpulan.  Adapun  kesimpulan-kesimpulan  tersebut  antara  lain  pada  aplikasi  Teka  Teki  Silang  ini  Algoritma Boyer Moore dapat mencocokkan jawaban, algoritma Boyer Moore dapat diterapkan pada aplikasi Teka Teki Silang dalam melakukan  pencocokan  kata  dari  pertanyaan  kejawaban  yang  ada  pada  sistem database dan  aplikasi  Teka  Teki  Silang berhasil dibangun dan dapat menerapkan algoritma Boyer Moore.
Vol 2, No 6, November 2021, Hal 378-384 ISSN 2722-7987 (Media Online) Website https://ejurnal.seminar-id.com/index.php/tin

## REFERENCES
[1] Wikipedia, “Teka-teki silang,” 2019. .
[2] C. Charras and T. Lecroq, Handbook of Exact String-Matching Algorithms . London: King College London Publication, 2004.
[3] M. S. Syakur and Wijanarto, “Generator Teka-Teki Silang Menggunakan Algoritma Backtracking dan Brute Force,” J. Appl. Intell. Syst. UDINUS , vol. 1, no. 1, pp. 12–21, 2016.
[4] A. Darmawan dan Setianingrum, “Implementasi Algoritma Boyer Moore Pada Aplikasi Kamus Istilah Kebidanan Berbasis Web,” J. Sist. Inf. , vol. II, no. April, pp. 53–62, 2018.
[5] G. L. Ginting, “Implementasi Algoritma Boyer-Moore Pada Aplikasi Pengajuan Judul Skripsi Berbasis Web,” Pelita Inform. , vol. 3, no. 1, 2014.
[6] S. S. Sari and G. Ginting, “Implementasi Algoritma Boyer Moore Pada Kamus Perbedaan Kata Dalam Bahasa Inggris British dan Bahasa Inggris America,” J. Informatics Manag. Inf. Technol. , vol. 1, no. 2, pp. 74–78, 2021.
[7] A. Fau, M. Mesran, and G. L. Ginting, “Analisa Perbandingan Boyer Moore Dan Knuth Morris Pratt Dalam Pencarian Judul Buku Menerapkan  Metode  Perbandingan  Eksponensial  (  Studi  Kasus :  Perpustakaan  STMIK  Budi  Darma  ),” J.  Times  (Technology Informatics Comput. Syst. , vol. 6, no. 1, pp. 12–22, 2017.
[8] M. Ayu Permatasari Siahaan, “Kamus Nama Bayi Beserta Maknanya,” Pelita Inform. , vol. 17, pp. 97–101, 2018.
[9] Sulastri,  “Implementasi  Algoritma Turbo  Boyer  Moore  Pada  Aplikasi  Tarian  Tradisional  Berbasis  Android,” Bull.  Comput.  Sci. Res. , vol. 1, no. 3, pp. 93–97, 2020.