contoh proposal judul baru revisi desember 2013(1)

ANALISIS PENYELESAIAN PUZZLE SUDOKU

Diajukan Untuk Menempuh Tugas Khusus dan Tugas Akhir(keterangan disesuaikan dengan tujuan pengajuan j

Lukman Hariadi

JURUSAN TEKNIK INFORMATIKA

SEKOLAH TINGGI MANAJEMEN INFORMATIK

ANALISIS PENYELESAIAN PUZZLE SUDOKU DENGAN MENERAPKAN

ALGORITMA BACKTRACKING

(berbentuk piramida terbalik)

PROPOSAL JUDUL

Diajukan Untuk Menempuh Tugas Khusus dan Tugas Akhirketerangan disesuaikan dengan tujuan pengajuan judul

Oleh

Lukman Hariadi 10201045

JURUSAN TEKNIK INFORMATIKA

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER

MALANG

2013

DENGAN MENERAPKAN

Diajukan Untuk Menempuh Tugas Khusus dan Tugas Akhir udul)

A DAN KOMPUTER ASIA

1. LATAR BELAKANG

(menunjukkan permasalahan, siapa yang memiliki masalah, kapan, dimana,

dan hubungannya dengan metode yang dipilih)

Permainan Sudoku adalah permainan yang dapat melatih logika

manusia dalam berpikir cepat dan teliti. Permainan ini tidak bisa sembarang

dimainkan, karena bila bermain dengan sembarangan di awal permainan,

tidak bisa menyelesaikan game ini. Puzzle Sudoku memiliki 9 sub-matriks

berukuran 3x3 yang disebut subgrid. Tujuan dari permainan ini adalah

mengisi semua sel dengan angka 1 sampai 9 sedemikian sehingga setiap

kolom, baris, dan subgrid mengandung angka 1 sampai 9 tepat satu buah.

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(1).

Tetapi cara ini tentu saja tidak tepat karena kemungkinannya akan sangat

banyak sekali. Karena itu algoritma ini diperbaiki dengan menambahkan

batasan (constraints), yaitu tidak boleh ada angka yang sama dalam satu

baris, kolom atau subgrid. Cara ini bisa mereduksi jumlah kemungkinan

secara signifikan sehingga algoritma menjadi lebih tepat.

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

(menunjukkan permasalahan apa yang akan diselesaikan di bagian

pembahasan)

Bagaimana menyelesaikan permainan puzzle Sudoku dengan

menerapkan algoritma backtracking.

3. BATASAN MASALAH

(dapat dibatasi dari segi sistem, konsep/model, metode, data, tools

dan sebagainya)

a. Analisis penyelesaian dilakukan untuk game puzzle Sudoku

berukuran 9 x 9 dengan inputan angka 1 sampai dengan 9.

b. Metode yang diterapkan adalah dengan algoritma backtracking

dengan constrain.

c. Bahasa pemrograman yang digunakan adalah Visual Basic 6.0.

d. Database yang digunakan Microsoft Access 2003.

4. TUJUAN DAN MANFAAT PENULISAN

Tujuan

a. Mempopulerkan permainan puzzle Sudoku di kalangan mahasiswa

untuk dapat melatih logika manusia dalam berpikir cepat dan teliti.

b. Membantu para penggemar permainan Sudoku dalam mencari cara

penyelesaian permainan yang lebih cepat dan tepat.

Manfaat Bagi Penulis

a. Belajar menganalisa permasalahan dengan solusi secara ilmiah

yaitu dengan memanfaatkan algoritma backtracking.

b. Dapat mengasah otak dalam berfikir secara cepat dan teliti untuk

mencari penyelesaian masalah.

Manfaat Bagi pembaca

a. Memberikan alternatif cara yang efisien dalam penyelesaian

permainan puzzle Sudoku.

b. Menjadi bahan kajian yang dapat dikembangkan dikemudian hari.

5. METODOLOGI PENELITIAN

(menjelaskan langkah-langkah apa yang akan dilakukan dalam

pelaksanaan penelitian sampai penelitian selesai. Jika dilakukan observasi,

dijelaskan tempatnya dimana dan data apa yang dicari/diamati)

