contoh proposal judul baru desember

Upload: intan-galistri

Post on 16-Oct-2015

96 views

Category:

Documents


0 download

DESCRIPTION

proposal judul

TRANSCRIPT

ANALISIS PENYELESAIAN PUZZLE SUDOKU DENGAN MENERAPKAN ALGORITMA BACKTRACKING(berbentuk piramida terbalik)

PROPOSAL JUDULDiajukan Untuk Menempuh Tugas Khusus dan Tugas Akhir(keterangan disesuaikan dengan tujuan pengajuan judul)

OlehLukman Hariadi10201045

JURUSAN TEKNIK INFORMATIKASEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER ASIA MALANG2013

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 PENULISANTujuan (Tujuan dapat dibagi 2 yaitu: tujuan umum dan khusus)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.(penelitian bisa memberi manfaat bagi banyak pihak)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 pembacaa. 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 DataSelanjutnya 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. PerancanganBerdasarkan analisa data yang telah dilakukan selanjutnya dilakukan pemodelan data ke dalam algoritma backtracking. Perancangan algoritma menggunakan flowchart dan pseudocode.d. ImplementasiHasil perancangan selanjutnya diimplementasikan dalam bentuk kode program. Pada penelitian ini akan digunakan bahasa pemrograman Visual Basic 6.0 dan database Microsoft Access 2003.e. PengujianAkan 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 SudokuPapan Sudoku terbuat dari sembilan buah kotak berukuran 33 (disebut blok/ subgrid) yang disusun sedemikian rupa sehingga menghasilkan kotak besar berukuran 99. 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/ subgrid harus berisi sebuah angka. 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. Boleh digantikan dengan 9 huruf, lambang, atau warna yang berbeda.

Gambar 1. Puzzle Sudokub. Algoritma BacktrackingAlgoritma backtracking pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Dalam perkembangannya beberapa ahli 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-simpul yang tidak mengarah ke solusi, sehingga waktu pencarian dapat dihemat. Algoritma ini banyak diterapkan untuk program games dan permasalahan pada bidang kecerdasan buatan.Saat ini algoritma backtracking banyak diterapkan untuk program games seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur dan sebagainya serta untuk menyelesaikan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence). Prinsip dasar algoritma backtracking adalah mencoba semua kemungkinan solusi yang ada. Perbedaan dengan algoritma brute force adalah pada konsep dasarnya, yaitu pada backtracking semua solusi dibuat dalam bentuk pohon solusi (tree), dan kemudian pohon tersebut akan ditelusuri secara DFS sehingga ditemukan solusi terbaik yang diinginkan.

