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 (runut-

balik). 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.

Manfaat

Bagi penulis

1. Mengaplikasikan disiplin ilmu yang telah diperoleh selama belajar di Perguruan

Tinggi Asia Malang Jurusan Teknik Informatika.

1

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. Menjadi bahan kajian yang dapat dikembangkan dikemudian hari.

5. 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 "angka-

angkanya 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.

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,

2

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

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

3

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.

Pohon Ruang Status

4

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.

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.

5

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

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)

6

Mencari sel yang masih kosong

Kandidat angka yang akan diisikan

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

yang bersesuaian

Isi sel dengan solusi

Hasil pengecekan=solusi

Hasil pengecekan=himpunan

kemungkinan solusi

Proses diulang sampai sejumlah sel (i=1 to

81)

Fungsi pembatas =

b. FlowChart pencarian solusi untuk game Sudoku

7

Start

Sel yang sudah diketahui isinya

i = 0 to 80

i ≤ 81

Sel(i) = kosong

Cek bariseliminasi angka yang tidak mungkin =

himpunan solusi A

Cek kolomeliminasi angka yang tidak mungkin =

himpunan solusi B

Cek blok/ subgrideliminasi angka yang tidak mungkin =

himpunan solusi C

Himpunan solusi A ∩ Himpunan solusi B ∩ Himpunan solusi C = Himpunan

solusi sel(i)

Σ himpunan solusi =1

Cetak Solusi

Simpan himpunan solusi sel(i)

Ada himpunan

solusi yang bersesuaian

Cek himpunan solusi sel(i) dengan himpunan solusi sel yang bersesuaian =

himpunan solusi sel(i)

Y

Y

T

Y

Y

T

T

End

i = i +1

T

Flowchart pencarian solusi

c. Pohon Ruang Status (State Space Tree)

Pohon dinamis yang dibentuk selama pencarian solusi untuk persoalan puzzle

sudoku dengan ukuran 9x9 adalah:

Pohon Ruang Status persoalan puzzle sudoku

d. Algoritma Backtracking dalam VB

Penulisan kode program dilakukan dengan menggunakan fungsi rekursi.

8

114

13

12

3

2

15

16

17

18

X1=1

X1=2

X1=3

X1=4

X1=5

X1=6

X1=7

X1=8

X1=9

3

4

dst…

X2=1

X2=2

B

6

7

dst…

X3=1

X3=2

B

B

58

X2=3

X3=39

10

dst…

B

B

11

X4=1

X4=2

X4=3

B

Algoritma backtracking dalam Visual Basic 6.0 sebagai berikut:

Declaration GeneralDim N as integer ‘ ukuran papan sudokuDim tabel(1…N2)(1…N2) ‘ representasi papan sudoku

Prosedur UtamaPrivate Sub solusi()

Menyelesaikan teka-teki Sudoku pada papan n2 *n2, versi rekursifEnd sub

AlgoritmaIf (Selesai) then

Exit sub ‘Papan sudah selesai diisi dan program selesaiElse

Updatetabel() ‘Update sel tabel yang masih kosongIf(!ValidBaris) then

Backtracking()Else

‘jika baris valid maka periksa kolomIf(!ValidKolom) then

Backtracking()Else

‘jika kolom valid maka periksa subgridIf(!ValidSubgrid) then

Backtracking()Else

‘jika subgrid valid maka panggil prosedur rekursifSolusi()

End ifEnd if

End ifEnd 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.Nomor Game

Penyelesaian Kebenaran

1 108 Berhasil Berhasil2 112 Berhasil Berhasil3 113 Berhasil Berhasil4 114 Berhasil Berhasil5 115 Berhasil Berhasil6 116 Berhasil Berhasil7 117 Berhasil Berhasil8 118 Berhasil Berhasil9 119 Berhasil Berhasil

10 120 Berhasil BerhasilData pengujian kemampuan

9

b. Pengujian kecepatan

Pengujian ke

Nomor Game

Waktu Penyelesaian

(mili detik)1 108 2,322 112 2,353 113 2,784 114 3,015 115 2,416 116 2,567 117 2,358 118 2,339 119 2,68

10 120 2,79Data pengujian kecepatan

c. Perbandingan dengan algoritma Brute Force

No. Nomor GameWaktu Penyelesaian

(mili detik)Backtracking Brute Force

1 108 2,32 2652 112 2,35 2363 113 2,78 2604 114 3,01 3005 115 2,41 2336 116 2,56 2457 117 2,35 2658 118 2,33 2319 119 2,68 246

10 120 2,79 273Data pengujian perbandingan dengan algoritma Brute Force

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.

Pengujian perbandingan dilakukan dengan membandingkan algoritma backtracking

dengan algoritma brute force. Penyelesaian dengan metode brute force merupakan cara

10

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 brute-

force.

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