Untuk mendukung penyelesaian penelitian ini digunakan beberapa

metodologi, yaitu:

a. Studi Pustaka (Library Research)

Studi Pustaka dilakukan dengan cara mempelajari teori-teori

literatur dan buku-buku yang berhubungan dengan objek kajian

sebagai dasar dalam penelitian ini, dengan tujuan memperoleh dasar

teoritis gambaran dari apa yang dilakukan. Teori yang dipelajari

yaitu: permainan puzzle, teori graph dan tree, algoritma backtracking,

dan sebagainya.

b. Analisa Data

Selanjutnya akan dilakukan analisa terhadap data yang telah

diperoleh dari proses pengumpulan data. Analisa data bertujuan

untuk mengetahui variabel-varibel apa yang dibutuhkan dalam

pemodelan permainan Sudoku kedalam algoritma backtracking,

serta kebutuhan input dan output sistem.

c. Perancangan

Berdasarkan analisa data yang telah dilakukan selanjutnya

dilakukan pemodelan data ke dalam algoritma backtracking.

Perancangan algoritma menggunakan flowchart dan pseudocode.

d. Implementasi

Hasil perancangan selanjutnya diimplementasikan dalam

bentuk kode program. Pada penelitian ini akan digunakan bahasa

pemrograman Visual Basic 6.0 dan database Microsoft Access 2003.

e. Pengujian

Akan dilakukan pengujian data untuk mengukur keakuratan

yang dihasilkan dari program yang telah dibuat.

6. LANDASAN TEORI

(berisi teori singkat tentang hal-hal yang penting saja, terutama tentang

objek dan algoritmanya)

a. Puzzle Sudoku

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:

- Kotak-kotak pada setiap baris, kolom, dan blok/

berisi sebuah angka.

- Angka-angka yang diisikan

dalam 1 blok/

berulang dan tidak ada angka yang berulang dalam 1 baris

maupun kolom.

Angka-angka ini sebenarnya tidak memiliki hubungan aritmetis

satu sama lain.

warna yang berbeda.

b. Algoritma Backtracking

Algoritma

Lehmer pada tahun 1950. Dalam perkembangannya beberapa ahli


sangatlah sederhana:

kotak pada setiap baris, kolom, dan blok/ subgrid

berisi sebuah angka.

angka yang diisikan harus unik dari 1 hingga 9 sehingga

dalam 1 blok/ subgrid hanya terdiri atas angka 1-


maupun kolom.

angka ini sebenarnya tidak memiliki hubungan aritmetis

satu sama lain. Boleh digantikan dengan 9 huruf, lambang, atau

warna yang berbeda.

Gambar 1. Puzzle Sudoku

Algoritma Backtracking

Algoritma backtracking pertama kali diperkenalkan oleh D.H.



subgrid harus

harus unik dari 1 hingga 9 sehingga

-9 yang tidak


angka ini sebenarnya tidak memiliki hubungan aritmetis

dengan 9 huruf, lambang, atau

pertama kali diperkenalkan oleh D.H.


seperti RJ Walker, Golomb, dan Baumert 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 lebih efektif, maka

pencarian solusi dilakukan dengan menelusuri suatu struktur

berbentuk pohon berakar secara preorder. Proses ini dicirikan

dengan ekspansi simpul terdalam lebih dahulu sampai tidak

ditemukan lagi suksesor dari suatu simpul.

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

waktu pencarian dapat dihemat. Algoritma ini banyak diterapkan

untuk program games dan permasalahan pada bidang kecerdasan

buatan.

Saat ini

program games seperti permainan tic

keluar dalam sebuah labirin, catur dan sebagainya serta untuk

menyelesaikan masalah

(artificial intelligence

Prinsip dasar algoritma

kemungkinan solusi yang ada. Perbedaan dengan algoritma

force adalah pada konsep dasarnya, yaitu pada

solusi dibuat dalam bentuk pohon solusi (

tersebut akan ditelusuri secara DFS sehingga ditemukan solusi

terbaik yang diinginkan.

) simpul-simpul yang tidak mengarah ke solusi, sehingga



Saat ini algoritma backtracking banyak diterapkan untuk

program games seperti permainan tic-tac-toe, menemukan jalan


menyelesaikan masalah-masalah pada bidang kecerdasan buatan

artificial intelligence).

