Implementasi Algoritma Backtracking Dengan Optimasi Menggunakan Teknik Hidden Single Pada Penyelesaian Permainan Sudoku

Implementasi Algoritma Backtracking Dengan Optimasi Menggunakan Teknik Hidden Single Pada Penyelesaian Permainan Sudoku Valdo Septiansen Widjaja

Dodick Z. Sudirman

Program Studi Teknik Informatika Fakultas Teknologi Informasi dan Komunikasi Universitas Multimedia Nusantara Gading Serpong, Tangerang, Indonesia [email protected]

Program Studi Teknik Informatika Fakultas Teknologi Informasi dan Komunikasi Universitas Multimedia Nusantara Gading Serpong, Tangerang, Indonesia [email protected]

Abstrak—Perkembangan teknologi informasi telah merambah dalam berbagai bidang, salah satunya bidang permainan seperti puzzle atau teka-teki. Sudoku adalah sebuah permainan teka-teki logika yang cukup menarik untuk dimainkan. Hingga saat ini permainan Sudoku telah populer di kalangan masyarakat. Berbagai jenis variasi puzzle dan tingkat kesulitan yang terdapat dalam Sudoku membuat para ilmuwan berusaha untuk melakukan penelitian terhadap permainan ini. Penggunaan algoritma backtracking dalam penyelesaian puzzle Sudoku merupakan salah satu penelitian yang telah dilakukan sebelumnya. Hanya saja, algoritma ini masih membutuhkan waktu yang cukup lama dalam melakukan komputasi penyelesaian puzzle Sudoku. Dalam penelitian ini, dibangun sebuah aplikasi untuk mengoptimalkan algoritma backtracking dalam menyelesaikan puzzle Sudoku menggunakan sebuah teknik optimasi yang disebut teknikhidden single.Aplikasi ini telah berhasil mengimplementasikan teknik hidden single ke dalam algoritma backtracking yang digunakan. Hasil uji coba penelitian menunjukkan bahwa dengan menggunakan optimasi teknik hidden single, algoritma backtracking mampu mengoptimalkan waktu dan kinerja komputasi pada penyelesaian puzzle Sudoku. Kata kunci—Sudoku, permainan, logika, puzzle, teka-teki, algoritma, optimasi, backtracking, hidden single.

I.

PENDAHULUAN

Perkembangan teknologi informasi terjadi dalam berbagai bidang, salah satunya dalam bidang permainan[6]. Selain sebagai hiburan, permainan juga dapat menjadi suatu hal yang menantang ataupun untuk mengasah kemampuan otak pemain, seperti permainan teka-teki yang saat ini sedang populer di kalangan masyarakat[8]. Sudoku adalah sebuah permainan teka-teki angka yang berbasis logika[9]. Pada umumnya, sebuah puzzle Sudoku terdiri dari 81 kotak yang disusun menjadi 9 baris, 9 kolom, dan 9 subbagian. Tujuan utama dari permainan ini adalah mengisi seluruh kotak tersebut dengan angka 1 sampai 9[1]. Permainan Sudoku mengharuskan pemainnya untuk berpikir secara logis sesuai dengan aturan-aturan permainan yang ada. Namun demikian, para ilmuwan komputer dan matematikawan berusaha untuk meneliti permainan ini karena tingkat kerumitan dan banyaknya variasi puzzle Sudoku yang masing-

Seminar Nasional Aplikasi Teknologi Informasi (SNATI) 2013 Yogyakarta, 15 Juni 2013

masing memiliki suatu solusi unik[4]. Salah satu teknik sederhana dan paling umum yang sering digunakan untuk menyelesaikan permainan Sudoku adalah teknik hidden single[1]. Meskipun begitu, pada beberapa variasi puzzle Sudoku tertentu tidak dapat diselesaikan hanya dengan menggunakan teknik hidden single saja. Algoritma backtracking merupakan perbaikan dari algoritma brute-force dan algoritma exhaustive-search, di mana algoritma ini membangun pohon ruang status (statespace tree) untuk menemukan solusi[3]. Prinsip dari algoritma backtracking adalah jika terjadi kesalahan dalam pencarian solusi pada sebuah node, maka akan dilakukan backtrack ke node sebelumnya. Meski begitu, algoritma ini menjadi tidak efisien jika kandidat solusi yang ditemukan sama dengan kandidat solusi yang ditemukan pada algoritma exhaustivesearch. Berdasarkan pemaparan tersebut di atas, maka dilakukan penelitian untuk melakukan implementasi teknik hidden single pada algoritma backtracking dengan tujuan melakukan optimasi pada algoritma tersebut sehingga dapat membantu dalam menyelesaikan puzzle Sudoku dengan lebih mudah. II.

