PENGEMBANGAN GAME SUDOKU MENGGUNAKAN ALGORITMA GENETIKA
TUGAS AKHIR Diajukan Untuk Memenuhi Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : NURHADI SANTOSO NIM : 07560198
JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG 2013
i
LEMBAR PERSETUJUAN Pengembangan Game Sudoku Mengunakan Algoritma Genetika
TUGAS AKHIR
Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Mengetahui/ menyetujui,
Pembimbing I
Pembimbing II
Dr. Ir. Ermanu Azizul Hakim, MT
Ali Sofyan Kholimi, S.Kom
NIP. 108.9109.0233
NIDN. 0701038202
ii
LEMBAR PENGESAHAN Pengembangan Game Sudoku Mengunakan Algoritma Genetika
TUGAS AKHIR Sebagai Persyaratan Guna Meraih Gelar Sarjana Strata 1 Teknik Informatika Universitas Muhammadiyah Malang
Disusun Oleh : Nurhadi Santoso NIM : 07560198
Tugas Akhir ini telah diuji dan dinyatakan lulus melalui sidang majelis penguji pada tanggal 10 Januari 2014. Menyetujui, Penguji I
Penguji II
Eko Budi Cahyono, S.Kom, MT NIP. 108.9504.0330
Ilyas Nuryasin, S.Kom, M.Kom. NIDN. 0723118601
Mengetahui, Ketua Jurusan Teknik Informatika
Eko Budi Cahyono, S.Kom, MT NIP 108.9504.0330
iii
LEMBAR PERNYATAAN
Yang bertanda tangan di bawah ini : NAMA
: Nurhadi Santoso
NIM
: 07560198
FAK/JUR
: Teknik / Teknik Informatika
Dengan ini saya menyatakan Bahwa Tugas Akhir dengan judul “Pengembangan Game Sudoku Menggunakan Algoritma Genetika” beserta seluruh isinya adalah karya saya sendiri dan bukan merupakan karya tulis orang lain, baik sebagian maupun seluruhnya, kecuali dalam bentuk kutipan yang telah disebutkan sumbernya. Demikian surat pernyataan ini saya buat dengan sebenar-benarnya. Apabila kemudian hari dtemukan adanya pelanggaran terhadap etika keilmuan dalam karya saya ini, atau ada klaim dari pihak lain terhadap keaslian karya saya ini maka saya siap menanggung segala bentuk resiko atau sanksi yang berlaku.
Mengetahui,
Malang, 3 Januari 2014
Dosen Pembimbing
Yang Membuat Pernyataan
Dr. Ir. Ermanu Azizul Hakim, MT
Nurhadi Santoso
iv
ABSTRAKSI
Perkembangan ilmu pengetahuan dan teknologi telah menghantarkan manusia ke zaman yang serba modern seperti sekarang ini. penggunaan internet, mobile phone, dan teknologi digital lainnya tidak dapat dihindari lagi. bentuk yang paling ,udah untuk diukur tingkat keberhasilan dan cukup digemari oleh sebagian besar orang yaitu pada permainan. Sudoku terdiri dari berbagai macam tingkat kesulitan. Semakin sulit soal, tentu akan semakin lama waktu yang dibutuhkan system untuk memecahkan soal tersebut. Adakalanya dalam mengerjakan kita mengalami jalan buntu, untuk itu penulis membuat aplikasi yang dapat menemukan solusi dengan soal yang acak namun tetap terikat pada peraturan dasar sudoku dengan menggunakan metode algoritma genetika.
Kata Kunci : Permainan, Algoritma Genetika
v
ABSTRACT
Developments in science and technology have exposed humans to the modern all times as it is today. use of the internet, mobile phones, and other digital technologies can not be avoided anymore. most forms, to measure the level of success already and quite favored by the majority of people are in the game. Sudoku consists of various levels of difficulty. The more difficult question, of course the longer the time it takes the system to solve the problem. Sometimes in our work stalled, for the authors to make an application that can find a solution to the problem is random but remains bound to the basic sudoku rules using genetic algorithm.
Keyword : Game, Genetic Algorithm
vi
LEMBAR PERSEMBAHAN Dengan mengucap puji syukur kehadirat Allah SWT atas segala rahmat serta hidayahnya sehingga laporan tugas akhir dengan judul : “Pengembangan Game Sudoku Menggunakan Algoritma Genetika” dapat penulis selesaikan. Tugas Akhir ini merupakan salah satu prasyarat untuk menyelesaikan studi tingkat strata satu di Fakultas Teknik Jurusan Informatika Universitas Muhammadiyah Malang. Selama penyelesaian tugas akhir ini, penulis telah memperoleh banyak bantuan, bimbingan, motivasi dan saran yang berguna dari berbagai pihak. Oleh
karena itu, pada kesempatan
ini
penulis ingin
mengucapkan rasa terima kasih kepada : 1.
Bapak Dr. Ir. Ermanu Azizul Hakim, MT. selaku Dosen Pembimbing I, yang telah meluangkan waktu untuk memberikan bimbingan maupun pengarahan dalam penyelesaian tugas akhir ini.
2.
Bapak Ali Sofyan Kholimi, S.Kom. selaku Dosen Pembimbing II, yang telah meluangkan waktu dalam memberikan bimbingan maupun pengarahan dalam pencapaian hasil yang maksimal pada penelitian tugas akhir ini.
3.
Seluruh Dosen Jurusan Teknik Informatika.
4.
Kepada Ibundaku tercinta, Ibu Siti Nurhayati yang selalu memberikan doa dan dukungan yang tak ternilai harganya dan juga kepada Ayahandaku tersayang, Bapak Santoso Prayitno yang selalu menjadi motivasi bagi saya.
5.
Saudara-saudaraku, Ayu, Toton, Upik yang selalu menjadi penyemangat.
6.
Keluarga Besar Biro Administrasi Akademik yang selalu memberikan nasehat dan dorongan motivasi sehingga terselesaikannya tugas akhir ini.
7.
Bapak H. Mu'ali dan Ibu Hj. Siti Safa'atin serta Bunda Selly, Alvaro, Alvariz, Devi, dan Arga yang selalu memberikan doa dan dorongan motivasi sehingga terselesaikannya tugas akhir ini.
8.
Keluarga Besar Ibu Sundari yang telah memberikan segala nasehat dan motivasi sehingga terselesaikan tugas akhir ini.
9.
Keluarga Besar PAB dan GCK yang selalu memberikan dukungan dan motivasi demi terselesaikannya tugas akhir ini.
vii
10. Teman-teman terbaikku: Ayu, Dimas, Yufi, Lily, Freddy, Lina dkk yang telah memberi dukungan dan dorongan semangat sehingga terselesaikannya tugas akhir ini. 11. Teman-teman angkatan 2007 yang tidak dapat penulis sebutkan satu persatu.
Saya juga menyadari dengan karya sederhana ini tentu masih jauh dari kesempurnaan. Oleh karena itu, saran dan kritik yang membangun dari berbagai pihak tentu diperlukan agar skripsi ini menjadi lebih baik. Akhir kata semoga skripsi ini bisa bermanfaat bagi yang membaca.
Malang, 3 Januari 2014
Penulis
viii
KATA PENGANTAR Dengan memanjatkan puji syukur kehadirat ALLAH SWT atas dilimpahkan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan Tugas Akhir yang berjudul :
"Pengembangan Game Sudoku Menggunakan Algoritma Genetika” Di dalam tulisan ini disajikan pokok-pokok bahasan yang meliputi : Game Sudoku, Algoritma Genetika
Penulis menyadari sepenuhnya bahwa dalam penulisan Tugas Akhir ini masih banyak kekurangan dan keterbatasan. Oleh karena itu penulis mengharapkan saran yang membangun agar tulisan ini bermanfaat bagi perkembangan ilmu pengetahuan kedepan. Amin.
Malang, 3 Januari 2014
Penulis
ix
DAFTAR ISI HALAMAN HALAMAN JUDUL ................................................................................... i LEMBAR PERSETUJUAN ....................................................................... ii LEMBAR PENGESAHAN ........................................................................ iii LEMBAR PERNYATAAN ........................................................................ iv ABSTRAKSI................................................................................................ v ABSTRACT ................................................................................................. vi LEMBAR PERSEMBAHAN ..................................................................... vii KATA PENGANTAR ................................................................................. ix DAFTAR ISI ................................................................................................ x DAFTAR GAMBAR ................................................................................... xiii DAFTAR TABEL ....................................................................................... xiv
BAB 1 PENDAHULUAN 1.1 Latar belakang ......................................................................................... 1 1.2 Rumusan masalah.................................................................................... 2 1.3 Tujuan penelitian ..................................................................................... 2 1.4 Batasan masalah ...................................................................................... 2 1.5 Metodologi penelitian ............................................................................. 2 1.6 Sistematika Penulisan ............................................................................. 3
BAB II LANDASAN TEORI 2.1 Sejarah Sudoku ....................................................................................... 5 2.1.1 Cara Bermain .............................................................................. 6 2.1.2 Jenis Sudoku ............................................................................... 7
x
2.2 Algoritma Genetika ................................................................................. 8 2.2.1 Definisi Dalam Algoritma Genetika ........................................... 10 2.2.2 Tahapan Dalam Menggunakan Algoritma Genetika .................. 10 2.2.3 Struktur Algoritma Genetika ....................................................... 11
BAB III ANALISA DAN PERANCANAAN SISTEM 3.1 Analisa dan Gambaran Umum ................................................................ 13 3.2 Kebutuhan Input ...................................................................................... 14 3.2.1 Functional Requirement .............................................................. 14 3.2.2 Non Functional Requirement ...................................................... 14 3.3 Perancangan Sistem ................................................................................ 14 3.3.1 Flowchart Diagram ..................................................................... 14 3.3.2 Use Case Diagram ....................................................................... 16 3.3.3 Activity Diagram ........................................................................ 17 3.3.4 Sequence Diagram ...................................................................... 19 3.3.5 Class Diagram ............................................................................. 22 3.4 Desain Antar Muka ................................................................................. 26 3.4.1 Tampilan Antarmuka Aplikasi .................................................... 26 3.5 Pembangkitan Puzzle .............................................................................. 27 3.6 Representasi Kromosom ......................................................................... 38 3.7 Fungsi Fitness ......................................................................................... 28
BAB IV IMPLEMENTASI DAN PENGUJIAN 4.1 Analisa dan Gambaran Umum ................................................................ 31 4.1.1 Tampilan Aplikasi ....................................................................... 31 4.1.2 Implementasi Fungsi Umum Aplikasi ........................................ 33
xi
4.1.3 Implementasi Algoritma Genetika pada Sudoku ........................ 33 4.2 Pengujian Umum .................................................................................... 38 4.2.1 Pengujian Perangkat Lunak ........................................................ 38 4.2.2 Pengujian Permainan Sudoku ..................................................... 40
BAB V KESIMPULAN DAN SARAN 5.1 Kesimpulan ............................................................................................. 42 5.2 Saran ........................................................................................................ 42
DAFTAR PUSTAKA .................................................................................. 43
xii
DAFTAR GAMBAR HALAMAN Gambar 2.1 Sudoku yang sudah diselesaikan ............................................... 7 Gambar 3.1 Flowchart Algoritma Genetika Pada Sudoku ............................ 15 Gambar 3.2 Use Case Diagram ..................................................................... 16 Gambar 3.3 Activity Diagram Input Sudoku ................................................ 17 Gambar 3.3 Activity Diagram Proses Sudoku .............................................. 18 Gambar 3.4 Activity Diagram Output Sudoku ............................................. 19 Gambar 3.5 Sequence diagram input pilihan sudoku ................................... 20 Gambar 3.6 Sequence diagram proses .......................................................... 21 Gambar 3.7 Sequence diagram output .......................................................... 21 Gambar 3.8 Class Diagram ........................................................................... 22 Gambar 3.9 Gambar antar muka aplikasi ...................................................... 26 Gambar 3.10 Puzzle Sudoku Valid ............................................................... 28 Gambar 4.1 Tampilan awal Sudoku solver ................................................... 33 Gambar 4.2 Tampilan menu Sudoku solver .................................................. 34 Gambar 4.3 Implementasi Fungsi ................................................................. 35 Gambar 4.4 Implementasi Fungsi Algoritma ................................................ 36 Gambar 4.5 Implementasi Fungsi Chromosome ........................................... 36 Gambar 4.6 Implementasi Fungsi Fitness ..................................................... 37 Gambar 4.7 Implementasi Fungsi Variable .................................................. 37
xiii
DAFTAR TABEL HALAMAN Tabel 4.1 Pengujian Fungsi Perangkat Lunak............................................... 38 Tabel 4.2 Penguian Permainan Sudoku ........................................................ 40
xiv
DAFTAR PUSTAKA
Hakim, R., & Sutarto. (2009). Mastering Java. Jakarta Pusat: Elex Media Komputindo. Harnaningrum, L. N. (2009). Algortima dan Pemrograman Java. Yogyakarta: Graha Ilmu. Kadir, A. (2008). Dasar Pemrograman Java 2. Yogyakarta: Andi. Komputer, W. (2009). Menguasai Java Programming. Jakarta Selatan: Salemba Infotek. Lewis, R. (2012). Metaheuristics Can Solve Sudoku Puzzle. inf.utfsm.cl. Retrieved December 06, 2013, from inf.utfsm.cl/~mcriff/Tesistas/Games/ Mantere, T., & Koljonen, J. (2006). Solving and Rating Sudoku Puzzles with Genetic Algorithms. New Developments in Artificial Intelligence and the Semantic Web Proceedings of the 12th Finnish Artificial Intelligence Conference STeP 2006, 86–92. Melanie, M. (1995). Genetic algorithms: An overview. Complexity, 1(1), 31–39. doi:10.1002/cplx.6130010108 Melanie, M. (1996). An Introduction to Genetic Algorithms. MIT Press. Purnomo, H., & Kusumadewi, S. (n.d.). Aplikasi Algoritma Genetika Untuk Penentuan Tata Letak Mesin, 203–211. Siswanto. (2011). Algoritma dan Struktur Data Non Linear dengan Java. (L. N. Harnaningrum, Ed.). Yogyakarta: Graha Ilmu. Weiss, J. M. (2009). Genetic Algorithms and Sudoku. MICS. Whitley, D. (1994). A Genetic Algorithm Tutorial. Statistics and Computing, 4(2), 65–85. doi:10.1007/BF00175354
xv
