Analisis Penyelesaian Puzzle Sudoku Dengan Menerapkan Algoritma Backtracking

ANALISIS PENYELESAIAN PUZZLE SUDOKU DENGAN MENERAPKAN ALGORITMA BACKTRACKING MEMANFAATKAN BAHASA PEMROGRAMAN VISUAL BASIC 6.0 DAN DATABASE MICROSOFT ACCESS 2003

MAKALAH PRA SEMINAR TUGAS AKHIR

OLEH : RINA DEWI INDAH SARI NIM : 03201045

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER STMIK “ASIA” MALANG JURUSAN TEKNIK INFORMATIKA 13 SEPTEMBER 2007

BERMAIN GAME SUDOKU

1.

Latar Belakang Permainan Sudoku adalah salah satu puzzle yang paling banyak digemari saat ini, dan

juga merupakan salah satu permasalahan paling sulit di bidang informatika. Permasalahan puzzle 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 menyelesaikan puzzle ini. Cara yang paling gampang adalah algoritma Brute Force yaitu dengan cara mengenumerasikan semua kemungkinan isi sel dengan angka 1 sampai 9. Untuk memecahkan teka-teki Sudoku, dapat digunakan algoritma backtracking (runutbalik). Algoritma ini merupakan perbaikan dari algoritma Brute Force, dimana solusi dapat ditemukan dengan penelusuran yang lebih sedikit dan dapat mencari solusi permasalahan secara lebih mangkus karena tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang perlu dipertimbangkan. Algoritma Backtracking ini mudah diimplementasikan dengan bahasa pemrograman yang mendukung pemanggilan fungsi/ prosedur rekursif. Salah satu bahasa pemrograman yang mendukung pemanggilan fungsi adalah Visual Basic 6.0.

2.

Rumusan Masalah Bagaimana menyelesaikan permainan puzzle Sudoku dengan menerapkan algoritma backtracking memanfaatkan bahasa pemrograman Visual Basic 6.0 dan Database Microsoft Access 2003 ?.

3.

Batasan Masalah

1. Analisis penyelesaian dilakukan untuk game puzzle Sudoku. 2. Metode yang diterapkan adalah dengan algoritma backtracking. 3. Bahasa pemrograman yang digunakan adalah Visual Basic 6.0.

4. Database yang digunakan Microsoft Access 2003. 4.

Tujuan dan Manfaat Penulisan Tujuan 1.

Menyelesaikan penyusunan Laporan Tugas Akhir (TA) pada program

pendidikan S-1 di Perguruan Tinggi Asia Malang.

2.

Mempopulerkan permainan puzzle Sudoku di kalangan mahasiswa

untuk dapat melatih logika manusia dalam berpikir cepat dan teliti.

3.

Membantu para penggemar permainan Sudoku dalam mencari cara

penyelesaian permainan yang lebih cepat dan tepat.

1

Manfaat Bagi penulis 1. Mengaplikasikan disiplin ilmu yang telah diperoleh selama belajar di Perguruan Tinggi Asia Malang Jurusan Teknik Informatika.

2. Belajar menganalisa permasalahan dengan solusi secara ilmiah yaitu dengan memanfaatkan algoritma backtracking. 3. Dapat mengasah otak dalam berfikir secara cepat dan teliti untuk mencari penyelesaian masalah. Bagi pembaca

1.

Memberikan

alternatif

cara

yang

efisien

dalam

penyelesaian

permainan puzzle Sudoku. 2.

5.

Menjadi bahan kajian yang dapat dikembangkan dikemudian hari.

Puzzle Sudoku

