PENETAPAN ALGORITMA BACKTRAKING PADA PERMAINAN SUDOKU

ISSN 2089 – 628X

PROSESOR Vol. IV Edisi 08 / Desember 2013

PENETAPAN ALGORITMA BACKTRAKING PADA PERMAINAN SUDOKU Dicky Apdillah Staff Pengajar AMIK INTeL Com GLOBAL INDO

ABSTRAK Algoritma Runut Balik (Backtracking) merupakan salah satu algoritma pencarian yang sering digunakan dalam beberapa penyelesaian masalah dan untuk memberikan kecerdasan buatan dalam permainan. Algoritma ini akan mencari solusi berdasarkan ruang yang mengarah kepada solusi yang akan diproses. Penulis merasa tertarik untuk menerapkan algoritma runut balik ini sebagai kecerdasan buatan dalam permainan Sudoku. Oleh karena itu, dalam penelitian ini akan dibahas mengenai” Penetapan Algoritma Backtracking Pada Permainan Sudoku”. Game adalah suatu system yang memiliki aturan dengan suatu varibel dan hasil yang dapat dihitung, dimana hasil yang berbeda ditugaskan dengan nilai-nilai yang berbeda, dimana pemain melakukan usaha dalam mempengaruhi hasil perhitungan tersebut. Sudoku adalah permainan dengan menggunakan angka yang sederhana namun membutuhkan ketelitian yang tinggi dan pemikiran yang matang dalam penyelesaiannya. Permainan ini dapat dimainkan oleh semua kalangan masyarakat karena sangat sederhana, tak membutuhkan banyak biaya dan dapat dimainkan oleh tua atau maupun muda. Sudoku melatih kemampuan berfikir dan kemampuan analis pemain.Hal-hal ini lah yang menjadi pertimbangan mengapa kemudian saya menjadikan permainan Sudoku ini menjadii objek perancangan. Kata Kunci :Algoritma, Game, Sudoku

I.

PENDAHULUAN

Ada berbagai macam permainan teka teki, salah satunya adalah Sudoku yang berasal dari Jepang. Dalam menyelesaikan permainan ini, pemain dituntut untuk berpikir dengan logika. Secara umum, Sudoku merupakan permainan dalam bentuk tabel yang berukuran 9x9. Dalam Sudoku yang berukuran 9x9 terdapat Sembilan kelompok/blok yang berukuran 3x3. Tujuan permainan ini adalah untuk mengisi setiap sel tabel yang masih kosong dengan angka-angka, sedemikian dan tidak ada angka yang berulang dalam baris maupun kolom. Terdapat beberapa algoritma dalam penyelesaian permainan Sudoku.Pada kesempatan ini algoritma yang digunakan adalah Algoritma Backtracking (runut balik). Permain Sudoku adalah salah satu permasalahan paling banyak digemari saat ini, dan juga merupakan salah satu permasalahan paling sulit dibidang informatika. Permasalahan Sudoku sulit untuk dipecahkan karena masuk dalam permasalahan NP-Complete, sehingga tidak bisa diselesaikan dalam waktu yang sama. Hingga saat ini banyak programmer yang mencari algoritma yang tepat untuk menyelesaikannya. Pada tahun 1950-an Jhon McCarthy dari Mussachusets Institute of Technology (IMIT) menciptakan bahasa pemograman LISP. Kemudian berkembang dengan dibuatnya program komputer yang “berpikir seperti permainan catur dan pembuktian perhitungan matematis secara komputasi.Hal ini membuktikan bahwa aplikasi