ALGORITMA BACKTRACKING

Algoritma backtrack pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950[10]. Dalam perkembangan algoritma ini, beberapa ahli seperti Rwalker, Golomb, dan Baumert menyajikan uraian umum tentang backtrack dan penerapannya dalam berbagai persoalan dan aplikasi. Algoritma backtracking adalah sebuah algoritma yang berbasis depth-first search (DFS) dalam pencarian solusi pada pohon ruang status yang dibangun secara dinamis. Algoritma ini membangun solusi parsial (partial solution) dari sebuah kandidat solusi dan mengevaluasi solusi parsial tersebut pada suatu waktu. Jika solusi parsial yang dibangun tidak memenuhi syarat, maka kandidat solusi tersebut tidak akan dibangun lebih lanjut dan dilakukan backtrack ke kandidat solusi lain yang memenuhi syarat. Algoritma backtracking dilakukan secara berulangulang hingga menemukan sebuah solusi yang sesuai dengan syarat.

K-1

ISSN: 1907 - 5022

III.

SUDOKU DAN TEKNIK HIDDEN SINGLE

Sebuah permainan teka-teki Sudoku terdiri dari 9x9 kotak, yang dibagi menjadi 9 subbagian berukuran 3x3 kotak[2]. Beberapa kotak telah diisi dengan angka-angka tertentu (antara 1 sampai 9) sebagai petunjuk awal permainan. Tujuan dari permainan Sudoku adalah untuk meletakkan sebuah angka (antara 1 sampai 9) ke dalam sebuah kotak kosong dengan aturan masing-masing baris, kolom, dan subbagian hanya boleh menampilkan angka tersebut sekali.

Gambar 1. Contoh Pohon Ruang Status Algoritma Backtracking[10]

Langkah-langkah pencarian solusi backtracking adalah sebagai berikut[10].

pada

algoritma

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Simpul yang telah dilahirkan dinamakan simpul hidup dan simpul hidup yang diperluas dinamakan simpul-E (Expand node). 2. Jika lintasan yang diperoleh dari perluasan simpul-E tidak mengarah ke solusi, maka simpul itu akan menjadi simpul mati yang tidak dapat diperluas lagi. 3. Jika posisi terakhir ada di simpul mati, maka pencarian dilakukan dengan membangkitkan simpul anak yang lainnya dan jika tidak ada simpul anak maka dilakukan backtracking ke simpul induk.

Gambar 3. Contoh Sudoku Valid Berukuran 9x9 kotak[11]

Secara umum, permainan Sudoku dapat diselesaikan secara manual dengan kombinasi beberapa teknik dasar, antara lain sebagai berikut[5]. 1) Pemindaian (scanning) Berupa proses memindai baris atau kolom untuk mengidentifikasi baris mana yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu kotak dengan membuang nilai-nilai yang tidak mungkin.

4. Pencarian dihentikan jika kita telah menemukan solusi atau tidak ada simpul hidup yang dapat ditemukan.

2) Penandaan (marking) Penandaan berupa analisis logika, dengan menandai kandidat angka yang dapat dimasukkan ke dalam sebuah kotak. 3) Analisis (analyzing) Analisis berupa eliminasi kandidat, di mana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah kotak hanya mempunyai sebuah kandidat. Gambar 2. Contoh Pseudocode Algoritma Backtracking[7]

Seminar Nasional Aplikasi Teknologi Informasi (SNATI) 2013 Yogyakarta, 15 Juni 2013

Teknik hidden single adalah salah satu teknik dalam menyelesaikan permainan Sudoku[11]. Teknik hidden singlebertujuan untuk mencari kandidat tunggal dari sebuah kotak, tetapi kandidat tunggal tersebut agak tersembunyi. Teknik ini dilakukan dengan mencari kandidat yang unik pada suatu baris, kolom, atau subbagian. Sebuah kotak yang memiliki hidden single dapat memiliki lebih dari satu kandidat,

K-2

ISSN: 1907 - 5022

tetapi salah satu kandidat tersebut adalah unik pada suatu baris, kolom, atau subbagian.