a. Sejarah Sudoku Sudoku juga dikenal sebagai Number Place atau Nanpure, adalah sejenis teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak. Sudoku adalah sebuah puzzle yang didasarkan pada konsep Latin Square. Latin Square sendiri diperkenalkan pada tahun 1783 oleh Leonhard Euler, seorang matematikawan asal Swiss. Permainan ini pertama kali diterbitkan di sebuah surat kabar Perancis pada 1895. Versi modern permainan ini dimulai di Indianapolis pada 1979. Kemudian menjadi terkenal kembali di Jepang pada 1986, ketika penerbit Nikoli menemukan teka-teki ini yang diciptakan Howard Garns seorang mantan arsitek yang meninggal tahun 1989. Kemudian Nikoli membawa permainan ini ke Jepang dan menerbitkannya di sebuah media cetak khusus puzzle miliknya “Monthly Nikolist”. Mereka menamakannya “Suuji Wa Dokushin Ni Kagiru”, disingkat Sudoku (artinya "angkaangkanya harus tetap tunggal") dan mematenkan kata ini. Media lain pun kemudian menerbitkan permainan ini dengan nama aslinya, Number Place. Mulai saat itulah permainan ini mewabah di Jepang. Lebih dari 600.000 majalah tentang Sudoku terjual di Jepang setiap bulannya. Lucunya, mereka lebih senang menyebutnya Number Place, sementara orang di luar Jepang menamakannya Sudoku. Sudoku menjadi benar-benar mewabah di Inggris ketika The Daily Telegraph mengenalkannya pada pembacanya pada bulan Februari 2005. Media lain pun kemudian mengikuti dengan menyediakan permainan ini di edisinya masing-masing. 2

Pertengahan Mei 2005 adalah awal demam Sudoku. Segala hal tentang Sudoku menjadi ladang uang, pemuatan di koran harian, penerbitan buku, penerbitan majalah, pertunjukkan televisi, siaran radio, pelayanan langganan lewat email, dan penyediaan layanan di telepon genggam. Khusus untuk buku, News & Star mencatat bahwa 6 dari 10 buku nonfiksi yang paling laris saat ini adalah buku tentang Sudoku. Dari Inggris, Sudoku kemudian menyebar di daratan Eropa, dari Prancis sampai Slowakia, lalu menular pula ke Australia dan Amerika.

b. Aturan Permainan Sudoku Aturan permainan untuk puzzle ini sangat sederhana, untuk menyelesaikan permainan ini tidak diperlukan pengetahuan umum, kepandaian atas bahasa tertentu, juga kemampuan matematika. Tetapi hanya memerlukan kecermatan, kesabaran, dan logika. Papan Sudoku terbuat dari sembilan buah kotak berukuran 3×3 (disebut blok/ subgrid) yang disusun sedemikian rupa sehingga menghasilkan kotak besar berukuran 9×9. Beberapa kotak sudah diisi sebagai petunjuk awal dan tugas pemain adalah melengkapi angka-angka pada kotak yang lain sehingga keseluruhan papan permainan terisi angka secara lengkap. Aturan permainannya sangatlah sederhana:

1.

Kotak-kotak pada setiap baris, kolom, dan blok/ subgrid harus berisi sebuah angka.

2.

Angka-angka yang diisikan harus unik dari 1 hingga 9 sehingga dalam 1 blok/ subgrid hanya terdiri atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1 baris maupun kolom. Angka-angka ini sebenarnya tidak memiliki hubungan aritmetis satu sama

lain. Anda boleh menggantinya dengan 9 huruf, lambang, atau warna yang berbeda.

6.

Algoritma Backtracking (Runut Balik) Algoritma backtracking pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950

menyajikan uraian umum tentang backtracking dan penerapannya dalam berbagai persoalan 3

dan aplikasi. Algoritma backtracking (runut balik) merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS) untuk mencari solusi persoalan secara lebih mangkus, maka pencarian solusi dilakukan dengan menelusuri suatu struktur berbentuk pohon berakar. Algoritma backtracking adalah suatu algoritma yang merupakan perbaikan dari algoritma brute force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Backtracking merupakan bentuk tipikal dari algoritma rekursif dan berbasis pada DFS dalam mencari solusi yang tepat. Selain itu, algoritma ini juga merupakan metode yang mencoba-coba beberapa keputusan sampai kita menemukan salah satu yang ”berjalan”. Kita tidak perlu memeriksa semua kemungkinan solusi yang ada, tetapi cukup yang mengarah kepada solusi saja. Dengan memangkas (pruning) simpul-simpul yang tidak mengarah ke solusi, sehingga waktu pencarian dapat dihemat. Algoritma ini banyak diterapkan untuk program games dan permasalahan pada bidang kecerdasan buatan.