kecerdasan buatan digunakan dalam memecahkan permasalahan permainan dan mmemecahkan tekateki.Para peneliti merasa bahwa kemampuan komputer untuk menjalankan permainan merupakan demonstrasi luar biasa tentang intelegensia manusia, tentu dalam hal yang terkendali dan terbatas. Backgammon, tic tac toe, dan lainnya ditulis, dicoba dan diperbaiki serta terus di perkembangkan dengan menggunakan teknik kecerdasan buatan. Program kecerdasan buatan juga ditulis untuk memecahkan teka-teki dan pertanyaan teka-teki.Sampai sekarang, permainan selalu digunakan sebagai contoh dalam mengajar kecerdasan buatan. Algoritma Runut Balik (Backtracking) merupakan salah satu algoritma pencarian yang sering digunakan dalam beberapa penyelesaian masalah dan untuk memberikan kecerdasan buatan dalam permainan. Algoritma ini akan mencari solusi berdasarkan ruang yang mengarah kepada solusi yang akan diproses. Penulis merasa tertarik untuk menerapkan algoritma runut balik ini sebagai kecerdasan buatan dalam permainan Sudoku. Oleh karena itu, dalam penelitian ini akan dibahas mengenai” Penetapan Algoritma Backtracking Pada Permainan Sudoku”. II.

LANDASAN TEORI

2.1. Pengertian Game Game adalah suatu system yang memiliki aturan dengan suatu varibel dan hasil yang dapat dihitung,

AMIK INTeL Com GLOBAL INDO -

51

ISSN 2089 – 628X


dimana hasil yang berbeda ditugaskan dengan nilainilai yang berbeda, dimana pemain melakukan usaha dalam mempengaruhi hasil perhitungan tersebut. Game secara umum dibagi menjadi lima bagian diantaranya: 1. Arcade/Action, game yang memiliki interaksi dengan manusia yang tinggi dan menggunakan graphis yang beragam, seperti: game Quake dan Freelancer. 2. Puzzle, game yang didalamnya terdapat unsure logika, seperti: game Tetris. 3. Card, game seperti Poker dan Black Jack. 4. Strategy, game yang memiliki suatu teknik dan pemikiran serta manajemen didalamnya seperti: game Command and Conquer dan Warcraft. 5. Sport, game seperti permainan olah raga yang sesungguhnya seperti game Fifa 2000. Dalam game terdapat banyak unsure grafik computer. Grafik computer adalah seperangkat alat yang terdiri dari hardware dan software untuk membuat gambar, grafik atau citra realistic untuk seni, game computer, foto dan film animal. Grafik tiga dimensi dapat menggambarkan sebuah benda dalam dunia nyata menjadi sebuah objek dari berbagai sudut pandang. Tidak seperti dua dimensi, grafik tiga dimensi banyak sekali hal yang harus dipertimbangkan. 2.2. Komponen Pendukung Sistem Komponen pendukung sistem merupakan panduan untuk melaksanakan dan menyelesaikan suatu studi. Dalam hal ini akan mengemukakan beberapa teori yang berkaitan dengan penyelesaian permasalahan. 2.2.1. Konsep Dasar Bahasa Pemograman Bahasa pemograman sering diistilahkan juga dengan bahasa komputer, adalah teknik komando atau set intruksi standar untuk memerintah komputer. Bahasa pemograman ini merupakan suatu set aturan sintaks dan semantik yang dipakai untuk mendefenisikan program komputer. Maka disini akan dijelaskan bahasa pemograman apa saja yang digunakan dalam penyelesaian penelitian ini. 2.2.2. Editor Microsoft Visual Basic Visual Basic adalah salah satu development tools untuk membangun aplikasi dalam lingkungan Windows. Dalam pengembangan aplikasi, Visual basic menggunakan pendekatan Visual untuk merancang user interface dalam bentuk form, sedangkan untuk kodingnya menggunakan dialek bahasa Basic yang cenderung mudah diperlajari. Visual Basic telah menjadi tools yang terkenal bagi para pemula maupun para developer. Dalam lingkungan Window’s User-interface sangat