Gambar 2. Pohon Solusi (tree)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 persoalanSolusi dinyatakan sebagai vektor dengan n-index:X = (x1, x2, , xn), xi himpunan berhingga Si Mungkin saja S1 = S2 = = Sn Keterangan: X = vektor solusix = komponen vektor solusiS = himpunan kemungkinan solusiContoh: Si = {0, 1}, xi = 0 atau 12. Fungsi pembangkit nilai xkDinyatakan sebagai:T(k) T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi.Keterangan: x = komponen vektor solusik = index komponen vektor solusiT = fungsi pembangkit3. Fungsi pembatas Pada beberapa persoalan fungsi ini dinamakan fungsi kriteria.Dinyatakan sebagaiB(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 solusik = index komponen vektor solusiB = fungsi pembatas

7. ANALISA DATA(berisi bentuk data yang akan diolah, misal: untuk SPK atau Data Mining, harus dijelaskan bentuk data primer dari tempat observasi seperti apa kemudian akan dimodelkan seperti apa ke dalam sistemnya. Tunjukkan variable input dan outputnya)Dalam penerapan algoritma backtracking pada permainan Sudoku ini dibutuhkan data mengenai bentuk dan prosedur permainan serta prosedur 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 yang diketahuib. Letak/posisi angka pada papan permainan

Gambar 3. Data awal permainan Sudoku8. PEMBAHASAN(membahas pemodelan permasalahan ke dalam metode/algoritma yang akan digunakan)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 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 dengan diagram blok yang ditunjukkan pada gambar 4.Keterangan gambar 4:a. Dilakukan perulangan sebanyak sel yang masih kosong.b. Mendefinisikan kandidat angka yang akan diisikan.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.

Mencari sel yang masih kosongKandidat angka yang akan diisikanPengecekan kandidat angka terhadap angka yang terdapat pada baris, kolom dan blok yang bersesuaianIsi sel dengan solusiHasil pengecekan=solusiHasil pengecekan=himpunan kemungkinan solusiProses diulang sampai sejumlah sel (i=1 to 81)

Gambar 4. Diagram Blok Pencarian SolusiContoh pencarian solusi yang dapat dilakukan sebagai salah satu penerapan algoritma backtracking:1. 123456789123456789Pencarian sel yang kosong.487521

34

6278

281

15297

912

1249

56

641358

Gambar 5. Pencarian sel kosongSel pertama yang kosong adalah pada baris ke-1 kolom ke-2.2. Angka yang akan diisikan adalah 1,2,3,4,5,6,7,8,9.3. Pencarian kandidat angka yang akan diisikanKandidat 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. PengecekanPengecekan dapat direpresentasikan dengan himpunan seperti pada gambar berikut:

69374, 81, 5ABC

Gambar 6. Himpunan SolusiHimpunan 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.5. Solusi diisikan pada sel tersebut.11234567894987521

2345678934

6278

281

15297

912

1249

56

641358

Gambar 7. Pengisian Solusi ke-1 pada sel6. 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:

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

2345678934

6278

281

15297

912

1249

56

641358

Gambar 8. Pengisian Solusi pada baris ke-17. 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 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}

123456789123456789498756213

371482965

6278

281

15297

912

1249

56

641358

Gambar 9. Pengisian Solusi pada baris ke-29. 123456789123456789Proses pencarian solusi dilakukan berulang-ulang sesuai jumlah sel yang masih kosong sampai seluruh sel terisi oleh angka menurut fungsi pembatas yang ada.498756213

371482965

625139784

243897651

156324897

987561432

512678349

839245176

764913528

Gambar 10. Puzzle sudoku yang telah terselesaikan

Pohon Ruang Status (State Space Tree)

115141312216171819X1=1X1=2X1=3X1=4X1=5X1=6X1=7X1=8X1=934dstX2=1X2=2B67dstX3=1X3=2BB58X2=3X3=3910dstBB11X4=1X4=2X4=3BPohon dinamis yang dibentuk selama pencarian solusi untuk persoalan puzzle sudoku dengan ukuran 9x9 adalah:

9. DAFTAR PUSTAKA(minimal 5 referensi, termasuk 3 jurnal yang dilampirkan. Referensi internet yang diperbolehkan hanya e-book dan jurnal ilmiah)Ajeng, Wirasati. ANALISA PENERAPAN ALGORITMA BACKTRACKING PADA GAME CROSSWORD PUZZLE. Sekolah Tinggi Teknologi Telkom. Bandung. 2005.

Deasy, Wulan dkk. Penerapan Algoritma Backtracking pada Pewarnaan Graf. Fakultas Teknologi Industri ITB. Bandung. 2005.

Daisy, Rahmania. Bahasa Komputer I. Politeknik Elektronika Negeri Surabaya (ITS). 2002.

Crispina, Pardede. MATEMATIKA DISKRIT. UNIVERSITAS GUNADARMA, Jakarta. 2004.

Crispina, Pardede. HIMPUNAN DAN OPERASI BINER, Teknik Informatika Universitas Gunadarma. Jakarta. 2003.

Dochi, Ramadhani. Runut Balik. E-learning Universitas Tanjungpura. 2006. (diakses tanggal 12 Juni 2007 jam 18:10)