7.

Strategi umum penyelesaian teka-teki Sudoku

1. Pemindahan (scanning) Berupa proses memindahkan baris atau kolom untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin.

2. Penandaan (marking) Berupa analisa logika, dengan menandai kandidat angka yang dapat dimasukkan dalam sebuah sel.

3. Analisa (analysing) Berupa eliminasi kandidat, dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya 1 kandidat.

8.

Prinsip Pencarian Solusi dengan Metode Backtracking Seperti yang telah dijelaskan bahwa pencarian solusi dengan menggunakan

algoritma backtracking digunakan pohon ruang status. Cara kerjanya adalah dengan membentuk lintasan dari akar ke daun.

4

Pohon Ruang Status Langkah-langkah pencarian solusi pada pohon ruang status:

1.

Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan pembentukan yang dipakai adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E (Expand-node). Simpul dinomori dari atas ke bawah sesuai dengan urutan kelahirannya.

2.

Tiap kali simpul-E diperluas, lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.

3.

Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan backtracking ke simpul hidup terdekat (simpul orang tua). Selanjutnya simpul ini menjadi simpul-E yang baru. Lintasan baru dibangun kembali sampai lintasan tersebut membentuk solusi.

4.

Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada simpul hidup untuk backtracking atau simpul yang dapat di diperluas.

9.

Algoritma Backtracking sebagai Pemecahan Solusi Permasalahan Puzzle Sudoku Penulis menganalisa pencarian solusi untuk game sudoku ini dengan algoritma

backtracking karena beberapa alasan, antara lain: 1.

Tidak memiliki informasi yang cukup untuk mengetahui sel mana yang harus diisi terlebih dahulu.

2.

Terdapat beberapa kemungkinan angka yang dapat diisikan ke dalam sel.

3.

Setiap keputusan yang diambil mengarah pada sekumpulan kemungkinan baru.

4.

Beberapa pilihan yang ada, kemungkinan merupakan solusi dari permainan ini.

5

Dengan adanya pilihan solusi yang banyak ini membuat kebanyakan orang memilih untuk melakukan pilihan solusi secara brute force, yang artinya mencoba semua kemungkinan yang ada dan dilakukan secara acak.

Proses diulang sampai sejumlah sel (i=1 to 81)

Mencari sel yang masih kosong

Kandidat angka yang akan diisikan

Pengecekan kandidat angka terhadap angka yang terdapat pada baris, kolom dan blok yang bersesuaian

Hasil pengecekan=solusi

Isi sel dengan solusi

Hasil pengecekan=himpunan kemungkinan solusi Diagram Blok Pencarian Solusi

10. Penerapan algoritma backtracking dalam teka-teki Sudoku a.

Pengorganisasian Solusi

1. Ruang Solusi (solution space) Semua kemungkinan solusi dari persoalan dinyatakan sebagai vektor X = (x1, x2, x3, x4, x5, x6, x7, x8, x9), xi Є Si 6

S1 = S2 = S3= S4= S5= S6= S7= S8= S9, Si = {1,2,3,4,5,6,7,8,9}, xi = 1 ΙΙ 2 ΙΙ 3 ΙΙ 4 ΙΙ 5 ΙΙ 6 ΙΙ 7 ΙΙ 8 ΙΙ 9 Maka, ruang solusi = S1 x S2 x S3 x S4 x S5 x S6 x S7 x S8 x S9 2. Fungsi Pembangkit T(k) yang membangkitkan nilai untuk x(k), yaitu bagian himpunan solusi.