memegang peran penting, karena dalam pemakaian aplikasi yang kita buat, pemakai senantiasa berineraksi dengan User-interface tanpa menyadari bahwa dibelakangnya berjalan instruksi-instruksi program yang mendukung tampilan dan proses yang dilakukan. Pada pemrograman Visual, pengembangan aplikasi dimulai dengan proses yang dimulai dengan pembentukan user interface, kemudian mengatur property dari objek-objek yang digunakan dalam user interface, dan baru dilakukan penulisan kode program untuk menangani kejadiankejadian (event). Tahap pengembangan aplikasi dengan istilah pengembangan aplikasi dengan pendekatan Bottom Up. Langkah awal dari belajar Visual Basic adalah mengenal IDE (intergrated Development Environment) Visual Basic yang merupakan lingkungan perngembangan terpadu bagi programmer dalam mengembangkan aplikasi.Dengan menggunakan IDE programmer dapat membuat user interface, melakukan koding, melakukan testing dan debugging serta menkompilasi program menjadiexecutable. Penguasaan yang baik akan IDE akan sangat membantu programmer dalam mengefektifkan tugas-tugasnya sehingga dapat berkerja dengan efesien. 2.2.3. Mengenal Struktur Kendali Struktur kendali memungkinkan anda untuk mengatur jalanya program anda, jika membiarkan tanpa di periksa oleh statement control-flow, suatu logika program akan berjalan dari kiri ke kanan dan dari atas ke bawah. Hanya program yang sangar sederhana dapat ditulis tanpa statement controlflow. Anda dapat meletakan suatu struktur kendali didalam struktur kendali lainnya, yang dikenal dengan istilah nested. Strukur kendali pada Visual Basic dapat nested sebanyak level yang anda inginkan. 2.2.4. Struktur Keputusan Struktur keputusan yang didukung oleh Visual Basic sebagai berikut : 1) If….Then Gunakan suatu struktur If..Then untuk menjalankan suatu pernyataan secara kodisional. Anda dapat menggunakan syntax satu baris maupun syntax banyak baris : If kondisi Then pernyataan Atau If kondisi Then Pernyataan-pernyataan End If Kondisi biasanya berupa suatu perbandingan, maupun ekspresi yang menghasilkan nilai


52

ISSN 2089 – 628X


numeric. Visual Basic menginterprestasikan False sebagai nol (0), dan True sebagai bukan nol. 2) If…Then…Else Gunakan If…Then…Else untuk mendefenisikan beberapa blok pernyataan yang akan dijalankan salah satu berdasarkan kondisi yang memenuhi syarat If kondisi1 Then [blok pernyataan-1] [ElseIf kondisi2 Then [blok pernyataan-2]]… [Else [blok pernyataan-n ]] End If Visual Basic awalnya akan mencoba kondisi1. Jika False, maka Visual Basic akan memeriksa kondisi2, dan seterusnya sampai menemukan suaatu kondisi True untuk dijalankan blok Pernyataannya. Contoh :

Masalah yang akan diangkat adalah bagaimana kita dapat menghasilkan solusi yang tepat, dan benar untuk mengatasi permasalahan yang timbul dalam permainan Sudoku. 3.2. Solusi Permasalahan Berikut ini adalah metode yang dapat digunakan dalam mencari solusi permasalahan Sudoku: 1) Genetic Algorithma(Algoritma Genetika) Algoritma Genetika Merupakan salah satu metode yang popular dan terus berkembang sekang ini.Algoritma genetika bekerja pada populasi solusi, maka algoritma genetika dapat menelusuri ruang pencarian solusi dalam berbagai arah sekaligus. Jika satu solusi tidak terlalu baik, maka ada harapan bahwa solusi yang lain merupakan solusi yang lebih baik. Solusi-solusi yang sudah baik ini nantinya mempunyai memungkinkan dikombinasikan (crossover) untuk menghasilkan solusi yang lebih baik lagi. Dan atua dengan mutasi, perubahan elemen pada solusi akan membuka kemungkinan baru, sehingga algoritma genetika lebih kecil kemungkinannya untuk terjebak pada local optima. 2) Constraint Satisfaction (Pemenuhan Kostrain)

If JlhRec >0 Then