Prinsip dasar algoritma backtracking adalah mencoba semua

kemungkinan solusi yang ada. Perbedaan dengan algoritma

adalah pada konsep dasarnya, yaitu pada backtracking

solusi dibuat dalam bentuk pohon solusi (tree), dan kemudian pohon


terbaik yang diinginkan.

Gambar 2. Pohon Solusi (tree)

simpul yang tidak mengarah ke solusi, sehingga



banyak diterapkan untuk

toe, menemukan jalan


masalah pada bidang kecerdasan buatan

adalah mencoba semua

kemungkinan solusi yang ada. Perbedaan dengan algoritma brute

backtracking semua

), dan kemudian pohon


Misalkan pohon di atas menggambarkan solusi dari suatu

persoalan. Jika kita ingin mencari solusi dari A ke E, maka jalur yang

harus ditempuh adalah (A-B-E). Demikian juga untuk solusi-solusi

yang lain. Algoritma backtracking akan memeriksa jalur secara DFS,

yaitu dari solusi terdalam pertama yang ditemui yaitu solusi E. Jika

ternyata E bukanlah solusi yang diharapkan, maka pencarian akan

dilanjutkan ke F. Jalur yang harus dilalui untuk bisa mencapai E

adalah (A-B-E) dan untuk mencapai F adalah (A-B-F). Kedua solusi

tersebut memiliki jalur awal yang sama, yaitu (A-B). Jadi, dari pada

memeriksa ulang jalur dari A kemudian B, maka jalur (A-B) disimpan

dulu dan langsung memeriksa solusi F. Untuk kasus pohon yang

lebih rumit, cara ini dianggap lebih efisien daripada jika menggunakan

algoritma Brute-Force.

Properti Umum Metode Runut Balik (Backtracking)

1. Solusi persoalan

Solusi dinyatakan sebagai vektor dengan n-index:

X = (x1, x2, …, xn), xi ∈ himpunan berhingga Si

Mungkin saja S1 = S2 = … = Sn

Keterangan: X = vektor solusi

x = komponen vektor solusi

S = himpunan kemungkinan solusi

Contoh: Si = {0, 1}, xi = 0 atau 1

2. Fungsi pembangkit nilai xk

Dinyatakan sebagai: T(k)

T(k) membangkitkan nilai untuk xk, yang merupakan komponen

vektor solusi.

Keterangan: x = komponen vektor solusi

k = index komponen vektor solusi

T = fungsi pembangkit

3. Fungsi pembatas

Pada beberapa persoalan fungsi ini dinamakan fungsi kriteria.

Dinyatakan sebagai B(x1, x2, …, xk)

Fungsi pembatas menentukan apakah (x1, x2, …, xk) mengarah

ke solusi. B bernilai true jika (x1, x2, …, xk) mengarah ke solusi.

Jika true, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi

jika false, maka (x1, x2, …, xk) dibuang dan tidak dipertimbangkan

lagi dalam pencarian solusi.

Keterangan: x = komponen vektor solusi

k = index komponen vektor solusi

B = fungsi pembatas

7. ANALISA DATA

(berisi bentuk

Mining, harus dijelaskan bentuk data primer dari tempat observasi seperti apa

kemudian akan dimodelkan seperti apa ke dalam sistemnya)

Dalam penerapan

dibutuhkan data mengenai bentuk dan prosedur permainan serta

penerapan algoritma sehingga dapat dimodelkan untuk menyelesaikan

permainan Sudoku.

1. Papan permainan 9 x 9, sehingga terdapat 81 sel

2. Set awal permainan

a. Angka

b. Letak/

Gambar

(berisi bentuk data yang akan diolah, missal: untuk SPK atau Data


kemudian akan dimodelkan seperti apa ke dalam sistemnya)

penerapan algoritma backtracking pada permainan Sudoku ini

dibutuhkan data mengenai bentuk dan prosedur permainan serta


permainan 9 x 9, sehingga terdapat 81 sel.

awal permainan