3. Fungsi Pembatas (bounding space) Baris dinyatakan sebagai B(x1, x2, x3, x4, x5, x6, x7, x8, x9) Kolom dinyatakan sebagai K(x1, x2, x3, x4, x5, x6, x7, x8, x9) Blok/ Subgrid dinyatakan sebagai G(x1, x2, x3, x4, x5, x6, x7, x8, x9) Fungsi pembatas = b.

∑

k

i =1

Bi K i Gi = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9

Start untuk game Sudoku FlowChart pencarian solusi

Sel yang sudah diketahui isinya

i = 0 to 80 i = i +1 T T End

i≤ 81

Y

Sel(i) = kosong Y

Cek baris eliminasi angka yang tidak mungkin = himpunan solusi A Cek himpunan solusi sel(i) dengan himpunan solusi sel yang bersesuaian = himpunan solusi sel(i) Y T

Ada himpunan solusi yang bersesuaian

Simpan himpunan solusi sel(i)

Cek kolom eliminasi angka yang tidak mungkin = himpunan solusi B

Cek blok/ subgrid eliminasi angka yang tidak mungkin = himpunan solusi C

Himpunan solusi A ∩ Himpunan solusi B ∩ Himpunan solusi C = Himpunan solusi sel(i)

T

7 Flowchart pencarian solusi

Σ himpunan solusi =1 Y Cetak Solusi

c.

Pohon Ruang Status (State Space Tree) Pohon dinamis yang dibentuk selama pencarian solusi untuk persoalan puzzle

sudoku dengan ukuran 9x9 adalah: X2=1 2

B

3

X3=1

X2=2 X2=3

X3=2

4

6

B

7

B X4=1

X3=3 3

8

X1=1 X1=2 1 2

X4=2

dst…

X1=5

1

B

1 0

B

dst…

1 1

B

X4=3

X1=3 X1=4

9

5

1 3

dst…

1 4

X1=6 1 5 X1=7

X1=8 X1=9

1 6

1 7

1 8

Pohon Ruang Status persoalan puzzle sudoku d.

Algoritma Backtracking dalam VB Penulisan kode program dilakukan dengan menggunakan fungsi rekursi.

8

Algoritma backtracking dalam Visual Basic 6.0 sebagai berikut: Declaration General Dim N as integer Dim tabel(1…N2)(1…N2)

‘ ukuran papan sudoku ‘ representasi papan sudoku

Prosedur Utama Private Sub solusi() Menyelesaikan teka-teki Sudoku pada papan n2 *n2, versi rekursif End sub Algoritma If (Selesai) then Exit sub ‘Papan sudah selesai diisi dan program selesai Else Updatetabel() ‘Update sel tabel yang masih kosong If(!ValidBaris) then Backtracking() Else ‘jika baris valid maka periksa kolom If(!ValidKolom) then Backtracking() Else ‘jika kolom valid maka periksa subgrid If(!ValidSubgrid) then Backtracking() Else ‘jika subgrid valid maka panggil prosedur rekursif Solusi() End if End if End if End if

11. Pengujian dan Analisa Selain untuk mengetahui unjuk kerja sistem, pengujian juga bertujuan untuk mengetahui kelebihan dan kekurangan dari sistem yang telah dibangun. Hasil-hasil pengujian tersebut nantinya akan dianalisa agar dapat diketahui mengapa terjadi kekurangan tersebut. a.

Pengujian kemampuan No. 1 2 3 4 5 6 7 8 9 10

Nomor Penyelesaian Kebenaran Game 108 Berhasil Berhasil 112 Berhasil Berhasil 113 Berhasil Berhasil 114 Berhasil Berhasil 115 Berhasil Berhasil 116 Berhasil Berhasil 117 Berhasil Berhasil 118 Berhasil Berhasil 119 Berhasil Berhasil 120 Berhasil Berhasil Data pengujian kemampuan 9