Metode yang bekerja dengan menentukan batasan dari suatu permasalahan, untuk mencari solusi yang sesuai dan paling memuaskan tanpa melanggar batas atau peraturan yang telah ditetapkan. Pemenuhan konstrain ini nantinya akan digunakan dalam mengecek jawaban apakah telah sesuai dengan batasan-batasan yang ada.

Posisi = 1 Else Posisi = 0 End If III. PERANCANGAN SISTEM

3.3. Deskripsi Umum Algoritma Backtracking (Runut Balik)

3.1. Deskripsi Game Sudoku adalah permainan dengan menggunakan angka yang sederhana namun membutuhkan ketelitian yang tinggi dan pemikiran yang matang dalam penyelesaiannya.Permainan ini dapat dimainkan oleh semua kalangan masyarakat karena sangat sederhana, tak membutuhkan banyak biaya dan dapat dimainkan oleh tua atau maupun muda.Sudoku melatih kemampuan berfikir dan kemampuan analis pemain.Hal-hal ini lah yang menjadi pertimbangan mengapa kemudian saya menjadikan permainan Sudoku ini menjadii objek perancangan. Saat ini sudah banyak apilkasi-aplikasi permainan Sudoku yang menggunakan berbagai metode kecerdasan buatan dalam pencarian solusi.Disini saya juga menawarkan aplikasi Sudoku yang dapat memberikan bantuan kepada pemain untuk mengkoreksi apakah jawaban yang dikerjakan oleh pengguna aplikai ini telah memenuhi peraturanperaturan yang ada dalam Sudoku tersebut.

Algoritma backtracking (runut balik) adalah algoritma yang berbasis pada DFS untuk mencari solusi permasalahan secara lebih mangkus. Runut balik merupakn perbaikan dari algoritma brutuforce yang secara sistematis akan melakukan pencarian solusi permasalahan diantara semua kemungkinan solusi yang ada. Dengan metode ini kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang akan dipertimbangkan. Akibatnyan, waktu pencarian dapat dihemat.Runut balik lebih alami dinyatakan dalam algoritma rekursif.Kadang-kadang disebutkan pula bahwa runut balik merupakan bentuk tipikal dari algoritma rekursif. Untuk memfasilitasi pencarian ini, maka ruang solusi diorganisasikan kedalam struktur pohon.Tiap simpul pohon menyatakan status (state) persoalan.Sedangkan sisi (cabang) dilabeli dengan nilai x. lintasan dari akar ke daun menyatakan


53

ISSN 2089 – 628X


solusi yang mungkin.Seluruh lintasan dari akar ke daun membentuk ruang solusi. Algoritma Backtracking membentuk sebuah pohon ruang status selam prosesnyan.Struktuk pohon ini lah, yang juga merupakan sebuah graf tak berarah, yang ditraversal dengan prinsip DFS (Depth First Search). Simpul-simpul pada pohon ruang status yang tidak mengarah ke solusi maka akan “dimatikan”. Sedangkan simpul-simpul pohon ruang status yang masih mengarah ke solusi maka akan terus berkembang. Pematian simpul pohon ruang status yang tidak mengarah kepada solusi ini sering disebut dengan istilah pruning. Dengan demikian, seluruh lintasan dari akar ke daun yang melalui simpul-simpul tida “dimatikan” akan membentuk sebuah ruang solusi. Code secara keseluruhan adalah sebagai berikut: Dim ss As Integer Dim mm As Integer Sub cekkolom1() Dim i As Integer, j As Integer, angka As Integer 'cek ke kanan baris 1 For i = 0 To 8 For j = i + 1 To 8 angka = Val(box(i).Text) 'jika ada yg dobel If angka = Val(box(j).Text) Or box(j).Text = "" Then ket(0).Picture = salah.Picture Exit Sub Else ket(0).Picture = benar.Picture End If Next j Next i '-----------------------End Sub

IV. HASIL

