Transcription
View metadata, citation and similar papers at core.ac.ukbrought to you byCOREprovided by ejournal.nusamandiri.ac.id (STMIK Nusa Mandiri)Vol. X No. 2, September 2013Jurnal Techno Nusa MandiriPENYELESAIAN PUZZLE SUDOKU MENGGUNAKAN ALGORITMABRUTE FORCE DAN BACKTRACKINGAndreas Yusuf1 dan Hendra2Program Studi Teknik InformatikaSTMIK Nusa MandiriJl. Kramat Raya No. 25 Jakarta [email protected]; [email protected] games is the most popular Numeric Puzzle Games in the world. This game requires you tofill in the numbers on a blank column matrix with certain regulations. This study will discuss howto solve Sudoku primarily to take advantage of the Brute Force Algorithm and Backtracking bytrying all possible contents of the box element of the matrix. This testing process using black boxmethod, where the program uses four levels of Sudoku puzzle consists of three levels of difficultybeginner level, intermediate level, advanced level, expert level, master level. Sudoku generallyconsists of a table with the number of boxes 9 x 9, which made the area (region) 3 x 3. QuestionsBeginners and Intermediate is used. Examiners performed by using an Intel Pentium III 550MHzprocessor with a 1.6 GHz Core2 Duo with clock speed 694ms and 320ms for about the first andsecond largest known differences exist at the level of the processor.Keywords: Numeric Puzzle Games, Sudoku games, Brute Force Algorithm, BacktrackingI.PENDAHULUANPermainan puzzle termasuk permainanyang membutuhkan nalar dan logika untukmenyelesaikan goal. Permainan puzzle danteka teki sangat banyak jenisnya, salahsatunya adalah teka-teki angka.PenyelesaianpuzzleSudokumenggunakan logika memerlukan waktuyang cukup lama, bila dibandingkan denganpemecahan menggunakan komputer. Sudokuadalah singkatan bahasa Jepang dari "Suujiwa dokushin ni kagiru", artinya "angkaangkanya harus tetap tunggal". Pertama kaliditerbitkan di sebuah surat kabar Perancispada 1895 dan mungkin dipengaruhi olehmatematikawan Swiss Leonhard Euler.Permainan ini sudah di kenal di mediamassa sejak abad 18, ketika permainanPuzzle Magic Squares di Prancis ramaidibicarakan. Pada awalnya pemainanSudoku hanya mengenal baris dan kolomsaja tapi dalam perkembangannya ada yangnamanya region.Tahun 1997, sudah banyak ditemukanpuzzle Sudoku dalam toko uku Jepang, dandalam 6 tahun berikutnya Sudokudikembangkan menjadi program computer.II.KAJIAN LITERATURSudoku adalah sebuah puzzle yangdidasarkan pada konsep Latin Square.Sudoku terdiri dari 3 3 kotak, masing-masing terbagi lagi menjadi sembilan kotaklebih kecil. Sehingga sebuah soal sudokumemiliki bagian-bagian yang perlu diberinama (Satsuko,2007:2).Penerapan algoritma Brute force dalamsudokudenganmencobaseluruhkemungkinan isi kotak elemen dari matriks.Misalkan solusi dari suatu permainansudokudinyatakansebagai:X (x1,x2,x3, .,x981); Dari vektor solusidiatas dapat disimpulkan bahwa denganmenggunakan algoritma Brute force makaharus membangkitkan seluruh kemungkinanvektorsolusiyangberjumlah981 1,99x1077 kemungkinan.III. METODE PENELITIANBeberapa cara untuk , Brute force, Backtracking danmetode Swordfish. Pada penelitian inimenggunakan metode algoritma Brute forcedan Backtracking lalu membandingkankeakuratan dan kecepatan dari penyelesaianpuzzle Sudoku. Algoritma Backtrackingmerupakan perbaikan dari algoritma Bruteforce, dimana solusi dapat ditemukandengan penelusuran yang lebih sedikit dandapat mencari solusi permasalahan secaralebih cepat karena tidak perlu memeriksasemua kemungkinan solusi yang ada. Hanyapencarian yang mengarah ke solusi sajayang perlu dipertimbangkan.203
Jurnal Techno Nusa MandiriVol. X No. 2, September 2013Ruang lingkup yang dikaji dalampenelitian ini yaitu pemecahan puzzleSudoku dengan algoritma Brute force danBacktracking, Algoritma yang digunakandimaksudkan untuk membandingkan waktuyang diperlukan untuk pemecahan puzzleSudoku, Puzzle Sudoku yang digunakanadalah puzzle Sudoku, Perangkat lunak yangdibangun hanya menampilkan hasil akhirdari implementasi algoritma yang telahdigunakan saja.IV. PEMBAHASANKonstruksi SistemPada perancangan program sudoku ini,menggunakan java sebagai tools. Tampilanawal dari program ini didesain sederhana,karena tujuan dari program ini adalah untukmembuktikan bahwa algoritma yangdigunakan dapat memecahkan puzzlesudoku.Prinsip dasar penyelesaian Sudokusangat sederhana: melengkapi setiap boksdan lajur agar terisi angka 1 sampai 9.Karena masing-masing terdiri dari 9 sel,maka tidak mungkin ada angka ganda dalamsetiap boks atau lajur. Setiap soal Sudokumempunyai satu solusi. Tidak yakemampuanmembedakan sembilan macam symbol.Waktuyang dibutuhkan untukmemecahkan satu puzzle yang sudahdisediakan oleh penulis dalam programdalam memecahkan puzzle yang sama, ratarata yang didapat adalah 1170 detik.SEL: Kotak terkecil yangseharusnya berisi angka.BOKS: Kotak lebih besar yangmengandung Sembilan sel, 3x3 sel.DERET: Lajur-lajur horisontalKOLOM: Lajur-lajur vertical204BLOK: Kumpulan tiga boks, verticalmaupun horizontal.Sebuah soal sodoku terdiri dari81 sel, atau 9 boks, atau 9 deret, atau9 kolom, atau 3 blok. Memulainyadapat dilakukan dari mana saja,tergantung struktur soal.Gambar 1. Sudoku dengan kotak 9 x 9Varian-varian SudokuSejak Sudoku dipopulerkan banyakvariasi puzzle Sudoku, beberapa variasinyaberkaitan dengan ukuran grid, objek isian,warna, dan ukuran dimensi. Sudoku mini /Sudoku yunior (Sudoku dengan ukuran grid4x4(subgrid 2x2) dan 6x6 (subgrid 2x3)),Multisudoku (Sudoku yang berbentukgabungan / tindihan dua atau lebih frameSudoku), Irregular Sudoku (Sudoku dengandaerah pengisian yang dibatasi), Monomino(Sudoku dengan warna sebagai bataspengisian), Kubus Sudoku / Kubus DionChurch (Sudoku dalam bentuk kubus),Oddevensudoku (Sudoku yang mengaitkankeunikan angka genap dan ganjil dengan selyang diarsir), Megasudoku (Sudoku denganukuran besar, grid 16x16 (subgrid 4x4),12x12(subgrid 3x4), dan 25x25 (subgrid5x5)).Sudoku secara umum terdiri dari tabeldengan kotak 9 x 9, yang dibuat denganregion 3 x 3. Untuk memulai permainan in i,beberapa kotak telah diisi dengan angkaangka yang menjadi petunjuk (clue). Tujuanakhir dari logika ini adalah mengisi kotakkotak yang masih kosong di mana setiapkotak diisi satu angka. Dalam setiap baris,kolom, dan region diisi dengan angka 1(satu) sampai dengan 9 (sembilan) dengan
Vol. X No. 2, September 2013kemungkinan hanya sekali. Setiap angkadalam solusi ini terjadi hanya sekali dalam 3Jurnal Techno Nusa Mandirikondisi (baris, kolom dan region).solve (int x)STARTIf (x 81)if (getValue(x, 0) ! 0 &&getValue(x, 0) getValueOriginal(x, 0))return solve(x 1)for (int i:Backtrack(x, 0))fill(x,0,0);if (!solve(x 1))if (i ! 0)fill(x, 0, i);ENDGambar 2. Penerapan konstruksi Sistem pada Puzzle Sudoku 9x9Penerapan Konstruksi sistemnya adalahsebagai berikut:1. Membuatarray yangbanyakelemennya sejumlah dengan banyakelemen matriks.2. Mengalokasikan setiap elemen arrayini dengan value, indeks baris, danindeks kolom dari elemen matriksyangbersesuaian(Penulismenggunakan x, y, value).3. Menghitungsetiapprobabilitaselemen–elemen tabel dengan prosespencarian solusi dimulai dari elementabel x0, y0 sampai x8, y81.4. Memeriksa seluruh kemungkinanangka (value) yang dapat dimilikioleh elemen tabel tersebut (terbataspada angka 1, 2, 3, 4, 5, 6, 7, 8, 9).5. Jika tidak terdapat angka yang validmaka backtrack ke elemen tabelsebelumnya dengan melihat urutanelementabelyangdiprosessebelumnya, ulangi langkah 5.6. Jika terdapat angka valid maka carielemen selanjutnya.7. Algoritma ini akan berhenti jikasudah ditemukan suatu solusi ataujika tidak terdapat kemungkinanadanya solusi.Pengujian SistemPadaprosespengujianinimenggunakan metode black box, dimanaprogram menggunakan 4 tingkatan puzzlesudoku yang terdiri dari tiga tingkatkesulitan beginners level, intermediate level,advance level, expert level, master level.Sudoku pada umumnya terdiri dari tabeldengan jumlah kotak 9 x 9, yang dibuatdengan wilayah (region) 3 x 3.Gambar 3. Pengujian sistem 4 tingkatanUntuk memulai logika pada permainanSudoku, ada beberapa kotak yang sebelumnya telah diisi dengan angka-angka yangdimana angka-angka tersebut digunakan205
Jurnal Techno Nusa MandiriVol. X No. 2, September 2013sebagai petunjuk (clue) untuk mencariangka-angka yang lain pada kotak yangbelum terisi.Tujuan dari permainan ini adalahmengisi semua kotak yang masih kosong dimana setiap kotak hanya dapat diisi oleh 1angka. Dalam setiap baris, kolom danwilayah diisi dengan angka 1 (satu) sampaidengan 9 (sembilan) dengan kemungkinanhanya sekali. Setiap angka dalam solusi initerjadi hanya sekali dalam 3 kondisi (baris,kolom dan a pengujian menguji waktu yangdiperlukan program untuk memecahkanpuzzle dengan menggunakan platform yangberbedaTabel 1. Tabel prosessorProsessorBeginnersIntermediatePentium III741ms351ms550MHzCore2 Duo47ms31ms1,6GhzCore2 Duo32ms16ms3,16GHzSoal yang digunakan adalah Beginnersdan Intermediate. Penguji dilakukan dengandengan menggunakanprosessor IntelPentium III 550MHz dengan Core2 Duo1,6GHz dengan clock speed 694ms dan320ms untuk soal pertama dan keduadiketahui perbedaan terbesar ada padatingkat prosessor.Dapat disimpulkan bahwa semakintinggi clock prosessor yang digunakan,semakin cepat waktu yang diperlukan untukmenyelesaikan puzzle. Semua soal dapatdiselesaiakan dengan baik, jawaban sesuaites yang diujikan. Tiap tingkat kesuitandapat diselesaikan tanpa ada masalah.Beginners600400Waktu(ms)0Gambar 4. Grafik Processor level Pemula204400350300250200150100500Waktu(ms)Gambar 5. Grafik Processor lanjutanPengujian KesalahanPada tahap ini penulis akan mengujiprogram dengan memasukan angka yangtidak valid. Dari pengujian tersebut penulismemasukan angka yang sama (angka 7)pada satu baris dan satu kolom yang sama.Gambar 6. Pengujian kesalahanDari hasil proses, program akanmendeteksi kesalahan dengan menandaiangka yang sama. Proses tidak akan berjalankarena tidak boleh ada angka yang samapada satu baris dan satu kolom yang sama.800200IntermediateHasil Akhir PengujianPerbandingan waktu tempuh untukmenyelesaikan puzzle yang diperlukan userbila dibandingkan dengan program dapatdilihat pada Tabel 2. Soal yang digunakanadalah soal beginners level. Dari tabelperbandingan dapat diketahui bahwa
Vol. X No. 2, September 2013program dapat menyelesaikan soal jauhlebih cepat daripada menggunakan cara yangkonvensional.Jurnal Techno Nusa Mandiridiharapkan dapat memperbaiki kromosomyang sudah ada.Individu-individupada generasigenerasi berikutnya diharapkan akanmemiliki nilai fitness yang lebih baik danmengarah pada suatu solusi yangdiharapkan. Solusi yang diambil adalahsolusi pada individu atau kromosom yangpaling besar nilai fitnessnya.Pindah Silang (Crossover)Salahsatu komponen paling pentingdalam algoritma genetika adalah crossoveratau pindah silang. Sebuah kromosom yangmengarah pada solusi yang bagus bisadiperoleh dari proses memindah-silangkandua buah kromosom.Gambar 7. Hasil proses kalkulasiTabel 2. Perbandingan 000Riyan1240000Feri1180000Program47Algoritma Genetika dalam PermainanSudokuPenerapan Algoritma Brute Forcedalam mencari solusi atau penyelesaianpermainan Sudokudidasarkan padapencarian solusi yang paling optimal. Setiapsolusi yang mungkin direpresentaiskandengan sebuah kromosom. Kromosomkromosom terrsebut kemudian diperiksanilai fitnessnya. Kromosom yang nilaifitnessnya paling tinggi atau yang palingoptimal akan dipilih untuk terus hidup ataulajut pada generasi berikutnya danberpeluang melakukan crossover untukmenghasilkan kromosom atau individu baruyang diharapkan mempunyai nilai fitnessyang lebih baik. Dengan adanya mutasiSkema PengkodeanPengkodean suatu kromosom adalahlangkah pertama ketika kita menggunakanalgoritma genetik untuk menyelesaikansuatu masalah. Pengkodean ini biasanyatergantung kepada masalah yang dihadapi.Pengkodean ini meliputi pengkodeanterhadap gen yang terdapat dalamkromosom. Gen dapat dipresentasikan dalambentuk : string bit, pohon, array bilanganreal, daftar aturan, elemen permutasi,elemen program, atau representasi lainnyayang dapat diimplementasikan untukoperator genetikapackage sudoku;public class Sudoku {private int[][] matrix newint[9][9];private int[][] inputMatrix newint[9][9];public void resetMatrix() {matrix new int[9][9];inputMatrix new int[9][9];}private void fill(int x, int y,int value) {while (x 0) {x 9;y--;}while(x 8) {x - 9;y ;}matrix[x][y] value;}205
Jurnal Techno Nusa MandiriVol. X No. 2, September 2013public void set(int x, int y, intvalue) {while (x 0) {x 9;y--;}while(x 8) {x - 9;y ;}inputMatrix[x][y] intx) {if (x 81)return true;if (getValue(x, 0) ! 0 &&getValue(x,0) getValueOriginal(x, 0)) {returnsolve(x 1);}else {for (int i :Backtrack(x, 0)) {if(i! 0) {fill(x, 0, i);{for (int x 0; x ! 9; x )if (!solve(x 1))for (int y 0; y ! 9; y )matrix[x][y]inputMatrix[x][y];}fill(x,0,0); elsereturn true;}}public boolean solve() {copyMatrix();return solve(0);}public int getValue(int x,int y) {while (x 0) {x 9;y--;}while(x 8) {x - 9;y ;}return matrix[x][y];}publicintgetValueOriginal(int x, int y) {while (x 0) {x 9;y--;}while(x 8) {x - 9;y ;}returninputMatrix[x][y];}206}return false;}public booleanvalidNumberOriginal (int x, inty, int number){if (number 1 number 9)return false;while (x 0){x 9; y--;}while(x 8){x - 9; y ;}int[] validNumbers {1,2,3,4,5,6,7,8,9};// cek vertikal, horizontalfor (int i 0; i ! 9; i ){if (inputMatrix[i][y] ! 0)validNumbers[inputMatrix[i][y]-1] 0;if (inputMatrix[x][i] ! 0)validNumbers[inputMatrix[x][i]-1] 0;}// cek kotakint squareX, squareY;
Vol. X No. 2, September 2013if (x 3)squareX 0;else if (x 6)squareX 3;elsesquareX 6;if (y 3)squareY 0;else if (y 6)squareY 3;elsesquareY 6;for (int i 0; i ! 3; i ){for (int j 0; j ! 3; j ){if(inputMatrix[i squareX][j squareY]! 0){validNumbers[inputMatrix[i squareX][j squareY]-1] 0;}}}return (validNumbers[number-1] 0) ? false : true;}private int[] Backtrack (int x,int y){while (x 0){x 9;y--;}while(x 8){x - 9;y ;}Jurnal Techno Nusa MandirisquareX 0;else if (x 6)squareX 3;elsesquareX 6;if (y 3)squareY 0;else if (y 6)squareY 3;elsesquareY 6;for (int i 0; i ! 3; i ){for (int j 0; j ! 3; j ){if(matrix[i squareX][j squareY]! 0){validNumbers[matrix[i squareX][j squareY]-1] 0;}}}return validNumbers;}public void printTable(){System.out.print("\n");for (int x 0; x ! 9; x ){for (int y 0; y ! 9; y ){System.out.print(" " inputMatrix[x][y] " ");if (y 2 y 5)System.out.print(" ");}if (x 2 x 5)System.out.print("\n-------- --------- --------");System.out.print("\n");}}int[] validNumbers {1,2,3,4,5,6,7,8,9};// cek vertikal horizontalfor (int i 0; i ! 9; i ){if (matrix[i][y] ! 0){validNumbers[matrix[i][y]1] 0;}if (matrix[x][i] ! 0){validNumbers[matrix[x][i]-1] 0;}}ElitismeKarena seleksi dilakukan secararandom, maka tidak ada jaminan bahwasuatu individu bernilai fitness tertinggi akanselalu terpilih. Kalaupun individu bernilaifitness tertinggi terpilih, mungkin sajaindividu tersebut akan rusak (nilai fitnessnyamenurun) karena proses pindah silang.Untuk menjaga agar individu bernilai fitnesstertinggi tersebut tidak hilang selamaevolusi, maka perlu dibuat satu ataubeberapa kopinya. Prosedur ini dikenalsebagai elitisme.// cek kotakint squareX, squareY;if (x 3)PENUTUP207
Jurnal Techno Nusa MandiriVol. X No. 2, September 2013Pada pengujian program menggunakansoal Beginners, Intermediate, Advance,Expert, Master didapatkan bahwa waktutempuh program berbeda-beda. Semakintinggi tingkat kesulitan, semakin lama waktuyang diperlukan.Untuk pengujian kedua semua soal yangdiuji dapat diselesaikan dengan tepat olehprogram dengan hasil Algoritma Brute forcedanBacktrackingterbuktidapatmenyelesaikan puzzle sudoku. AlgoritmaBrute force dan Backtracking dapatdigunakan untuk menyelesaikan puzzlesudoku dengan baik. Waktu yang diperlukanuntuk memcahkan puzzle tidak dipengaruhioleh tingkat kesulitan dari puzzle itu sendiri.Waktu untuk memecahkan puzzle lebihdipengaruhi oleh spesifikasi komputer yangdigunakan terutama prosessor. Semakintinggi clock prosessor, semakin cepat waktuyang diperlukan untuk menyelesaikanpuzzle.Proses pengujian program didapatkanhasil 47ms, 31ms, 16ms, 16ms, 31ms untukmasing-masingtingkat(Beginners,Intermediate, Advance, Expert, Master)sedangkanuntukhasilpengujianberdasarkan perbedaan prosessor (PentiumIII 550MHz, Core2 Duo 1,6GHz, Core2 Duo3,16GHz) didapatkan hasil 741ms, 47ms,32ms untuk pengujian pertama dan 351ms,31ms, 16ms.DAFTAR PUSTAKACrook, J.F. 2009. A Pencil-and-PaperAlgorithm for Solving Sudoku Puzzle.Notices of the AMS. Vol: 56, No. 4.Davis, Tom. 2010. The Mathematics ircles.(20 Juni 2011).Gurari, Eitan, 1999. Data StructuresChapter: General Algorithms & StateSearch Algorithms. www.cse.ohiostate.edu/ gurari/course/cis680/cis680No1.html##QQ1-29-103. (24 Juni2011).Jussien, Narendra. 2007. A-Z Sudoku. ISTELtd.Kadir, Abdul. 2007. Dasar PemrogramanJava 2. Yogyakarta: ANDI OFFSET.208Mepham, Michael. 2005. Solving Sudoku.Crosswords Ltd.Omimura, Satsuko. 2009. Sudoku The BlackHat. Jakarta: Prestasi Pustaka.Hendra. Meraih gelar Sarjana Komputerdari STMIK Indonesia pada tahun 1998.Pada tahun 2010 mendapatkan gelarMagister Komputer dari STMIK NusaMandiri. Aktif dalam berbagai kegiatanpenelitian dan seminar ilmiah. Menjadianggota Asosiasi Dosen Indonesia (ADI)dan Asosiasi Perguruan Tinggi IlmuKomputer (APTIKOM).
Sebuah soal sodoku terdiri dari 9 kolom, atau 3 blok. Memulainya dapat dilakukan dari mana saja, tergantung struktur soal. Gambar 1. Sudoku dengan kotak 9 x 9 Varian-varian Sudoku Sejak Sudoku dipopulerkan banyak variasi puzzle Sudoku, beberapa variasinya berkaitan dengan ukuran grid, objek isian, warna, dan ukuran dimensi.