ngka yang diketahui

etak/posisi angka pada papan permainan

Gambar 3. Data awal permainan Sudoku

untuk SPK atau Data


da permainan Sudoku ini

dibutuhkan data mengenai bentuk dan prosedur permainan serta prosedur


8. PEMBAHASAN

(membahas pemodelan permasalahan ke dalam metode/algoritma

yang akan digunakan)

Analisa pencarian solusi untuk game sudoku ini dengan algoritma

backtracking karena beberapa alasan, antara lain:

a. Tidak memiliki informasi yang cukup untuk mengetahui sel

mana yang harus diisi terlebih dahulu.

b. Terdapat beberapa kemungkinan angka yang dapat diisikan ke

dalam sel.

c. Setiap keputusan yang diambil mengarah pada sekumpulan

kemungkinan baru.

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

Penggunaan algoritma backtracking ini akan terlihat dalam proses

pengisian sel dengan sebuah angka dimana terdapat beberapa kemungkinan

angka yang sesuai untuk sel tersebut. Pada pengisian selanjutnya, angka

yang diisikan akan dicocokkan dengan angka-angka pada sel dalam baris,

kolom dan subgrid yang bersesuaian. Metode membandingkan dan

pencarian angka yang menuju ke solusi dilakukan secara rekursif. Proses

pencarian solusi digambarkan pada diagram blok berikut ini:

Gambar 4. Diagram Blok Pencarian Solusi

Keterangan:

a. Dilakukan perulangan sebanyak sel yang masih kosong.

b. Mendefinisikan kandidat angka yang akan diisikan.

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)

c. Pencarian kandidat angka dilakukan dengan pengecekan angka

pada baris, kolom dan blok/ subgrid yang bersesuaian. Angka

yang sudah terdapat pada baris, kolom dan blok/ subgrid yang

bersesuaian akan di eliminasi dari himpunan kemungkinan

solusi.

d. Pengecekan dilakukan dengan mengeliminasi kandidat angka

yang tidak mengarah ke solusi.

e. Jika pengecekan menghasilkan solusi, maka dilakukan proses

pengisian angka dan proses kembali ke tahap awal. Tetapi jika

pengecekan angka belum menghasilkan solusi, maka dilakukan

backtracking ke kandidat angka yang lain.

Contoh pencarian solusi yang dapat dilakukan sebagai salah satu penerapan

algoritma backtracking:

1. Pencarian sel yang kosong.

4 8 7 5 2 1

3 4

6 2 7 8

2 8 1

1 5 2 9 7

9 1 2

1 2 4 9

5 6

6 4 1 3 5 8

Gambar 5. Pencarian sel kosong

Sel pertama yang kosong adalah pada baris ke-1 kolom ke-2.

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

2. Angka yang akan diisikan adalah 1,2,3,4,5,6,7,8,9.

3. Pencarian kandidat angka yang akan diisikan

Kandidat angka yang mungkin adalah sebagai berikut:

Baris ke-1, kolom ke-2 (S1,2)

a. Kandidat yang mungkin pada baris ke-1, B={3,6,9}

b. Kandidat yang mungkin pada kolom ke-2, K={3,4,7,8,9}

c. Kandidat yang mungkin pada blok ke-1, G={1,5,7,9}

4. Pengecekan

Pengecekan dapat direpresentasikan dengan himpunan seperti pada

gambar berikut:

Gambar 6. Himpunan Solusi

Himpunan A = {3,6,9}

Himpunan B = {3,4,7,8,9}

Himpunan C = {1,5,7,9}

A ∩ B ∩ C = {9}, Jadi, solusinya adalah 9.

6 9

3

7

4, 8

1, 5

A

B

C

5. Solusi diisikan pada sel tersebut.

4 9 8 7 5 2 1 3 4 6 2 7 8

2 8 1 1 5 2 9 7 9 1 2 1 2 4 9 5 6 6 4 1 3 5 8

Gambar 7. Pengisian Solusi ke-1 pada sel

6. Selanjutnya melakukan pencarian sel yang kosong berikutnya yaitu sel

pada baris ke-1 kolom ke-6. Proses dilakukan berulang-ulang sampai