seluruh kandidat angka telah dicoba sebelumnya, maka dilakukan proses backtrack. 6) Backtrack Proses ini melakukan backtrack untuk kembali ke kotak (node) yang telah diproses sebelumnya.Kemudian dilakukan pengecekan kembali pada kotak tersebut. 7) Fill the empty cell with one of the candidate number Proses ini melakukan pengisian pada kotak kosong dengan salah satu kandidat angka yang sesuai dengan aturan permainan Sudoku. B. Hasil Uji Coba Pengujian dilakukan dengan membandingkan algoritma backtracking biasa dengan algoritma backtracking hidden single dalam menyelesaikan puzzle Sudoku. Pengujian dilakukan terhadap beberapa tingkat kesulitan yang masingmasing berjumlah 100 puzzle. Berikut akan dijelaskan hasil pengujian salah satu tingkat kesulitan. TABLE I.

Gambar 4. Contoh Teknik Hidden Single Pada Baris[11]

Eksp. Ke-

Gambar 4 menunjukkan salah satu kondisi hidden single pada baris. Kotak warna kuning, yaitu pada baris ke-1, kolom ke-5, memiliki hidden single, yaitu angka 2. Pada subbagian ke-1, sudah terdapat angka 2 di baris ke-2 sehingga kotak kosong pada baris ke-1, kolom ke-1 tidak mungkin diisi dengan angka 2. Kemudian pada kolom ke-8, sudah terdapat angka 2 di baris ke-5 sehingga pada baris ke-1, kolom ke-8 tidak mungkin diisi dengan angka 2. Maka pada baris ke-1, yang bisa diisi dengan angka 2 hanya pada kolom ke-5. IV.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

IMPLEMENTASI DAN UJI COBA

A. Implementasi Algoritma Backtracking Hidden Single Implementasi algoritma backtracking hidden single terdiri dari beberapa proses, antara lain sebagai berikut. 1) Find and save any empty cell into array Proses ini melakukanpencarian dan memasukkan setiap kotak kosong yang ada pada puzzle ke dalam sebuah array. 2) Find and save any candidate number in the empty cell Proses ini melakukan pengecekan dan menyimpan kandidat angka yang mungkin pada sebuah kotak. 3) Check if is there any candidate Proses ini melakukan pengecekan apakah kotak tersebut memiliki kandidat angka. Jika tidak ada kandidat angka pada kotak tersebut, maka dilakukan proses backtrack. 4) Check if is there any hidden single number Proses ini melakukan pengecekan apakah kotak tersebut memiliki hidden single number. Jika terdapat hidden single number, maka dilakukan proses backtrack.

HASIL PENGUJIAN PENYELESAIAN SUDOKU TINGKAT KESULITAN HARD

Jumlah kotak Waktu Jumlah Backtrack Backtrack Optimasi Backtrack kosong Backtrack Backtrack H. Single H. Single (45 - 49) 45 941 729 24 9 8 45 7173 2355 229 46 48 45 5308 2883 224 82 44 45 5260 2447 129 72 26 45 821 567 19 0 8 45 632 536 10 2 4 45 559 511 5 0 3 45 4217 5337 164 46 30 45 1102 709 31 7 9 45 8120 3415 362 107 46 45 6682 1806 282 31 36 45 6131 4499 266 167 38 45 2471 2472 49 38 10 45 441 441 1 0 1 45 13110 5281 538 165 53 45 4220 3251 178 102 38 45 6321 2895 281 67 59 45 737 759 0 0 0 45 593 469 7 0 3 45 1955 948 70 18 10 45 1073 788 28 6 11 46 3528 2423 146 66 35 46 9791 2453 440 78 24 46 5486 1564 236 38 21 46 715 552 8 1 4 46 1418 1145 47 29 8 46 460 486 1 0 1 46 3733 2334 157 69 31 46 983 742 24 9 5

5) Check if all candidates have been tried Proses ini melakukan pengecekan terhadap seluruh kandidat angka yang telah dicoba sebelumnya. Jika

Seminar Nasional Aplikasi Teknologi Informasi (SNATI) 2013 Yogyakarta, 15 Juni 2013

K-3

ISSN: 1907 - 5022

TABLE I.

Eksp. Ke30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

TABLE I.

HASIL PENGUJIAN PENYELESAIAN SUDOKU TINGKAT KESULITAN HARD (LANJUTAN)