4.1.2. Kebutuhan perangkat lunak Perangkat lunak sofware merupakan yang paling penting dalam aplikasi game Sudoku yang dirancang menggunakan sebagai berikut: a. Sistem operasi Windows 7 . b. Microsof office 2007 c. Aplikasi dibuat dan dikembangkan dengan menggunakan bahasa pemograman Visual Basic 6.0 d. Sofware pendukung lain. 4.2. Implementasi Program Dalam menjalankan program pertama yang akan ditemukan adalah menu utama, yang didalamnya terdapat beberapa file untuk mengetahui informasi yang ada. Berikut adalah tampilan gambar dari program yang dirancang. 4.2.1. Tampilan Form menu utama Gambar form menu utama yang terdapat pada gambar 4.1 dibawah ini menerangkan mengenai entity-entity apa saja yang terdapat dalam program menu utama. Dapat dilihat sebagai berikut.

Gambar 4.1. implementasi gambar utama 4.2.2. Tampilan Form Memilih Level Pada form ini merupakan suatu aplikasi game sudoku yang tampil sesuai dengan level yang ditentukan oleh user.

4.1. Cara Kerja Sistem Dalam bab ini akan dibahas mengenai implementasi sistem yang telah dibuat, dan akan menerangkan komponen sofware, hardware, dan brainware yang dibutuhkan untuk menjalankan sistem informasi yang dirancang ini 4.1.1. Kebutuhan Perangkat keras Perangkat keras hadware yang digunakan adalah sebagai berikut: a. b. c. d.

Processor Pentium IV 1.80 Ghz Monitor 17 Keyboard dan mouse Printer Canon MP 1980 series printer

Gambar 4.2. Tampilan Form Memilih level 4.2.3. Tampilan form Level Mudah Form ini menampilkan soal form level mudah yang nantinya akan diselesaiakn oleh user dalam mempermainkan permainan Sudoku.


54

ISSN 2089 – 628X


Gambar 4.3. Tampilan form level mudah

Gambar 4.8. Tampilan form Jawaban pada level sulit

V.

KESIMPULAN

Dari keseluruhan uraian dan penjelasan pada penulisan penelitian ini maka kesimpulan yang dapat diambil adalah sebagai berikut: Gambar 4.4. Tampilan Form Level Sedang

a. Game sudoku dirancang agar user dapat mengarahkan kemampuannya dalam bermain game yang bisa memberikan tantangan berdasarkan kemampuan user. b. Level dirancang menggunakan aplikasi game Sudoku dengan tingkat kesulitan untuk menyesuaikan kemampuan user.

Gambar 4.5. Tampilan form Level Sulit

c. Game Sudoku mengasah otak dan juga mengandung unsur pendidikan dan dapat meningkatan kecerdasan dalam berlogika.

4.2.4. Tampilan Form Jawaban Pada Level Form ini menampilkan jawaban pada level-level yang telah dimainkan oleh user yang akan nampak pada gambar bberikut ini.

DAFTAR PUSTAKA Hadi Rahadian (2004), Visual basic, Program Studi Teknik Informatika,. Hans Daeng (2009). “Sudoku Solver Manual Version 1.6.0.”. Dalam http://www.dader.net/. Lee, Wei meng. 2006. Program Sudoku. New York: springer-Varlag New York, Inc.

Gambar 4.6. Tampilan form Jawaban pada level mudah

Mujaddi , Sibghatullah. 2009. “Penerapan algoritma runut-balik (Backtracking) Dalam permainan Sudoku”. Dalam http://informatika .stei.itb.ac.id/rinaldi.munir/stmik/. Morenvino M, Ray AI, Anton R S, (2006)..”Combination of BFS and Brute Force Algoritma implementation in Futoshiki Puzzel game”. Dalam http://informatika.stei.itb.ac.id/rinaldi.munir/stmik/. http://id.wikipedia.org

Gambar 4.7. Tampilan Form Jawaban pada level Sedang

Munawar, 2009.Permodelan Visual dengan UML, Edisi 1, Yogyakarta : Graha.


55

ISSN 2089 – 628X



56

PENETAPAN ALGORITMA BACKTRAKING PADA PERMAINAN SUDOKU

Recommend Documents