b.

Pengujian kecepatan Waktu Penyelesaian (mili detik) 1 108 2,32 2 112 2,35 3 113 2,78 4 114 3,01 5 115 2,41 6 116 2,56 7 117 2,35 8 118 2,33 9 119 2,68 10 120 2,79 Data pengujian kecepatan

Pengujian ke

Nomor Game

c. Perbandingan dengan algoritma Brute Force Waktu Penyelesaian (mili detik) Backtracking Brute Force 1 108 2,32 265 2 112 2,35 236 3 113 2,78 260 4 114 3,01 300 5 115 2,41 233 6 116 2,56 245 7 117 2,35 265 8 118 2,33 231 9 119 2,68 246 10 120 2,79 273 Data pengujian perbandingan dengan algoritma Brute Force No.

Nomor Game

12. Kesimpulan Pengujian Dari hasil pengujian diatas terlihat bahwa pada 10 (sepuluh) kali pengujian kemampuan aplikasi untuk menemukan solusi dalam penyelesaian game sudoku telah berhasil dilakukan dengan benar. Demikian juga pada pengujian kecepatan yang dilakukan terlihat bahwa waktu yang dibutuhkan untuk menemukan solusi cukup singkat, hal ini dikarenakan pada algoritma Backtracking pencarian solusi hanya pada angka yang mungkin saja.

Menurut

paper

yang

diterbitkan

oleh

Felgenhauer

dan

Jarvis,

terdapat

6.670.903.752.021.072.936.960 (6,67x1021) kemungkinan cara pengisian Sudoku yang mungkin sesuai dengan aturan. Oleh karena itu cara backtracking ini lebih mangkus dan sering dipakai untuk menyelesaikan Sudoku.

10

Pengujian perbandingan dilakukan dengan membandingkan algoritma backtracking dengan algoritma brute force. Penyelesaian dengan metode brute force merupakan cara yang paling naif yaitu dengan cara mencoba semua kemungkinan pengisian sel dengan angka 1 sampai 9 tanpa memperdulikan angka-angka yang telah terisi serta tanpa mematuhi aturan Sudoku. Jadi dengan algoritma ini semua kemungkinan dicoba termasuk kasus yang menyalahi aturan Sudoku. Sehingga jumlah kemungkinan pengisian setiap sel sebanyak 981 buah (1,9 x 1077 buah) kemungkinan. Tentu saja cara ini kurang tepat karena kasus terburuk (worst case) juga dicoba. Sehingga dapat disimpulkan bahwa teknik brute force sangat lambat jika dibandingkan dengan teknik backtracking. 13. Kesimpulan

1. Permainan teka-teki Sudoku dapat diselesaikan dengan algoritma Backtracking. Dengan menggunakan algoritma ini, teka-teki Sudoku dapat diselesaikan dan waktu untuk menyelesaikan teka-teki ini lebih singkat dibandingkan dengan algoritma bruteforce.

2. Algoritma Backtracking sangat berguna untuk mencari solusi jalur kombinasi yang diperlukan untuk mendapatkan solusi secara optimal.

3. Algoritma Backtracking mudah diimplementasikan dengan bahasa pemrograman yang mendukung pemanggilan fungsi/ prosedur rekursif. 14. Saran Adapun saran yang dapat diberikan demi pengembangan aplikasi penyelesaian game sudoku ini adalah :

1. Jika ingin menyelesaikan kasus dengan banyak kemungkinan seperti game sudoku beserta pengembangannya maka gunakanlah algoritma Backtracking.

2. Untuk mendapatkan hasil optimal, kombinasikan algoritma Backtracking ini dengan algoritma-algoritma yang lain.

3. Untuk alokasi memori yang akan dipakai untuk menyimpan langkah-langkah penyelesaian sebaiknya menggunakan dynamic array, karena sebagian besar program yang menggunakan algoritma ini menghasilkan solusi yang tidak dapat diprediksi.

11