Jumlah kotak Waktu Jumlah Backtrack Backtrack Backtrack Optimasi kosong Backtrack Backtrack H. Single H. Single (45 - 49) 46 20813 8391 960 209 180 46 9283 4943 401 169 58 46 1269 525 38 0 3 46 1792 1348 58 20 25 46 818 631 13 3 5 46 702 547 10 0 4 47 12795 8379 514 286 118 47 2237 1563 84 34 24 47 13700 6010 571 199 83 47 774 690 14 6 6 47 1940 1080 71 21 10 47 8828 5539 369 206 49 47 4786 3685 210 133 35 47 2540 2151 101 70 18 47 513 506 3 1 2 47 18288 7114 849 185 149 47 9195 3162 274 77 57 47 4040 3172 170 103 33 47 3561 1778 146 36 32 47 3384 2378 74 47 14 47 59611 25151 2703 838 397 47 13334 4005 603 104 76 47 7545 5935 332 210 68 47 951 912 23 23 0 47 4460 2980 190 86 42 47 15983 1837 710 33 33 48 23445 17577 1065 638 209 48 5087 2444 210 60 38 48 12774 2105 572 57 25 48 17699 5371 824 158 83 48 1288 623 35 1 8 48 16127 7610 656 267 94 48 32184 18855 1383 670 236 48 6233 4604 269 157 52 48 73803 27744 3462 862 265 48 3808 1452 158 28 22 48 2005 1076 70 7 21 48 14461 9554 657 350 101 48 2637 2226 98 76 13 48 6472 4459 277 146 45 48 577 608 4 0 3 48 7848 4136 265 129 54 48 2762 949 108 12 14 48 59469 38091 2326 1148 499 48 140302 90179 5076 2658 933 48 2259 1325 83 16 11 48 6648 1468 81 20 21 48 13296 8312 499 253 108 48 42440 16337 1904 592 158 49 22500 11363 1051 409 147 49 29696 14490 1402 512 189 49 5216 4054 215 140 38 49 3193 2127 124 55 29 49 11054 9087 492 350 81 49 1157 897 10 0 2 49 16524 7703 761 302 55

Seminar Nasional Aplikasi Teknologi Informasi (SNATI) 2013 Yogyakarta, 15 Juni 2013

Eksp. Ke86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

HASIL PENGUJIAN PENYELESAIAN SUDOKU TINGKAT KESULITAN HARD (LANJUTAN)

Jumlah kotak kosong (45 - 49) 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49

Waktu Jumlah Backtrack Backtrack Backtrack Optimasi Backtrack Backtrack H. Single H. Single 8792 7966 397 297 82 7449 3404 180 134 17 140159 22795 5673 663 264 5445 3381 234 103 45 2162 1818 82 55 14 200309 143237 7544 4800 1571 19405 7327 824 209 122 9270 8253 416 215 63 294944 102372 10405 2751 1418 66455 50819 2784 1575 693 224351 118881 8223 3355 1462 15112 12227 672 295 98 11348 7441 492 262 88 15841 11606 625 334 83 5952 3508 249 92 37

Pada TABLE I di atas menunjukkan hasil pengujian penyelesaian Sudoku terhadap 100 puzzle dengan jumlah awal kotak kosong secara acak antara 45 sampai 49 buah. Parameter yang diuji pada penelitian ini adalah waktu penyelesaian (diukur dalam milliseconds) dan jumlah backtrack yang dilakukan. Terlihat pada tabel tersebut bahwa 95% soal diselesaikan lebih cepat dengan menggunakan algoritma backtracking hidden single, sedangkan jumlah backtrack yang dilakukan oleh backtracking hidden single lebih sedikit daripada jumlah backtrack yang dilakukan oleh backtrack biasa.

Gambar 5. Chart Time Hasil Pengujian Penyelesaian 100 Puzzle Sudoku Tingkat Kesulitan Hard

Pada Gambar 5 di atas menunjukkan hasil statistik waktu penyelesaian dari hasil pengujian yang telah dilakukan, berdasarkan TABLE I. Garis biru menggambarkan waktu penyelesaian backtracking biasa dan garis merah menggambarkan waktu penyelesaian backtracking hidden single. Selain itu terdapat juga rata-rata waktu penyelesaian dari masing-masing algoritma backracking. Terlihat pada gambar tersebut bahwa rata-rata waktu penyelesaian backtracking biasa, dengan waktu 19370 milliseconds, lebih lama daripada rata-rata waktu penyelesaian backtracking hidden single, dengan waktu 9810 milliseconds.

K-4

ISSN: 1907 - 5022

B. Saran Saran untuk penelitian dan pengembangan aplikasi selanjutnya adalah sebagai berikut. 1. Adanya keterbatasan pada saat aplikasi berjalan, yaitu terkadang aplikasi menjadi not responding pada saat aplikasi melakukan uji coba. Diharapkan pada penelitian selanjutnya, penulisan kode menggunakan threading sehingga aplikasi dapat berjalan dengan lebih baik. 2. Aplikasi dapat dikembangkan dengan menambahkan optimasi pada algoritma backtracking dengan menggunakan teknik-teknik penyelesaian Sudoku lainnya, seperti hidden pair atau hidden triple. Gambar 6. Backtrack & Optimation Chart Hasil Pengujian Penyelesaian 100 Puzzle Sudoku Tingkat Kesulitan Hard