didapatkan solusi untuk sel yang kosong pada baris ke-1:

S1,6 = {6}, S1,9 = {3}

4 9 8 7 5 6 2 1 3 3 4 6 2 7 8 2 8 1 1 5 2 9 7 9 1 2

1 2 4 9 5 6 6 4 1 3 5 8

Gambar 8. Pengisian Solusi pada baris ke-1

7. Pencarian solusi pada baris ke-2 akan dihadapkan pada kasus yang

berbeda yaitu terdapat himpunan solusi yang lebih dari satu. Dalam

hal ini akan dilakukan backtrack ke kandidat angka yang lain. Hasil

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

pengecekan berupa himpunan solusi akan disimpan yang kemudian

dapat digunakan untuk proses backtracking.

Pencarian kandidat angka untuk baris ke-2:

S2,2 = {7}, S2,3 = {1,5}, S2,5 = {6,8,9}, S2,6 = {2,6,8,9},

S2,7 = {6,9}, S2,8 = {5,6}, S2,9 = {5}

8. Selanjutnya dilakukan backtrack berdasarkan himpunan solusi yang

telah ada untuk masing-masing sel. Sehingga didapatkan solusi:

S2,2 = {7}, S2,3 = {1}, S2,5 = {8}, S2,6 = {2}, S2,7 = {9}

S2,8 = {6}, S2,9 = {5}

4 9 8 7 5 6 2 1 3 3 7 1 4 8 2 9 6 5 6 2 7 8 2 8 1

1 5 2 9 7 9 1 2 1 2 4 9 5 6 6 4 1 3 5 8

Gambar 9. Pengisian Solusi pada baris ke-2

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

9. Proses pencarian solusi dilakukan berulang-ulang sesuai jumlah sel

yang masih kosong sampai seluruh sel terisi oleh angka menurut

fungsi pembatas yang ada.

4 9 8 7 5 6 2 1 3 3 7 1 4 8 2 9 6 5 6 2 5 1 3 9 7 8 4

2 4 3 8 9 7 6 5 1 1 5 6 3 2 4 8 9 7 9 8 7 5 6 1 4 3 2 5 1 2 6 7 8 3 4 9 8 3 9 2 4 5 1 7 6 7 6 4 9 1 3 5 2 8

Gambar 10. Puzzle sudoku yang telah terselesaikan

Pohon Ruang Status (State Space Tree)

Pohon dinamis yang dibentuk selama pencarian solusi untuk

persoalan puzzle sudoku dengan ukuran 9x9 adalah:

1 1

5

1

4

1

3

1

2

2

1

6

1

7

1

8

1

9

X1=

X1=

X1=

3

X1=

X1=

X1=6

X1=

X1=

X1=

9

3

4

dst…

X2=

X2=2

B 6

7

dst…

X3=1

X3=2

B

B

5 8

X2=

X3= 9

1

0

dst…

B

B

1

1

X4=

X4=

X4=

B

1 2 3 4 5 6 7 8 9

1

2

3

4

5

6

7

8

9

9. DAFTAR PUSTAKA

a. Ajeng, Wirasati. ANALISA PENERAPAN ALGORITMA BACKTRACKING PADA GAME “ CROSSWORD PUZZLE. Sekolah Tinggi Teknologi Telkom. Bandung. 2005.

b. Deasy, Wulan dkk. Penerapan Algoritma Backtracking pada

Pewarnaan Graf. Fakultas Teknologi Industri ITB. Bandung. 2005. c. Daisy, Rahmania. Bahasa Komputer I. Politeknik Elektronika Negeri

Surabaya (ITS). 2002. d. Crispina, Pardede. MATEMATIKA DISKRIT. UNIVERSITAS

GUNADARMA, Jakarta. 2004. e. Crispina, Pardede. HIMPUNAN DAN OPERASI BINER, Teknik

Informatika Universitas Gunadarma. Jakarta. 2003. f. Dochi, Ramadhani. Runut Balik. E-learning Universitas Tanjungpura.

2006. (diakses tanggal 12 Juni 2007 jam 18:10)

contoh proposal judul baru revisi desember 2013(1)

Documents