Pada Gambar 6 di atas menunjukkan hasil statistik jumlah backtrack dari hasil pengujian yang telah dilakukan, berdasarkan TABLE I. Garis biru menggambarkan jumlah backtrack yang dilakukan algoritma backtracking biasa dan garis merah menggambarkan jumlah backtrack yang dilakukan algoritma backtracking hidden single. Selain itu terdapat juga rata-rata jumlah backtrack dari masing-masing algoritma backracking. Terlihat pada gambar tersebut bahwa rata-rata jumlah backtrack yang dilakukan algoritmabacktracking biasa, dengan 763 kali, lebih banyak daripada rata-rata jumlah backtrack yang dilakukan algoritma backtracking hidden single, dengan 295 kali. Hasil pengujian penyelesaian 100 puzzle Sudoku tingkat kesulitan hard di atas menunjukkan bahwa algoritma backtracking hidden single lebih efisien daripada algoritma backtracking biasa, dilihat dari segi waktu penyelesaian dan jumlah backtrack yang dilakukan. V.

KESIMPULAN DAN SARAN

A. Kesimpulan Kesimpulan yang diperoleh dari penelitian antara lain sebagai berikut. 1. Optimasi pada algoritma backtracking dengan menggunakan teknik hidden single untuk menyelesaikan permainan Sudoku telah berhasil diimplementasikan dan diuji. 2. Optimasi pada algoritma backtracking dengan menggunakan teknik hidden single mampu mengoptimalkan waktu penyelesaian dan meminimalkan jumlah penggunaan backtrack pada algoritma backtracking biasa dalam menyelesaikan permainan Sudoku.

DAFTAR PUSTAKA [1]

D. Adler & Associates. 2012. “Sudoku Solver Manual Version 1.6.0”. Dalam http://www.dadler.net/. [2] Lee, Wei-Meng. 2006. Programming Sudoku. New York: SpringerVerlag New York, Inc. [3] Levitin, Anany & Maria Levitin. 2011. Algorithmic Puzzles. New York: Oxford University Press, Inc. [4] Majumder, Abhisek dkk. 2010. “The Game of Sudoku-Advanced Backtrack Approach”. Dalam International Journal of Computer Science and Network Security, VOL.10 No.8, August 2010. [5] Mujaddid, Sibghatullah. 2009. “Penerapan Algoritma Runut-Balik (Backtracking) Dalam Penyelesaian Permainan Sudoku”. Dalam http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/. [6] Noviyanto, Fiftin. 2008. “Membangun Sistem Pembelajaran Pengenalan Bentuk Untuk Anak Berbasis Multimedia Dan Game Interaktif”. Dalam http://www.journal.uad.ac.id/. [7] Sulun, Hafni Syaeful & Rinaldi Munir. 2010. “Pembangkit Teka-Teki Silang Dengan Algoritma Backtracking Serta Aplikasi Permainannya Yang Berbasis Web”. Dalam Jurnal Informatika, Vol.4 No.2, Juli 2010. [8] Sutanto, Hendy. 2009. “Combination of BFS and Brute Force Algorithm Implementation in Futoshiki Puzzle Game”. Dalam http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/. [9] Syam, Umi Fadilah Wardati. 2007. “Perumusan Sudoku Dengan Solusi Unik Menggunakan Algoritma Pencabangan Dan Pembatasan (Branch And Bound)”. Dalam http://informatika.stei.itb.ac.id/~rinaldi.munir/ Stmik/. [10] Teneng, Joko Purwadi, & Erick Kurniawan. 2010. “Penerapan Algoritma Backtracking Pada Permainan Math Maze”. Dalam http://ti.ukdw.ac.id/. [11] Wihandika, Randy Cahya, Nur Rosyid Mubtada’i & Rizky Yuniar H. 2011. “Penyelesaian Puzzle Sudoku Menggunakan Algoritma Genetika”. Dalam http://www.eepis-its.edu/.

3. Tingkat kesulitan sebuah puzzle Sudoku mempengaruhi hasil uji coba kedua algoritma yang telah duji. Semakin rumit tingkat kesulitan puzzle, maka perbedaan waktu penyelesaian dan jumlah backtrack yang digunakan semakin besar.

Seminar Nasional Aplikasi Teknologi Informasi (SNATI) 2013 Yogyakarta, 15 Juni 2013

K-5

ISSN: 1907 - 5022