PEMBANGKITAN DAN PENYELESAIAN SLITHER LINK DENGAN ANSWER SET PROGRAMMING DAN PROCEDURAL PROGRAMMING SALMAN FARIZI

PEMBANGKITAN DAN PENYELESAIAN SLITHER LINK DENGAN ANSWER SET PROGRAMMING DAN PROCEDURAL PROGRAMMING

SALMAN FARIZI

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011

ABSTRAK SALMAN FARIZI. Application of Generator and Solver Slither Link with Answer Set Programming and Procedural Programming. Supervised by MUSHTHOFA. Slither Link is a popular pencil-based puzzle game similar to Sudoku. This problem has been shown to be NP-Complete. The goal of the game is to link grid segments forming a loop such that the number of lines adjacent to a cell is equal to the number written on the cell. In this research, we investigate the use of Answer Set Programming as a formal representation of the game, and to prove an alternative solving method, as opposed to the procedural method. We then perform experiment to test the efficiency of Answer Set Programming compared to the procedural method in solving Slither Link. For the Anser Set Programming method, we use DLV as the solver, whereas for the procedural method we write a program in C++ to solve Slither Link in a procedural manner. The result shows that ASP performed consistently better than the procedural method we use. Keywords : Slither Link, Answer Set Programming, Logic Programming.

PEMBANGKITAN DAN PENYELESAIAN SLITHER LINK DENGAN ANSWER SET PROGRAMMING DAN PROCEDURAL PROGRAMMING

SALMAN FARIZI

Skripsi Sebagai salah suatu syarat untuk memperoleh gelar Sarjana Komputer pada Program Studi Ilmu Komputer

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011

Judul Skripsi Nama NIM

: Pembangkitan dan Penyelesaian Sliher Link dengan Answer Set Programming dan Procedural Programming : Salman Farizi : G64086006

Menyetujui:

Pembimbing

Mushthofa, S.Kom., M.Sc. NIP. 19820325 200912 1 003

Mengetahui: Ketua Departemen Ilmu Komputer Institut Pertanian Bogor

Dr. Ir. Sri Nurdiati, M.Sc NIP. 19601126 198601 2 001

Tanggal Lulus:

RIWAYAT HIDUP Penulis dilahirkan pada tanggal 10 Desember 1986 di Jakarta sebagai anak pertama dari dua bersaudara dari pasangan Hifni Machmud dan Esty Dianingsih. Penulis menyelesaikan pendidikan menengah atas pada tahun 2004 dari SMU Negeri 3 Bogor dan lulus program Diploma Manajemen Informatika Politeknik Manufaktur Astra di Jakarta pada tahun 2007. Selama tiga bulan penulis melaksanakan praktek kerja lapang di PT Gajah Tunggal tbk. Pada tahun 2007 sampai 2008 penulis bekerja pada salah satu perusahaan otomotif di Jakarta, kemudian penulis melanjutkan studi Sarjana di Departemen Ilmu Komputer jurusan Ilmu Komputer, Institut Pertanian Bogor pada tahun 2008.

PRAKATA Segala puji bagi Allah dan salawat serta salam atas Rasul Allah, Nabi Muhammad shalallahu alaihi wa salam serta kepada keluarga dan sahabat-sahabatnya. Melalui lembar ini penulis ingin menyampaikan terima kasih kepada Bapak Mushthofa S.Kom., M.Sc. selaku pembimbing yang telah meluangkan waktu dan tenaganya untuk membimbing penulis, memberikan ilmu-ilmu yang sangat berharga, serta dukungan selama penelitian ini berjalan. Bapak Dr. Ir. Agus Buono M.Si, M.Kom. dan Bapak Ahmad Ridha S.Kom., MS. yang telah bersedia menjadi penguji dalam pelaksanaan seminar dan sidang. Penulis juga mengucapkan terima kasih kepada seluruh keluarga, terutama Mama dan Bapak yang telah memberikan dukungannya, kasih sayang, pengorbanan, dan kesabarannya selama ini. Abang Sandi, Teteh Etsa, Syalfa, Uwa, Paman, serta Bibi yang selalu mengingatkan penulis untuk berdoa, berusaha, dan memberikan semangat untuk terus menyelesaikan tugas akhir. Teguh yang selalu membantu, memberi dukungan, pendapat, dan teman satu bimbingan selama ini. Teman-teman Badminton ilkom dan teman-teman acara nonton bareng yang selalu memberi keceriaan dan wawasan baru pada penulis. Abdul Rahmat Ramdhan yang tanpa lelah selalu memberi dukungan pada seminar dan sidang, serta teman-teman Ilkom Ekstensi angkatan 3 terima kasih untuk kebersamaan selama kuliah di Ilmu Komputer IPB. Seluruh staf pengajar yang telah memberikan ilmu yang berharga selama penulis menuntut ilmu di Departemen Ilmu Komputer. Seluruh staf administrasi dan perpustakaan Departemen Ilmu Komputer yang selalu memberikan kemudahan dalam mengurus segala macam hal berkaitan dengan perkuliahan, serta pihak lain yang tidak bisa disebutkan satu-persatu. Sebagaimana manusia yang tidak luput dari kesalahan, penulis menyadari bahwa karya ilmiah ini jauh dari sempurna. Namun penulis berharap semoga karya ini bisa berguna untuk siapapun yang membacanya.

Bogor, Mei 2011

Salman Farizi

DAFTAR ISI Halaman

DAFTAR GAMBAR ................................................................................................................... v DAFTAR LAMPIRAN .............................................................................................................. vi PENDAHULUAN ....................................................................................................................... 1 Latar Belakang ........................................................................................................................ 1 Tujuan Penelitian .................................................................................................................... 1 Ruang Lingkup Penelitian ...................................................................................................... 1 Manfaat Penelitian .................................................................................................................. 1 TINJAUAN PUSTAKA .............................................................................................................. 1 NP-Complete........................................................................................................................... 1 Logic Programming ................................................................................................................ 2 Answer set programming ........................................................................................................ 2 DLV (datalog with disjunction) .............................................................................................. 4 Slither link ............................................................................................................................... 5 METODOLOGI .......................................................................................................................... 5 Formulasi aturan pembangkitan slither link ............................................................................ 5 Formulasi aturan penyelesaian ................................................................................................ 6 Pembangunan front end .......................................................................................................... 7 Arsitektur sistem ..................................................................................................................... 8 HASIL DAN PEMBAHASAN ................................................................................................... 8 Domain masalah dalam DLV .................................................................................................. 8 Encoding dengan DLV ........................................................................................................... 9 Menjalankan model penyelesaian slither link ....................................................................... 12 Implementasi dengan Procedural Programming .................................................................. 13 Struktur data.......................................................................................................................... 13 Hasil Pengujian ..................................................................................................................... 14 KESIMPULAN DAN SARAN ................................................................................................. 15 Kesimpulan ........................................................................................................................... 15 Saran ..................................................................................................................................... 15 DAFTAR PUSTAKA ................................................................................................................ 15 LAMPIRAN .............................................................................................................................. 16

iv

DAFTAR GAMBAR Halaman 1 Hubungan antara P, NP, dan NPC (Cormen et al 2001). ............................................................... 2 2 Graf tujuh kota. .............................................................................................................................. 5 3 Masalah slither link dan solusinya (Yato 2003). ............................................................................ 5 4 Formulasi pembangkitan. ............................................................................................................... 5 5 Grafik tingkat kesulitan puzzle berbanding dengan constraint puzzle. ........................................... 6 6 Formulasi Penyelesaian. ................................................................................................................. 6 7 Cell dengan nilai 0 (Conceptis puzzle 1997). ................................................................................. 6 8 Cell bernilai 0 dan 3 yang bertetangga (Conceptis puzzle 1997). .................................................. 7 9 Cell bernilai 0 dan 3 diagonal (Conceptis puzzle 1997). ................................................................ 7 10 Dua cell bernilai 3 yang bertetangga (Conceptis puzzle 1997). ................................................... 7 11 Dua cell bernilai 3 dan diagonal (Conceptis puzzle 1997). .......................................................... 7 12 Angka apapun pada pojok cell (Conceptis puzzle 1997). ............................................................ 7 13 Arsitektur sistem. ......................................................................................................................... 8 14 Diagram alur proses solver slither link. ........................................................................................ 8 15 Representasi dari fakta slither link. .............................................................................................. 8 16 Representasi status garis di sekeliling cell arc(X,Y,0,0,0,1). ........................................... 9 17 Cell dengan predikat arc(X,Y,1,0,0,0). ........................................................................... 9 18 Cell dengan predikat arc(X,Y,1,0,0,0). ........................................................................... 9 19 Cell dengan predikat arc(X,Y,0,0,1,0). ........................................................................... 9 20 Cell dengan predikat arc(X,Y,0,0,0,1). ........................................................................... 9 21 Cell dengan nilai 0. ...................................................................................................................... 9 22 Cell dengan nilai 1. .................................................................................................................... 10 23 Cell dengan nilai 2. .................................................................................................................... 10 24 Cell dengan nilai 3. .................................................................................................................... 10 25 Local loop pada cell bernilai 3. .................................................................................................. 10 26 Constraint pada posisi pojok kiri atas. ....................................................................................... 11 27 Constraint pada posisi pojok kanan atas .................................................................................... 11 28 Constraint pada posisi pojok kiri bawah. ................................................................................... 11 29 Constraint pada posisi pojok kanan bawah. ............................................................................... 11 30 Antisipasi cabang. ...................................................................................................................... 12 31 Ketersambungan dari garis. ........................................................................................................ 12 32 Local loop dengan 2 cell bernilai 3. ........................................................................................... 12 33 Cell bernilai 2 yang bersebelah dengan 0. .................................................................................. 12 34 Slither link hasil pembangkitan. ................................................................................................. 13 35 Solusi slither link........................................................................................................................ 13 36 Ilustrasi penomoran sisi pada grid.............................................................................................. 13 37 Grafik perbandingan waktu eksekusi dan ukuran slither link. ................................................... 15

v

DAFTAR LAMPIRAN Halaman 1 Program DLV, modul pembangkitan. ................................................................................................ 17 2 Program DLV, constraint cell dengan nilai 0, 1, 2, dan 3. ................................................................ 18 3 Program DLV, constraint mencegah local loop. ............................................................................... 19 4 Program DLV, constraint pada cell dengan posisi di pojok grid....................................................... 20 5 Program DLV, constraint untuk mengantisipasi cabang dan ketersambungan garis. ........................ 21 6 Program DLV, constraint dari cell bernilai 2 yang bersebelahan dengan cell bernilai 0. .................. 22 7 Pseudo code program C++ untuk membaca fakta slither link. .......................................................... 23 8 Pseudo code program C++, modul basic_rule . ................................................................................. 24 9 Pseudo code program C++, modul advance_rule . ............................................................................ 25 10 Pseudo code program C++, modul cek_garis_cell . ........................................................................ 26 11 Pseudo code program C++, modul sambung_garis dan modul cek_cabang. ................................... 27 12 Pseudo code program C++, modul cek_logic dan fungsi sambung. ................................................ 28

vi

PENDAHULUAN Latar Belakang Slither link adalah salah satu permainan kertas terkenal yang sulit untuk dipecahkan secara konvensional. Tujuan dari slither link adalah membentuk loop, yaitu sebuah putaran garis yang tidak bercabang dan kembali ke titik awal tetapi harus memenuhi aturan slither link yaitu jumlah garis yang mengelilingi cell harus sama dengan angka di dalam cell. Penyelesaian untuk persoalan ini harus melibatkan algoritme yang mencari kemungkinan semua solusi. Hal ini menyebabkan kompleksitas dari eksekusi algoritme ini akan menjadi eksponensial terhadap ukuran masukan yang diberikan. Permasalahan ini lebih dikenal sebagai Nondeterministic Polynomial-time Complete (NP-Complete). Teknik pemrograman komputer mempunyai banyak paradigma atau teknik untuk menyelesaikan sebuah masalah, pemilihan teknik pemrograman yang tepat akan memberikan cara paling efektif untuk mendapatkan solusi dari masalah ini. Salah satunya adalah teknik procedural programming. Teknik ini akan memberi sekumpulan instruksi untuk komputer berupa langkah-langkah, dan perintahnya bersifat linear untuk menyelesaikan sebuah masalah dengan menggunakan loop dan percabangan. Teknik lain yang digunakan dalam pemrograman komputer adalah logic programming yang bersifat deklaratif, teknik ini akan mengubah masalah menjadi sekumpulan fakta dan aturan. Dengan melakukan pendekatan secara logika, sebuah model penyelesaian akan menyelesaikan slither link mirip dengan logika manusia. Metode ini akan memberikan cara yang lebih efisien dalam menemukan solusi dari slither link, salah satunya adalah dengan menggunakan answer set programming. Tujuan Penelitian Tujuan dari penelitian ini adalah untuk membuat model penyelesaian game slither link menggunakan answer set programming dengan tool DLV (datalog with disjunction) dan procedural programming menggunakan C++ kemudian membandingkan kinerja dari kedua metode tersebut.

Ruang Lingkup Penelitian Ruang lingkup permasalahan pada tugas ini adalah : 1

2 3

Membuat model penyelesaian game slither link. dengan menggunakan answer set programming dan procedural programming. Ukuran pembanding adalah rata-rata waktu eksekusi dari setiap model solver. Software yang digunakan adalah PHP sebagai front end dan DLV serta C++ sebagai back end.

Manfaat Penelitian Penelitian ini diharapkan dapat menunjukkan bahwa answer set programming bisa menyelesaikan masalah game slither link NP-Complete sebagaimana procedural programming melakukannya.

TINJAUAN PUSTAKA NP-Complete Setiap masalah bisa diselesaikan dengan berbagai jenis algoritme, tapi algoritme yang disebut efisien adalah algoritme yang bisa menyelesaikan masalah dalam waktu polinomial untuk semua input. Algoritme yang disebut tidak efisien adalah algoritme yang menyelesaikan masalah dalam waktu eksponensial untuk beberapa input. Ada tiga kelas masalah yaitu P, NP, dan NPC. Kelas P (polinomial) berisi masalahmasalah yang bisa dalam waktu polinomial, sebuah fungsi f(n) dikatakan P jika f(n) = O(nk) dengan k bernilai konstan dan n adalah ukuran dari input. Contoh masalah yang bisa diselesaikan dengan waktu polinomial adalah masalah sorting, dari semua algoritme sorting kompleksitas terbaiknya untuk kasus worst case adalah O(n2) dan O(n log n) untuk kasus best case (Cormen et al. 2001). Kelas NP (non deterministic polynomial) berisi masalah-masalah yang bisa diverifikasi dalam waktu polinomial. Maksud dari kalimat tersebut adalah jika kita mempunyai kandidat solusi dari masalah NP, maka kita bisa melakukan verifikasi apakah solusi tersebut benar dalam waktu polinomial. Setiap masalah dalam P adalah NP, karena untuk setiap masalah dalam P bisa kita selesaikan dalam waktu polinomial tanpa memerlukan kandidat solusi. Contoh masalah yang masuk dalam kelas NP adalah TSP (travelling salesman problem) (Cormen et al. 2001).

1

Kelas NPC atau NP-Complete (non deterministic polynomial complete) adalah persoalan NP yang paling sulit. Sebuah masalah X dikatakan NP-Complete jika : 1 X termasuk ke dalam kelas NP. 2 Setiap persoalan di dalam NP dapat ditransformasi dalam waktu polinomial menjadi X. Jika sebuah masalah X hanya memenuhi kondisi nomor dua, maka masalah tersebut dikatakan NP-hard. Jika salah satu masalah NPComplete bisa diselesaikan dengan waktu polinomial, maka semua masalah NP-Complete bisa diselesaikan dalam waktu polinomial. Beberapa masalah NP-Complete yang terkenal adalah Hamiltonian Cycle Problem dan Subset Sum. Masalah NP-Complete pertama yang berhasil dipecahkan adalah SATISFIABILITY (SAT) oleh Stephen Cook yang disebut teorema Cook (Garey et al 1979). Semua persoalan P (polinomial) juga adalah NP (non deterministic poyinomial), P adalah himpunan bagian dari NP. Namun belum ada yang bisa membuktikan apakah masalah P ≠ NP atau P = NP sehingga P ∩ NPC = ∅ . Gambar 1 adalah ilustrasi hubungan antara P, NPC, dan NP.

Gambar 1 Hubungan antara P, NP, dan NPC (Cormen et al 2001). Logic Programming Logic (declarative) programming muncul sebagai paradigma berbeda pada tahun 1970-an, karena logic programming mengharuskan programmer untuk mendeklarasikan tujuan (goal) dari komputasi. Goal diekspresikan sebagai kumpulan dari aturan tentang hasil dan constraint (pembatas) dari komputasi. Logic programming disebut juga sebagai rule-based programming (Tucker et al 2002). Secara umum, logic programming merepresentasikan masalah dalam bentuk aturan dan fakta. Sebuah aturan ditulis sebagai : h ← p1, p2, ..., pn.

Sebagai contoh, misalnya kita mendapatkan fakta bahwa Allen dan Mary berbicara bahasa Rusia, Bob berbicara bahasa Inggris. Sedangkan aturannya adalah seseorang bisa berbicara dengan orang lain yang bernilai benar ketika mereka berbicara dalam bahasa yang sama. Maka kita bisa menulisnya sebagai fakta dan aturan berikut: speaks(allen,russian). speaks(bob,english). speaks(mary,russian). talkswith(P1, P2) :- speaks(P1,L), speaks(P2,L), P1\=P2.

Contoh eksekusi program : ?- speaks(alen,russian). true. ?- talkswith(X,allen). returns X = mary.

Answer set programming Answer set programming (ASP) adalah sebuah bentuk pemrograman berorientasi deklaratif untuk menyelesaikan masalah pencarian solusi yang sulit terutama masalah dengan kompleksitas tinggi (diatas ∑𝑃2 ) Answer Set Programming adalah pengembangan dari Logic Programming dan telah diaplikasikan di banyak bidang ilmu pengetahuan. Answer set semantics adalah salah satu formalisme yang paling populer dan semantik yang paling umum diterima dalam pemrograman logika, semantik ini mendefinisikan stable model yang memperbolehkan negasi dan disjungsi dalam aturan. Kelebihan ASP dibandingkan pemrograman berbasis Prolog adalah semantik yang jelas menjamin program bisa berhenti. Pemrograman berbasis Prolog tidak murni deklaratif karena semantik yang disediakan oleh Prolog masih bergantung pada aspek prosedural dari program, seperti urutan dari bagian body pada aturan. Penyempurnaan lain yang ditawarkan ASP adalah semantik yang jelas untuk menangani program tidak stratified yang tidak bisa dilakukan oleh Prolog. Misalnya kita mempunyai pernyataan : “jika seseorang bisa diasumsikan bukan laki-laki maka orang tersebut pasti seorang wanita”, dalam ASP pernyataan tersebut ditulis sebagai berikut : female(X) ← person(X), not male(X). male(X) ← person(X), not female(X).

Untuk setiap fakta dari person(a), answer set semantics menghitung satu himpunan jawaban (answer set) yang berisi female(a) dan satu

2

himpunan jawaban berisi male(a). Fitur penting lain dari ASP adalah kemampuannya untuk menggunakan ekspresi disjungsi (“V”) pada head dari aturan. ASP menjadi sangat deklaratif untuk berbagai masalah. Sebagai contoh, program sebelumnya bisa ditulis menggunakan satu aturan seperti berikut : female(X) V male(X) ← person(X).

Penggunaan disjungsi pada head akan meningkatkan kekuatan ekspresif dari ASP . Syntax ASP Pada Answer Set Programming terdefinisi penggunaan tiga buah simbol yaitu, predikat (p), konstanta (k), dan variabel (ν). Predikat adalah simbol yang diawali dengan huruf kecil sedangkan variabel adalah simbol yang diawali dengan huruf besar. Sebuah simbol konstanta bisa bernilai numerik. Sebuah term bisa berupa konstanta atau variabel. Dalam sebuah simbol predikat p, sebuah atom didefinisikan sebagai 𝑝 𝑡1 , … , 𝑡𝑘 dimana untuk setiap 𝑡𝑖 , 1 ≤ 𝑖 ≤ 𝑘 adalah sebuah term yang bisa berupa konstanta atau variabel, k disebut aritas dari p. Atom dengan aritas () disebut atom proporsional. Sebuah classical literal l bisa berupa sebuah atom p (positif), atau sebuah negasi atom ¬p (negatif). Dua tipe negasi dalam ASP yaitu, default negation dengan bentuk “not b” yang berarti tidak ada bukti yang menunjukkan bahwa b berniali benar maupun b bernilai salah. Explicit negation dengan bentuk “¬b” yang berarti kita mempunyai bukti bahwa b bernilai salah. Sebuah rule (r) dalam ASP mempunyai bentuk : 𝑎1 ∨ … ∨ 𝑎𝑘 ← 𝑏1 , … , 𝑏𝑚 , 𝑛𝑜𝑡 𝑐𝑚 +1 , … , 𝑛𝑜𝑡 𝑐𝑛 Himpunan dari 𝑎1 ∨ … ∨ 𝑎𝑘 adalah head dari aturan r, dinotasikan dengan 𝐻(𝑟), sedangkan himpunan dari 𝑏1 , … , 𝑏𝑚 , 𝑛𝑜𝑡 𝑐𝑚+1 , … , 𝑛𝑜𝑡 𝑐𝑛 adalah body dari r dan dinotasikan dengan 𝐵 𝑟 . Ada dua tipe body yaitu positive body literal yang dinotasikan sebagai 𝐵+ 𝑟 dimana + 𝐵 𝑟 = 𝑏1 , … , 𝑏𝑚 , dan negative body literal 𝐵 − 𝑟 dimana 𝐵 − 𝑟 = 𝑛𝑜𝑡 𝑐𝑚 +1 , … , 𝑛𝑜𝑡 𝑐𝑛 sehingga 𝐵 𝑟 = 𝐵 + 𝑟 ∪ 𝐵 − 𝑟 . Sebuah rule r tanpa head 𝑘 = 0 disebut sebagai hard constraint, sebuah rule dengan tepat satu head 𝑘 = 1 disebut sebagai normal rule, sedangkan sebuah rule dengan k > 1 disebut sebagai disjunctive rule. Jika body dari rule kosong 𝑘 = 𝑚 = 0 maka rule tersebut disebut sebagai fact atau dengan kata lain kita

tidak menggunakan tanda “←”. Sebuah rule dikatakan positif jika n = m atau dengan kata lain dalam bahasa matematika ∀ 𝑟 ∈ 𝑃 ∶ 𝐵 − 𝑟 = ∅ , dan disebut juga sebagai horn rule. Answer Set Semantics Semantics dari program P adalah program yang bebas dari variabel, maka kita harus mendefinisikan ground instantiation dari program yang akan mensubstitusi semua variabel dari program dengan konstanta. Herbrand Universe dari P (Program) atau kita sebut 𝐻𝑈𝑝 , adalah himpunan semua simbol yang dibentuk dari konstanta dalam P. Herbrand Literal Base berarti untuk setiap program P, 𝐻𝐵𝑝 adalah himpunan dari semua ground (classical) literal yang dibangun dari simbol predikat yang muncul pada P dan konstanta dari 𝐻𝑈𝑝 . Ground Instantiation berarti untuk setiap rule r, Ground(r) menotasikan himpunan rule yang didapatkan dengan mengganti setiap variabel yang muncul di r dengan simbol konstanta dalam 𝐻𝑈𝑝 . Dinotasikan dengan Ground(P) yaitu himpunan dari semua ground instances dari rule pada P. Semantics dari program P didefinisikan dengan mencari positive ground program. Sebuah interpretasi I adalah subset dari 𝐻𝐵𝑝 . Sebuah himpunan dari literals S memenuhi sebuah rule r jika dan hanya jika 𝐻 𝑟 𝑆 ≠ ∅ kapanpun 𝐵 + 𝑟 ⊆ 𝑆 dan 𝐵 − 𝑟 ∩ 𝑆 = ∅ . Himpunan dari literal S memenuhi sebuah program P jika memenuhi seluruh rule pada P. Sebuah model dari program P adalah sebuah interpretasi 𝐼 ⊆ 𝐻𝐵𝑝 dimana I harus memenuhi P. Sebuah answer set dari ground program yang positif adalah model minimal dari P. Hasil reduksi atau Gelfond-Lifschitz transform (GL-transform) adalah program ground positive yang didapatkan dari Ground(P) dengan cara : 1 Menghapus semua rule r ∈ Ground(P) sehingga 𝐵 − 𝑟 ∩ 𝐼 ≠ ∅. 2 Menghapus literal body negatif dari rule yang tersisa. Sebuah answer set dari sebuah program P adalah sebuah interpretasi 𝐼 ⊆ 𝐻𝐵𝑝 sehingga I adalah answer set dari P. Program P dikatakan konsisten jika memiliki minimal satu buah answer set (ANS(P) ≠ ∅). Sebuah ground classical literal a dikatakan bravely true jika

3

ada minimal satu answer set A ∈ ANS(P), dimana 𝑎 ∈ 𝐴 . Sedangkan sebuah ground classical literal a dikatakan cautiously true jika setiap answer set A ∈ ANS(P), dimana 𝑎 ∈ 𝐴. Jika terjadi kasus spesial dimana program P definite-horn, dalam kasus ini P memiliki tepat satu answer set dan dinotasikan dengan Tp atau immediate consequence (Gelfond et al 1991). Berdasarkan answer set semantics , maka terdefinisi reasoning task sebagai berikut : 1 Answer set existence, buktikan program P memiliki paling sedikit satu buah answer set (selain itu maka program dikatakan tidak konsisten). 2 Brave reasoning, diberikan program P dan sebuah atom a maka buktikan apakah a benar pada minimal satu answer set P. 3 Cautious reasoning, diberikan program P dan sebuah atom a maka buktikan apakah a benar dalam semua answer set P. 4 Generate all answer sets, diberikan program P maka hitung semua answer sets A ∈ ANS(P). DLV (datalog with disjunction) Untuk melakukan implementasi answer set programming para peneliti membuat ASP solver untuk mengevaluasi dan menampilkan answer set, beberapa ASP solver yang terkenal adalah DLV, clasp/claspD, SMODELS, dan ASSAT. ASP solver yang digunakan untuk menyelesaikan masalah slither link adalah DLV (datalog with disjunction). DLV dikembangkan oleh University of Calabria dan Vienna Technical University. DLV adalah alat untuk mengkomputasi answer set yang mengimplemtasikan pemrograman logika disjungsi dengan menggunakan semantik answer set (Gelfond et al 1991). Disjunctive datalog memperbolehkan ekspresi logika OR (disjungsi) muncul didalam aturan. Kelebihan dari DLV adalah komputasinya sound and complete, sound adalah solusi yang dihasikan merupakan jawaban dari masalah dan complete adalah semua solusi harus muncul. Struktur dari DLV adalah :  Rule : 𝑎1 ∨ … ∨ 𝑎𝑛 ∶ − 𝑏1 , … , 𝑏𝑘 , 𝑛𝑜𝑡 𝑏𝑘+1 , … , 𝑛𝑜𝑡 𝑏𝑚 .  Constraint : : − 𝑏1 , … , 𝑏𝑘 , 𝑛𝑜𝑡 𝑏𝑘+1 , … , 𝑛𝑜𝑡 𝑏𝑚 .  Program : Sebuah himpunan terbatas P yang terdiri atas rules dan constraints.

Dengan mengikuti paradigma Guess/Check/Optimize (GCO) masalah dengan kompleksitas tinggi bisa diselesaikan. GCO untuk program P akan terdiri atas tiga bagian berikut : 1 Bagian Guessing. Bagian guessing akan mendefinisikan search space (ruang pencarian) yang merepresentasikan kandidat solusi. Pada bagian ini kita berusaha menebak semua solusi yang mungkin muncul. 2 Bagian Checking. Bagian ini bersifat opsional yang akan memfilter kandidat solusi sedemikian rupa sehingga answer sets dari P akan merepresentasikan solusi yang bisa diterima untuk instance masalah. Pada bagian ini kita menuliskan constraint agar solusi yang muncul hanya solusi yang diinginkan. 3 Bagian optimization. Bagian ini memungkinkan untuk mengekspresikan evaluasi bobot kuantitatif dari solusi dengan menggunakan weak constraint. Misalnya kita akan memodelkan bahwa setiap kali seseorang memberitahu kita sebuah lelucon, maka kita tertawa. Hal ini bisa dilakukan dengan cara berikut : joke. laugh :- joke.

Baris pertama adalah fakta dan mengekspresikan bahwa joke adalah benar. Baris kedua adalah aturan, ini dibaca sebagai “ jika lelucon adalah benar, maka tertawa juga harus benar”. (tanda “:-“ berarti sebuah panah ke kiri, pemrograman logika mengartikannya sebagai implikasi). Salah satu masalah NP-Complete yang terkenal adalah Graph 3-Colorability (Garey et al 1979). Diberikan (undirected) graf G ={V,E}, putuskan bagaimana memberi warna pada setiap node dalam graf dengan salah satu dari tiga warna yang didefinisikan dimana tidak boleh ada dua node yang bertetangga mempunyai warna yang sama. Kasus graph coloring dengan tujuh node dan 3 warna ditunjukkan pada Gambar 2 :

4

Minnesota

Iowa

Wisconsin

Illinois

indiana

Michigan

Ohio

Nomor didalam cell slither link yang belum terselesaikan dipilih sedemikian sehingga mempunyai solusi yang unik, Gambar 3 adalah contoh masalah slither link dan penyelesaiannya :

Gambar 2 Graf tujuh kota. % aturan pewarnaan (guess) col(Country, red) v col(Country,green) v col(Country, blue) :- node(Country). % periksa warna yg incident(check) :- arc(Country1, Country2), col(Country1, CommonColor), col(Country2, CommonColor).

DLV akan menghasilkan enam solusi, dan semua solusi memenuhi ketentuan graph coloring (graf tiga warna). Berikut adalah salah satu solusi yang dihasilkan : {col(minnesota,green), col(wisconsin,red), col(illinois,green), col(iowa,blue), col(indiana,red), col(michigan,blue), col(ohio,green) }

Slither link Slither link ditemukan tahun 1989 oleh perusahaan puzzle jepang Nikoli, slither link juga dikenal sebagai Fences and Loop the Loop dan Dotty Dilemma. Slither link dimainkan dalam grid empat persegi panjang dengan beberapa nomor terisi didalam grid (tidak semua terisi). Masalah slither link telah terbukti NP-Complete (Yato 2003) sehingga bisa ditangani oleh answer set programming.

Gambar 3 Masalah slither link dan solusinya (Yato 2003).

METODOLOGI Formulasi aturan pembangkitan slither link Aturan-aturan yang berlaku dalam pembangkitan slither link dikumpulkan. Aturanaturan tersebut diformulasikan ke dalam bahasa logika answer set programming. Untuk pembangkitan slither link secara acak langkahlangkah yang harus dilakukan adalah (Wan 2009) : 1 Mengisi grid dengan sembarang loop. 2 Secara acak hapus nomor di dalam cell satu per satu. 3 Periksa apakah slither link masih bisa menghasilkan solusi yang unik. 4 Hapus semua edge. 5 Tampilkan hasil pada pengguna.

Tingkat kesulitan dari slither link didefinisikan berdasarkan luas persegi atau papan permainannya dan angka yang terisi di dalam grid. Aturan dari slither link adalah sebagai berikut :

Slither link yang dibangkitkan harus secara acak. Ketika menghapus nomor di dalam cell, algoritme pembangkitan harus memastikan bahwa slither link yang dihasilkan bisa diselesaikan menggunakan aturan logika. Proses ini dikerjakan oleh modul back end dan ditunjukkan pada Gambar 4.

1 Setiap masalah di representasikan dalam grid empat persegi panjang. Panjang dari persegi tersebut menunjukkan ukuran dari masalah. 2 Sebuah 1 x1 persegi dikelilingi oleh empat titik yang disebut cell. Sebuah cell bisa mempunyai nomor antara null, 0, 1, 2, atau 3. 3 Tujuan dari permainan adalah membuat loop yang tidak memotong atau bercabang dengan menghubungkan titik-titik yang bertetangga dengan garis, sehingga sebuah nomor dalam cell nilainya sama dengan jumlah garis yang mengelilingi cell tersebut.

Gambar 4 Formulasi pembangkitan.

5

Tingkat kesulitan puzzle

Slither link yang ingin dibangkitkan adalah slither link yang berada di tengah pada grafik perbandingan antara tingkat kesulitan puzzle dan jumlah constraint pada puzzle seperti ditunjukkan pada Gambar 5 berikut :

Constraint puzzle

Gambar 5 Grafik tingkat kesulitan puzzle berbanding dengan constraint puzzle. Gambar 5 bermakna bahwa slither link yang optimal adalah yang memiliki jumlah constraint yang tidak terlalu sedikit dan tidak terlalu banyak sehingga solusi yang dihasilkan unik dan sulit ditemukan, tetapi jika constraint sedikit maka solusi dari slither link kemungkinan banyak, dan sebaliknya jika constraint terlalu banyak maka kemungkinan slither link tidak mempunyai solusi. Untuk mendapatkan slither link dengan jumlah constraint yang tepat sangat sulit. Formulasi aturan penyelesaian Solusi yang dihasilkan akan dimodelkan sebagai graf yang mempunyai loop di dalam grid yang memenuhi aturan slither link. Maksud dari pernyataan tersebut adalah graf yang dihasilkan adalah solusi dari slither link dimana dalam setiap cell yang terdapat angka di dalamnya maka jumlah edge yang mengelilingi cell tersebut harus sesuai dengan angka di dalam cell tersebut. Dengan paradigma Guess and Check maka : 1 Guess Akan ditebak semua kemungkinan graf (kandidat solusi) yang akan muncul dalam slither link, semua graf yang muncul adalah graf yang mempunyai loop atau cycle. 2 Check Kandidat solusi yang dibangkitkan oleh prosedur guess diperiksa kembali dengan constraint yang ditentukan sehingga didapatkan solusi yang memenuhi aturan slither link.

Gambar 6 Formulasi Penyelesaian. Cara termudah untuk menyelesaikan slither link adalah mengeliminasi garis dimana garis tersebut tidak seharusnya berada, cara ini dilakukan dengan memberikan nilai 0 untuk garis tersebut. Misalnya sebuah cell dengan nilai 0 tidak boleh mempunyai garis di sekelilingnya, maka semua garis yang mengelilingi cell tersebut harus dieliminasi. Petunjuk-petunjuk tersebut direpresentasikan dalam bentuk rule, dan berikut adalah petunjuk atau teknik untuk membantu menyelesaikan masalah slither link : 1 Tidak boleh ada garis di sekeliling cell dengan nilai 0. Perhatikan angka 0 pada contoh berikut, angka 0 berarti sebuah cell tidak boleh dikelilingi oleh garis maka berikan tanda X pada keempat sisinya untuk menandakan bahwa tidak boleh ada garis pada posisi tersebut.

Gambar 7 Cell dengan nilai 0 (Conceptis puzzle 1997). 2 Cell dengan nilai 0 dan 3 yang bertetangga. Contoh berikut menggambarkan cell dengan angka 3 yang berada di bawah cell dengan angka 0. Garis diatas cell yang bernilai 3 diberi tanda X maka hanya ada satu cara untuk menyelesaikan garis di sekeliling cell dengan nilai 3 yaitu pada kiri, bawah, dan kanan cell tersebut.

6

Gambar 8 Cell bernilai 0 dan 3 yang bertetangga (Conceptis puzzle 1997). 3 Cell dengan nilai 0 dan 3 dengan posisi diagonal. Pada Gambar 9 bagian kiri diilustrasikan dua buah skenario jika terjadi diagonal antara 0 dan 3 dengan garis keabuan, berdasarkan fakta tersebut maka gambar di sebelah kanan pada Gambar 9 menggambarkan petunjuk ketika terjadi skenario ini.

Gambar 9 Cell bernilai 0 dan 3 diagonal (Conceptis puzzle 1997). 4 Cell dengan nilai 3 yang bertetangga. Hanya ada dua solusi yang mungkin untuk skenario ini dan digambarkan pada Gambar 10 bagian kiri dengan garis keabuan. Berdasarkan fakta tersebut maka Gambar 10 bagian kanan menggambarkan petunjuk yang harus dilakukan jika skenario ini terjadi.

Gambar 11 Dua cell bernilai 3 dan diagonal (Conceptis puzzle 1997). 6 Angka apapun pada pojok grid. Cell yang terletak di pojok grid memiliki karakteristik khusus untuk angka berapapun yang dimilikinya. Angka 0 sudah dijelaskan pada teknik pertama, angka 1 akan mengugurkan dua sisi pada pojok cell karena tidak mungkin sebuah garis akan terbentang pada posisi tersebut, maka berikan tanda X pada dua sisi tersebut. Angka 2 memiliki dua solusi yang mungkin tetapi kedua solusi tersebut pasti memiliki awal garis yang sama dan digambarkan pada gambar di kanan. Angka 3 pada pojok grid memiliki dua solusi yang mungkin, dan garis merah menggambarkan garis yang pasti terbentang untuk angka 3 pada pojok grid.

Gambar 12 Angka apapun pada pojok cell (Conceptis puzzle 1997). Pembangunan front end Modul front end akan dibangun menggunakan PHP dan JavaScript yang berfungsi sebagai GUI (graphical user interface) dan memperlihatkan slither link yang dibangkitkan serta solusinya.

Gambar 10 Dua cell bernilai 3 yang bertetangga (Conceptis puzzle 1997). 5 Cell dengan dua nilai 3 yang diagonal. Ada dua kemungkinan solusi untuk menangani skenario ini, salah satunya ditunjukkan pada Gambar 11 bagian kiri. Berdasarkan fakta tersebut maka ada empat garis yang pasti ada jika skenario ini terjadi, dan digambarkan pada Gambar 11 bagian kanan dengan warna merah. Untuk mencegah percabangan, berikan tanda X pada empat sisi lain.

7

Arsitektur sistem Backend Identifikasi aturanaturan pembangkitan slither link

Pembangkitan slither link

Domain masalah dalam DLV

Front End

Solusi untuk masalah slither link adalah membuat loop sedemikian sehingga loop yang dihasilkan memenuhi kondisi nilai yang terdapat pada cell dalam grid, arti kata memenuhi adalah garis jumlah garis yang mengelilingi cell harus memiliki jumlah yang sama dengan angka yang terdapat di dalam cell.

GUI

Parser

Backend

Penyelesaian Slither link

solusi yang diinginkan ke dalam bahasa logika DLV menggunakan paradigma GCO (guess / check / optimize) agar solver bisa menyelesaikannya. Sebagai perbandingan dibuat juga model penyelesaian slither link dengan menggunakan procedural programming dengan software C++, kedua metode ini akan dibandingkan rata-rata waktu eksekusinya.

Identifikasi aturanaturan penyelesaian slither link

Gambar 13 Arsitektur sistem. Arsitektur sistem ini terdiri atas tiga bagian yaitu, modul back end, modul front end, dan modul parser. Pada bagian back end akan di kerjakan oleh DLV dan C++, bagian ini adalah bagian utama yang menangani pembangkitan dan penyelesaian slither link dengan answer set programming maupun dengan procedural programming. Kemudian bagian parser adalah bagian penghubung yang bertugas sebagai modul penerjemah. Gambar 14 menggambarkan sebuah diagram alur tentang bagaimana sebuah solver slither link bekerja menghasilkan solusi.

Sebuah cell dalam slither link direpresentasikan dengan predikat C(X,Y,N) yang memiliki tiga argumen yaitu, X dan Y yang berarti koordinat cell dalam grid (X koordinat vertikal dan Y koordinat horizontal) , dan N yang berarti angka yang terdapat di dalam cell. N bisa bernilai 0, 1, 2, 3, atau null. Himpunan dari predikat C disebut sebagai fakta atau deskripsi dari masalah slither link yang akan diselesaikan, seperti pernyataan berikut mengilustrasikan fakta untuk slither link dengan ukuran 3x3. C(1,1,null). C(1,2,null). C(1,3,2). C(2,1,1). C(2,2,0). C(2,3,3). C(3,1,2). C(3,2,null). C(3,3,null).

Fakta tersebut adalah representasi dari Gambar 15:

Gambar 15 Representasi dari fakta slither link. Gambar 14 Diagram alur proses solver slither link.

HASIL DAN PEMBAHASAN Masalah slitherlink diselesaikan dengan metodologi pemrograman deklaratif dengan terlebih dahulu mendeskripsikan masalah, kemudian melakukan proses encoding kondisi

Predikat arc(X,Y,A,B,C,D) memiliki enam argumen didalamnya yang merepresentasikan posisi cell dan status garisgaris di sekeliling cell, dimana X dan Y merepresentasikan posisi cell (X koordinat vertikal dan Y koordinat horizontal), sedangkan A, B, C, dan D merepresentasikan nilai atau status dari garis di sekeliling cell. Jika bernilai 0 maka tidak ada garis terbentang pada posisi

8

tersebut, dan jika bernilai 1 maka ada garis terbentang di posisi tersebut. A berposisi di atas cell, B berposisi di sebelah kanan cell , C berposisi di bagian bawah cell, dan D berposisi di sebelah kiri cell seperti ditunjukkan pada Gambar 16.

Gambar

18

Cell

dengan

predikat

arc(X,Y,1,0,0,0).

3 arc(X,Y,0,0,1,0)

Gambar Gambar

16

Representasi sekeliling

status

garis

di cell

19

Cell

dengan

predikat

arc(X,Y,0,0,1,0).

4 arc(X,Y,0,0,0,1)

arc(X,Y,0,0,0,1).

Encoding dengan DLV Sebelumnya pada bagian metodologi telah dijelaskan mengenai beberapa teknik atau petunjuk cara menyelesaikan slither link, teknik itulah yang akan diterjemahkan ke bahasa logika secara deklaratif menggunakan paradigma GC (guess, check). Langkah pertama yang dilakukan adalah mendefinisikan ruang pencarian yaitu bagian guess pada program, pada bagian ini terdapat empat aturan disjungsi yang mendefinisikan ruang pencarian dari masalah yaitu cell dengan nilai 0, 1, 2, 3, dan null dijelaskan pada Lampiran 1. Misalnya untuk cell dengan nilai 1 maka cell tersebut mempunyai empat kemungkinan solusi untuk dibangkitkan. Kode program berikut menggambarkan bagaimana sebuah cell bernilai 1 dibangkitkan kemungkinan solusinya. arc(X,Y,1,0,0,0) v arc(X,Y,0,1,0,0) v arc(X,Y,0,0,1,0) v arc(X,Y,0,0,0,1) :C(X,Y,1).

Berikut adalah representasi bentuk cell dari solusi yang telah dibangkitkan :

Gambar

20

Cell

dengan

predikat

arc(X,Y,0,0,0,1).

Kemudian langkah selanjutnya adalah mendefinisikan constraint atau aturan yang akan menghapus calon answer set yang tidak memenuhi syarat, bagian ini masuk ke dalam metode check. Constraint dari program adalah : 1 Cell dengan nilai 0 (lihat Lampiran 2). Sebuah cell dengan nilai 0 tidak boleh memiliki garis yang mengelilinginya, dan hal tersebut berakibat juga pada cell disebelah kiri atau kanan maupun pada atas dan bawah cell dengan nilai 0 tersebut. Dengan bahasa logika aturan ini diterjemahkan menjadi : :- arc(X,Y,0,0,0,0), arc(A,Y,_,_,1,_), X=A+1.

Answer set yang tidak akan tereliminasi adalah sebagai berikut :

1 arc(X,Y,1,0,0,0)

Gambar 21 Cell dengan nilai 0. Gambar

17

Cell

predikat arc(X,Y,1,0,0,0).

2 arc(X,Y,0,1,0,0)

dengan

2 Cell dengan nilai 1 (lihat Lampiran 2). Sebuah cell dengan nilai 1 akan mempengaruhi jumlah garis yang mengelilingi tetangganya karena hanya boleh ada satu sisi yang bernilai 1. Misalnya cell yang bernilai 1 mempunyai garis pada posisi B maka tetangganya di sebelah kanan harus memiliki nilai 1 juga tetapi pada garis

9

di posisi D selain itu maka hapus kandidat tersebut. Aturan ini diterjemahkan menjadi :

pada posisi A, B, dan C maka tetangga yang berada di atas cell tersebut harus memiliki nilai 1 pada sisi di posisi C, begitu juga dengan tetangga yang berada di sebelah kanan yang harus memiliki nilai 1 pada sisi di posisi D, dan tetangga yang berada di bawah harus memiliki nilai 1 pada sisi di posisi A. Skenario tersebut digambarkan oleh constraint berikut :

:- arc(X,Y,0,1,0,0), arc(X,B,_,_,_,0), B=Y+1.

Tanda “_” adalah anonymous variable yang bermakna bahwa argumen ini bisa dihiraukan atau berapapun nilainya tidak mempengaruhi rule. Answer set yang tidak akan tereliminasi adalah sebagai berikut :

:- arc(X,Y,1,1,1,0), arc(X,B,_,_,_,0), B=Y+1. :- arc(X,Y,1,1,1,0), arc(A,Y,_,_,0,_), X=A+1. :- arc(X,Y,1,1,1,0), arc(A,Y,0,_,_,_), A=X+1.

Gambar 22 Cell dengan nilai 1. 3

Cell dengan nilai 2 (lihat Lampiran 2). Serupa dengan aturan sebelumnya dimana aturan ini akan mempengaruhi jumlah garis yang mengelilingi tetangganya, karena nilai dari cell ini adalah 2 maka ada dua garis yang harus bernilai 1 dan dua garis lainnya bernilai 0, begitu juga pada dua buah cell tetangga dari cell ini. Misalnya cell yang bernilai 2 memiliki garis pada posisi A dan B maka tetangga yang berada di atas harus memiliki nilai 1 pada sisi di posisi C dan tetangga di sebelah kanan harus memiliki nilai 1 pada sisi di posisi D, jika menyalahi aturan ini maka eliminasi answer set tersebut. Aturan ini diterjemahkan menjadi . :- arc(X,Y,1,1,0,0), arc(X,B,_,_,_,0), B=Y+1. :- arc(X,Y,1,1,0,0), arc(A,Y,_,_,0,_), X=A+1.

Constraint pertama merepresentasikan cell di sebelah kanan cell yang bernilai 2, dan constraint kedua merepresentasikan cell di atas cell bernilai 2. Answer set yang tidak akan tereliminasi adalah sebagai berikut :


Cell dengan nilai 3 (lihat Lampiran 2). Cell dengan tipe seperti ini adalah kebalikan dari cell dengan nilai 1, jika pada cell dengan nilai 1 memiliki tiga garis dengan nilai 0 maka cell dengan nilai 3 memiliki tiga garis dengan nilai 1 dan satu garis lainnya bernilai 0. Cell dengan tipe ini mengharuskan tiga tetangganya memiliki nilai 1 pada sis yang bertetangga, dan satu tetangganya memiliki nilai 0 pada sisi yang bertetangga. Misalnya sebuah cell dengan nilai 3 memiliki garis

Answer set yang tidak akan tereliminasi adalah sebagai berikut :


Mencegah local loop (lihat Lampiran 3). Untuk mencegah local loop yaitu loop yang terjadi pada satu buah cell atau dengan kata lain cell tersebut mempunyai nilai 4 yang tidak diperbolehkan dalam aturan slither link maka eliminasi answer set dimana sebuah cell yang sudah memiliki tiga sisi bernilai 1 dan sisi lainnya bernilai 0 tetapi sisi bernilai 0 tersebut ternyata bernilai 1 pada tetangganya sehingga mengakibatkan local loop. Local loop hanya mungkin terjadi pada cell yang mempunyai tiga sisi yang bernilai 1, untuk mencegah hal ini maka definisikan constraint berikut : :- arc(X,Y,1,1,1,0), arc(X,B,_,1,_,_), Y = :- arc(X,Y,0,1,1,1), arc(A,Y,_,_,1,_), X = :- arc(X,Y,1,0,1,1), arc(X,B,_,_,_,1), B = :- arc(X,Y,1,1,0,1), arc(A,Y,1,_,_,_), A =

B+1. A+1. Y+1. X+1.

Gambar 25 mengilustrasikan salah satu answer set yang akan dieliminasi oleh constraint di atas.

Gambar 25 Local loop pada cell bernilai 3.

10

6

Constraint pada cell dengan posisi X = 1 dan Y =1 (1,1). Constraint ini akan sangat membantu menyelesaikan slither link, karena kesalahan menempatkan garis pada cell di posisi ini akan mengakibatkan jalan buntu pada solusi dan akan langsung terlihat tanpa perlu menunggu cell lain terbuka garisnya (lihat Lampiran 4). Sebagai contoh jika cell memiliki nilai 1 maka kandidat solusi yang akan gugur adalah jika cell tersebut memiliki sisi yang bernilai 1 pada posisi A atau D karena hal tersebut akan mengakibatkan jalan buntu atau garis berhenti pada posisi itu, untuk mencegah hal ini maka didefinisikan constraint berikut :

mempunyai nilai 1 maka kandidat solusi yang akan gugur adalah yang mempunyai sisi bernilai 1 pada posisi D atau C. Constraint berikut mendefinisikan aturan tersebut dalam bahasa logika.

:- arc(1,1,1,0,0,0). :- arc(1,1,0,0,0,1).

Gambar 28 Constraint pada posisi pojok kiri bawah.

Constraint tersebut akan mengeliminasi calon answer set berikut :

Gambar 26 Constraint pada posisi pojok kiri atas. 7

Constraint pada cell dengan posisi (1, #maxint), #maxint adalah ukuran dari slither link sehingga cell tersebut terletak pada pojok kanan atas (lihat Lampiran 4). Sebagai ilustrasi jika cell pada posisi ini memiliki nilai 1, maka kandidat solusi yang akan gugur adalah jika cell tersebut memiliki sisi di posisi A atau B yang bernilai 1. Hal tersebut akan mengakibatkan terjadinya jalan buntu, atau garis tidak bisa menyambung dengan garis selanjutnya. Hal tersebut dicegah oleh constraint berikut : :- arc(1,#maxint,1,0,0,0). :- arc(1,#maxint,0,1,0,0).


Gambar 27 Constraint pada posisi pojok kanan atas 8

Constraint pada cell dengan posisi (#maxint ,1), #maxint adalah ukuran dari slither link. Cell dengan posisi ini terletak pada pojok kiri bawah dari grid (lihat Lampiran 4). Sebagai ilustrasi jika cell ini

:- arc(#maxint,1,0,0,0,1). :- arc(#maxint,1,0,0,1,0).


9

Constraint pada cell dengan posisi (#maxint, #maxint), #maxint adalah ukuran dari slither link sehingga cell tersebut terletak pada pojok kanan bawah dari grid (lihat Lampiran 4). Sebagai ilustrasi jika cell pada posisi ini memiliki nilai 1, maka kandidat solusi yang akan tereliminasi adalah jika cell tersebut memiliki sisi yang berposisi di B atau C yang bernilai 1. Untuk mengeliminasi kondisi tersebut maka constraint berikut harus didefinisikan : :- arc(#maxint,#maxint,0,1,0,0). :- arc(#maxint,#maxint,0,0,1,0).


Gambar 29 Constraint pada posisi pojok kanan bawah. 10 Antisipasi cabang (lihat Lampiran 5). Cabang akan mengacaukan loop yang dihasilkan, solusi dari slither link adalah sebuah loop maka solusi tersebut tidak boleh mempunyai cabang. Constraint ini akan mengeliminasi kandidat solusi yang mengakibatkan cabang, seperti jika sebuah cell mempunyai nilai 2 dan sisi yang bernilai 1 adalah A dan B maka cell di kanan atas dari cell tersebut tidak boleh memiliki nilai 1 pada sisi yang berposisi di D atau nilai 1 pada sisi yang berposisi di C. Hal seperti ini ditangani oleh constraint berikut : :- arc(X,Y,1,1,_,_), arc(A,B,_,_,1,_), X=A+1, B=Y+1.

11

:- arc(X,Y,1,1,_,_), arc(A,B,_,_,_,1), X=A+1, B=Y+1.



Gambar 32 Local loop dengan 2 cell bernilai 3. Gambar 30 Antisipasi cabang. 11 Ketersambungan dari garis (lihat Lampiran 5). Himpunan garis penyusun loop tidak boleh terputus, maka sangat penting untuk memeriksa apakah antar himpunan garis penyusun loop merupakan sebuah rangkaian yang tersambung. Ilustrasi dari skenario ini adalah jika sebuah cell di sembarang posisi memiliki nilai 1 pada sisi di posisi A dan nilai 0 pada posisi D tanpa memperhatikan nilai dari posisi B dan C, maka ke arah kiri satu-satunya cara agar garis tersambung adalah dengan memperhatikan tetangga sebelah kiri atas apakah cell tersebut memiliki nilai 1 pada salah satu sisi dari B atau C. Jika tidak memenuhi kondisi ini maka eliminasi kandidat solusi tersebut, skenario tersebut digambarkan dalam constraint berikut : :- arc(X,Y,1,_,_,0), arc(A,B,_,M,N,_), M=N, X=A+1, Y=B+1.


13 Cell bernilai 2 yang bersebelahan dengan cell bernilai 0 pada bagian atas, bawah, kiri, serta kanan dari grid (lihat Lampiran 6). Terdapat dua tipe kandidat solusi yang akan gugur jika skenario ini terjadi yaitu cell yang memiliki nilai 1 pada sisi A dan C serta cell yang memiliki nilai 1 pada sisi B dan D karena pada salah satu sisi akan terjadi jalan buntu atau garis tidak bisa melanjutkan sehingga loop tidak terjadi. salah satu constraint yang digunakan adalah sebagai berikut : :- arc(#maxint,Y,1,0,1,0), arc(#maxint,B,0,0,0,0), Y=B+1.


Gambar 33 Cell bernilai 2 yang bersebelah dengan 0. Bagian constraint yang telah dijelaskan sebelumnya akan mengeliminasi kandidat solusi yang tidak memenuhi aturan slither link sehingga answer set yang didapatkan merupakan solusi yang diharapkan. Menjalankan model penyelesaian slither link

Gambar 31 Ketersambungan dari garis. 12 Local loop dari cell dengan nilai 3 yang bersebelahan (lihat Lampiran 3). Jika terdapat dua buah cell dengan nilai 3 yang bersebelahan baik di kiri dan kanan maupun pada atas dan bawah, ada kemungkinan konfigurasi keduanya membentuk local loop sehingga menyalahi aturan dari slither link. Yang dimaksud local loop pada skenario ini adalah loop yang terjadi antara dua cell yang memiliki nilai 3 tersebut, salah satu constraint yang digunakan adalah sebagai berikut :

Fakta dari slither link yang telah dibangkitkan disimpan dalam file bernama soal.dat dan program DLV untuk penyelesaian slither link disimpan dalam file bernama slither.txt. Pemisahan file antara fakta dan program disebabkan karena fakta yang akan selalu berubah seiring dengan slither link yang dibangkitkan. Berikut akan diberikan ilustrasi bagaimana sebuah slither link diselesaikan menggunakan program DLV. Misalnya telah dibangkitkan sebuah slither link dengan ukuran 3x3 dan memiliki fakta sebagai berikut :

:- arc(X,Y,1,1,0,1), arc(A,Y,0,1,1,1), A=X+1.

12

dalam file ukuran.dat dan data.dat dengan format sebagai berikut : /// ** data.dat **// 𝑁1 𝑁2 ...... 𝑁𝑘

Gambar 34 Slither link hasil pembangkitan. C(1,1,null). C(1,2,1). C(1,3,null). C(2,1,null). C(2,2,null). C(2,3,1). C(3,1,1). C(3,2,null). C(3,3,2).

Kemudian fakta ini akan diproses bersama dengan model penyelesaian slither link oleh DLV, sehingga menghasilkan answer set yang merupakan solusi. D:\DLV>dlv.mingw.exe -nofacts -silent soal.dat slither.txt -N=3 {arc(1,2,1,0,0,0), arc(2,3,0,1,0,0), arc(3,1,0,1,0,0), arc(3,3,0,1,1,0), arc(1,1 ,1,0,1,1), arc(1,3,1,1,0,0), arc(2,1,1,1,0,0), arc(2,2,0,0,0,1), arc(3,2,0,0,1,1 )}

Solusi tersebut harus diterjemahkan kembali menjadi sebuah slither link kembali, maka jika answer set tersebut diterjemahkan menjadi sebuah slither link seperti ditunjukkan Gambar 35.

Gambar 35 Solusi slither link. Implementasi Programming

dengan

Procedural

Pada bagian metodologi telah ditunjukkan bahwa slither link mempunyai petunjukpetunjuk yang bisa digunakan untuk menyelesaikan masalah. Petunjuk-petunjuk ini yang akan digunakan dalam membuat program ini. Program penyelesaian slither link menggunakan C++ ini terdiri atas enam modul dan satu fungsi. Struktur data Fakta tentang ukuran slither link dan nilai– nilai dalam cell yang dibangkitkan disimpan

Dimana 𝑁𝑖 adalah nilai di dalam cell, dan k adalah jumlah cell dalam grid atau sebanyak ukuran grid dikuadratkan. Kemudian fakta ini akan dibaca oleh program sebagai array yang berukuran k.Kemudian setiap sisi pada grid diberi nilai default 3 yang berarti statusnya belum diketahui (lihat Lampiran 7), jika bernilai 0 berarti tidak boleh ada garis pada sisi tersebut dan jika bernilai 1 maka ada garis pada sisi tersebut. Representasi posisi garis pada slither link digambarkan pada Gambar 36 :

Gambar 36 Ilustrasi penomoran sisi pada grid. Modul pertama bernama basic_rule, modul ini akan mengaplikasian teknik-teknik dasar penyelesaian slither link salah satunya adalah jika terdapat cell dengan angka 0 maka sisi-sisi yang yang dipengaruhi akan diberi nilai 0 dan beberapa teknik lain seperti telah dijelaskan sebelumnya pada bagian metodologi. Pseudo code modul dapat dilihat pada Lampiran 8. Modul kedua bernama advance_rule, modul ini akan mencari kemungkinan terbukanya nilai dari sisi-sisi pada cell di posisi samping kiri, kanan, atas, dan bawah dengan melihat tetangganya. Misalnya pada cell dengan posisi di atas (i ≤ ukuran) dan cell tersebut bernilai 3 maka dengan melihat cell di sebelah kirinya diketahui bahwa sisi atas dari cell tersebut bernilai 0, kemudian program langsung memberi nilai 1 pada sisi atas dan kiri di cell yang bernilai 3. Pseudo code modul dapat dilihat pada Lampiran 9. Modul ketiga bernama cek_garis_cell, modul ini akan memberikan nilai 1 atau 0 pada sisi-sisi cell yang sudah dipastikan bahwa pemberian nilai tersebut akan membuat jumlah garis yang mengelilingi cell sesuai dengan nilai di dalamnya. Pseudo code modul dapat dilihat pada Lampiran 10.

13

Modul keempat bernama sambung_garis, modul ini akan menyambungkan sisi dari cell yang tidak mungkin bercabang lagi, dan tersisa satu kemungkinan arah menuju garis selanjutnya. Misalnya pada sisi atas cell ke arah kanan mempunyai tiga kemungkinan cabang yaitu ke atas, ke samping, dan ke bawah. Jika dua dari cabang tersebut bernilai 0 maka bisa dipastikan garis tersebut mengarah ke cabang yg tidak bernilai 0. Pseudo code modul dapat dilihat pada Lampiran 11. Modul kelima bernama cek_cabang , modul ini akan memberi tanda berupa nilai 0 pada sisi yang berpotensi menjadi cabang, dan mengembalikan status dari setiap sisi pada grid. modul ini hanya mengubah nilai dari sisi yang masih bernilai 3 dan berpotensi menjadi cabang. Pseudo code modul dapat dilihat pada Lampiran 11. Modul keenam bernama cek_logic, modul ini akan memeriksa cell yang mempunyai nilai null dan sudah bisa ditebak kemungkinan solusinya dengan memeriksa tetangganya. Cell yang diperiksa hanya yang berada pada posisi tertentu yang bisa ditebak secara pasti kemungkinan solusinya. Pseudo code modul dapat dilihat pada Lampiran 12. Program ini memiliki satu buah fungsi dengan nama sambung. Fungsi ini akan melakukan perjalanan dari sisi yang pertama kali ditemui dan bernilai 1 dan kembali ke sisi tersebut sehingga perjalanan tersebut berupa sebuah loop yang memenuhi aturan slither link yaitu jumlah garis yang mengelilingi sebuah cell sesuai dengan nilai di dalam cell. Perjalanan akan terhenti jika menemui jalan buntu, kemudian cabang yang menyebabkan jalan buntu tersebut akan ditandai untuk ditutup kemudian fungsi akan mencoba cabang baru (backtracking) sampai solusi ditemukan. Status dari sisi yang bernilai 1 berguna sebagai petunjuk, karena jika masih bernilai 3 maka fungsi akan mendahului garis yang bernilai 1 dan kebalikannya jika sisi tersebut bernilai 0 maka fungsi tidak akan melaluinya. Pseudo code modul dapat dilihat pada Lampiran 12. Hasil Pengujian Pengujian dilakukan dengan membangkitkan 30 soal slither link secara acak pada setiap ukuran puzzle, mulai dari ukuran puzzle 3x3 sampai dengan 20x20 kemudian dihitung waktu penyelesaian atau waktu eksekusi sampai dengan sebuah solusi didapatkan dari kedua metode yaitu answer set programming (ASP) dan procedural

programming (PP). Waktu yang digunakan sebagai perbandingan adalah rata-rata waktu eksekusi dari tiap ukuran, sistem memberi batas waktu (time out) yaitu 300 detik untuk menyelesaikan slither link jika sistem melewatinya maka ditandai. Waktu eksekusi tersebut dituliskan pada Tabel 1. Tabel 1. Waktu eksekusi (detik) dari teknik Answer Set Programming (ASP) dan procedural programming (PP) dan waktu pembangkitan (detik). Ukuran

ASP

PP

Pem bangkit an

3

0,21

0,15

0,60

4

0,24

0,16

0,59

5

0,27

0,15

0,80

6

0,33

0,29

0,87

7

0,39

0,26

1,06

8

0,45

1,15

1,34

Jumlah Timeout ASP

PP

9

0,54

0,37

1,81

10

0,59

0,43

2,13

11

0,63

0,87

1,88

12

0,70

1,23

2,20

13

0,79

5,25

3,99

14

0,93

7,00

4,36

15

1,17

4,64

5,27

16

1,14

12,61

5,59

17

1,38

12,11

6,45

1

18

1,68

5,80

12,69

5

19

1,94

14,09

7,86

3

20

2,06

18,74

11,42

5

1

Kecepatan waktu eksekusi ASP tidak mengalami kenaikan yang drastis ketika ukuran slither link mengalami peningkatan, berbanding terbalik dengan waktu eksekusi pada metode procedural programming dimana waktunya mengalami kenaikan pesat. Jika dibandingkan hasil keduanya maka waktu eksekusi dengan menggunakan metode answer set programming lebih cepat dibandingkan procedural programming. berikut adalah grafik waktu pembangkitan dan waktu eksekusi dari kedua metode.

14

DAFTAR PUSTAKA Cormen TH, Leiserson CE, Rivest RL, Stein C. 2001. Introduction to Algorithm. England : McGraw-Hill.

Gambar 37 Grafik perbandingan waktu eksekusi dan ukuran slither link.

KESIMPULAN DAN SARAN Kesimpulan Tujuan utama dari penelitian ini adalah membuat model penyelesaian slither link dengan menggunakan paradigma answer set programming, paradigma ini akan menyelesaikan slither link seperti cara berpikir manusia dengan mengkodekan program ke dalam bahasa logika, berbeda dengan paradigma procedural programming dimana programmer menuliskan urutan instruksi untuk dikerjakan oleh komputer berupa operasi yang akan dilakukan dan nilai yang akan disimpan dalam variabel. Paradigma answer set programming yang diaplikasikan pada masalah slither link terbukti efisien dan efektif dalam rata-rata waktu eksekusi dibandingkan menggunakan procedural programming dan dalam hal kualitas kode program yang dihasilkan meskipun procedural programming mendukung penggunaan fungsi tetapi karena ukuran kode program yang besar akan sulit ketika dilakukan pengembangan atau perubahan sistem. Model penyelesaian slither link telah sukses diaplikasikan ke bentuk web based sehingga berbentuk game interactive dengan menggunakan antar muka sehingga pengguna bisa memainkan slither link dan meminta penyelesaiannya. Saran Penelitian selanjutnya diharapkan bisa menerapkan answer set programming untuk membangkitkan soal slither link yang dijamin sulit, karena saat ini pembangkitnya menggunakan procedural programming yang tidak dijamin sulit solusinya. Memperbaiki kinerja dari penyelesaian slither link yang menggunakan procedural programming dengan menggunakan teknik lain.

Conceptis Puzzle. 1997. Slither link Technique. [terhubung berkala]. http://www.conceptispuzzles.com/index.as px?uri=puzzle/slitherlink/techniques [12 januari 2011]. Eiter T, Gottlob G. 1993. Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics. Technical University of Vienna. http://www.kr.tuwien.ac.at/staff/eiter/etarchive/ilps93.ps.gz . Garey MR, Johnson DS. 1979. Computers and Intractability : a guide to the theory of NPCompleteness. United States of America : Bell Telephone Laboratories. Gelfond M, Lifschitz V. 1991. Classsical Negation in Logic Programs and Disjunctive Databases. University of Texas. http://citeseerx.ist.psu.edu/viewdoc/downl oad?doi=10.1.1.49.9332&rep=rep1&type= pdf . Leone N et al. 2006. The DLV System for Knowledge Representation and Reasoning. ACM Trans. Comput. Log. Lifschitz V. 2008. What is Answer Set Programming. Department of Computer Sciences – University of Texas at Austin. http://userweb.cs.utexas.edu/users/vl/paper s/wiasp.pdf Tucker AB, Noonan R. 2002. Programming Languanges : Principles and Paradigms. England : McGraw-Hill. Wan J. 2009. Logical Slither link. Computer Science and Mathematics – School of Computer Science. http://intranet.cs.man.ac.uk/Intranet_subw eb/library/3yrep/2009/7035254.pdf . Yato T, Seta T. 2003. Complexity and Completeness of Finding Solution and its Application to Puzzles. Department of Computer Science – The Unversity of Tokyo. http://www-imai.is.s.utokyo.ac.jp/~yato/data2/SIGAL87-2.pdf .

15

LAMPIRAN

16

Lampiran 1 Program DLV, modul pembangkitan. 1 2 3 4 5

arc(X,Y,1,0,0,0) C(X,Y,1). arc(X,Y,1,1,0,0) arc(X,Y,1,0,1,0) arc(X,Y,1,1,1,0) C(X,Y,3). arc(X,Y,0,0,0,0) arc(X,Y,1,0,0,0) arc(X,Y,1,1,0,0) arc(X,Y,1,0,1,0) arc(X,Y,1,0,1,1)

v arc(X,Y,0,1,0,0) v arc(X,Y,0,0,1,0) v arc(X,Y,0,0,0,1) :v arc(X,Y,0,1,1,0) v arc(X,Y,0,0,1,1) v arc(X,Y,1,0,0,1) v v arc(X,Y,0,1,0,1) :- C(X,Y,2). v arc(X,Y,0,1,1,1) v arc(X,Y,1,0,1,1) v arc(X,Y,1,1,0,1) ::- C(X,Y,0). v arc(X,Y,0,1,0,0) v arc(X,Y,0,1,1,0) v arc(X,Y,0,1,0,1) v arc(X,Y,1,1,0,1)

v v v v

arc(X,Y,0,0,1,0) v arc(X,Y,0,0,0,1) v arc(X,Y,0,0,1,1) v arc(X,Y,1,0,0,1) v arc(X,Y,1,1,1,0) v arc(X,Y,0,1,1,1) v arc(X,Y,0,0,0,0) :- C(X,Y,null).

Modul ini akan membangkitkan kemungkinan solusi dengan melihat angka di dalam cell slither link, baris pertama akan membangkitkan kandidat solusi untuk cell yang memiliki nilai 1 ditunjukkan oleh predikat C(X,Y,1), baris kedua akan membangkitkan kandidat solusi untuk cell dengan nilai 2, baris ketiga untuk cell dengan nilai 3, baris keempat untuk cell dengan nilai 0, dan baris kelima untuk cell dengan nilai null.

17

Lampiran 2 Program DLV, constraint cell dengan nilai 0, 1, 2, dan 3. 1 2 3 4

::::-

arc(X,Y,1,0,0,0), arc(X,Y,0,1,0,0), arc(X,Y,0,0,1,0), arc(X,Y,0,0,0,1),

arc(A,Y,_,_,0,_), arc(X,B,_,_,_,0), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_),

X=A+1. B=Y+1. A=X+1. Y=B+1.

5 6 7 8 9 10 11 12 13 14 15 16

::::::::::::-

arc(X,Y,1,1,0,0), arc(X,Y,1,1,0,0), arc(X,Y,0,1,1,0), arc(X,Y,0,1,1,0), arc(X,Y,0,0,1,1), arc(X,Y,0,0,1,1), arc(X,Y,1,0,0,1), arc(X,Y,1,0,0,1), arc(X,Y,1,0,1,0), arc(X,Y,1,0,1,0), arc(X,Y,0,1,0,1), arc(X,Y,0,1,0,1),

arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_), arc(X,B,_,_,_,0), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(A,Y,_,_,0,_), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(X,B,_,_,_,0),

B=Y+1. X=A+1. B=Y+1. A=X+1. Y=B+1. A=X+1. Y=B+1. X=A+1. X=A+1. A=X+1. Y=B+1. B=Y+1.

17 18 19 20 21 22 23 24 25 26 27 28

::::::::::::-

arc(X,Y,1,1,1,0), arc(X,Y,1,1,1,0), arc(X,Y,1,1,1,0), arc(X,Y,0,1,1,1), arc(X,Y,0,1,1,1), arc(X,Y,0,1,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,1,0,1), arc(X,Y,1,1,0,1), arc(X,Y,1,1,0,1),

arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,_,_,0), arc(X,B,_,0,_,_), arc(A,Y,0,_,_,_), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(X,B,_,0,_,_), arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_),

B=Y+1. X=A+1. A=X+1. B=Y+1. Y=B+1. A=X+1. X=A+1. A=X+1. Y=B+1. Y=B+1. B=Y+1. X=A+1.

29 30 31 32

::::-


arc(X,B,_,_,_,1), arc(X,B,_,1,_,_), arc(A,Y,_,_,1,_), arc(A,Y,1,_,_,_),

B=Y+1. Y=B+1. X=A+1. A=X+1.

Bagian B=Y+1 menandakan bahwa posisi B ada di bawah Y, dan bagian X=A+1 menandakan bahwa posisi X ada di sebelah kanan A .Baris 1 sampai baris 4 pada lampiran ini menunjukkan constraint untuk cell bernilai 1, baris 5 sampai baris 16 menunjukkan constraint untuk cell bernilai 2, dan pada baris 17 sampai baris 28 constraint untuk cell bernilai 3. Baris 29 sampai baris 32 menunjukkan constraint untuk cell bernilai 0.

18

Lampiran 3 Program DLV, constraint mencegah local loop. 1 2 3 4

::::-


arc(A,Y,0,1,1,1), arc(A,Y,1,0,1,1), arc(X,B,1,0,1,1), arc(X,A,1,1,1,0),

A=X+1. X=A+1. Y=B+1. A=Y+1.

5 6 7 8

::::-


arc(X,B,_,1,_,_), arc(A,Y,_,_,1,_), arc(X,B,_,_,_,1), arc(A,Y,1,_,_,_),

Y X B A

= = = =

B+1. A+1. Y+1. X+1.

Baris 1 sampai baris 4 menunjukkan constraint untuk mencegah sebuah cell memiliki nilai 4 atau cell tersebut memilik 4 buah garis yang mengelilinginya, dan baris 5 sampai baris 8 menunjukkan constraint untuk mencegah dua buah cell bernilai 3 yang bertetangga dan keduanya membentuk loop.

19

Lampiran 4 Program DLV, constraint pada cell dengan posisi di pojok grid. 1 2 3 4 5 6 7 8

::::::::-

arc(1,1,1,0,0,0). arc(1,1,0,0,0,1). arc(1,1,0,0,1,1). arc(1,1,1,1,0,0). arc(1,1,1,1,1,0). arc(1,1,0,1,1,1). arc(1,1,0,1,0,1). arc(1,1,1,0,1,0).

9 10 11 12 13 14 15 16

::::::::-

arc(1,#maxint,1,0,0,0). arc(1,#maxint,0,1,0,0). arc(1,#maxint,1,0,0,1). arc(1,#maxint,1,0,1,1). arc(1,#maxint,0,1,1,1). arc(1,#maxint,0,1,0,1). arc(1,#maxint,1,0,1,0). arc(1,#maxint,0,1,1,0).

17 18 19 20 21 22 23 24

::::::::-

arc(#maxint,1,0,0,0,1). arc(#maxint,1,0,0,1,0). arc(#maxint,1,0,1,1,0). arc(#maxint,1,1,0,0,1). arc(#maxint,1,1,1,1,0). arc(#maxint,1,1,1,0,1). arc(#maxint,1,0,1,0,1). arc(#maxint,1,1,0,1,0).

25 26 27 28 29 30 31 32

::::::::-

arc(#maxint,#maxint,0,1,0,0). arc(#maxint,#maxint,0,0,1,0). arc(#maxint,#maxint,0,0,1,1). arc(#maxint,#maxint,1,1,0,0). arc(#maxint,#maxint,1,0,1,1). arc(#maxint,#maxint,1,1,0,1). arc(#maxint,#maxint,0,1,0,1). arc(#maxint,#maxint,1,0,1,0).

Pada baris 1 sampai baris 8 menunjukkan constraint untuk cell dengan posisi di pojok kiri atas grid (1,1), kemudian baris 9 sampai baris 16 adalah constraint untuk cell dengan posisi di pojok kanan atas grid dimana #maxint adalah ukuran dari slither link, baris selanjutnya yaitu baris 17 sampai baris 24 adalah constraint untuk cell dengan posisi di pojok kiri bawah grid, dan baris 25 sampai baris 32 pada lampiran menunjukkan constraint untuk cell dengan posisi di pojok kanan bawah grid.

20

Lampiran 5 Program DLV, constraint untuk mengantisipasi cabang dan ketersambungan garis. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

::::::::::::::::-

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

:- arc(X,Y,1,_,_,0), arc(A,B,_,M,N,_), M=N, X=A+1, Y=B+1. %kiri atas :- arc(X,Y,1,0,_,_), arc(A,B,_,_,M,N), M=N, X=A+1, B=Y+1. %kanan atas :- arc(1,Y,1,0,_,_), arc(1,B,0,_,_,_), B=Y+1. %atas -- kanan :- arc(1,Y,1,_,_,0), arc(1,B,0,_,_,_), Y=B+1. %atas -- kiri :- arc(X,#maxint,1,0,_,_), arc(A,#maxint,_,0,_,_), X=A+1. %bagian kanan -- atas :- arc(X,Y,0,1,_,_), arc(A,B,_,_,M,N), M=N, X=A+1, B=Y+1. %kanan atas :- arc(X,#maxint,_,1,0,_), arc(A,#maxint,_,0,_,_), A=X+1. %bagian kanan -- bawah :- arc(#maxint,Y,_,1,0,_), arc(#maxint,B,_,_,0,_), B=Y+1. %bagian bawah -- kanan :- arc(X,#maxint,0,1,_,_), arc(A,#maxint,_,0,_,_), X=A+1. %bagian kanan -- atas :- arc(1,Y,0,1,_,_), arc(1,B,0,_,_,_), B=Y+1. %bagian atas -- kiri :- arc(X,Y,_,_,1,0), arc(A,B,M,N,_,_), M=N, A=X+1, Y=B+1. %kiri bawah :- arc(X,Y,_,0,1,_), arc(A,B,M,_,_,N), M=N, A=X+1, B=Y+1. %kanan bawah :- arc(#maxint,Y,_,0,1,_), arc(#maxint,B,_,_,0,_), B=Y+1. %bawah -- kanan :- arc(#maxint,Y,_,_,1,0), arc(#maxint,B,_,_,0,_), Y=B+1. %bawah -- kiri :- arc(X,Y,0,_,_,1), arc(A,B,_,M,N,_), M=N, X=A+1, Y=B+1. %atas -- kiri :- arc(X,Y,_,_,0,1), arc(A,B,M,N,_,_), M=N, A=X+1, Y=B+1. %bawah -- kiri :- arc(X,1,_,_,0,1), arc(A,1,_,_,_,0), A=X+1. %samping kiri -- bawah :- arc(X,1,0,_,_,1), arc(A,1,_,_,_,0), X=A+1. %samping kiri - atas :- arc(X,1,1,_,_,0), arc(A,1,_,_,_,0), X=A+1. %samping kiri -- atas :- arc(X,1,_,_,1,0), arc(A,1,_,_,_,0), A=X+1. %samping kiri -- bawah :- arc(X,#maxint,1,0,1,0), arc(A,#maxint,_,0,_,_), arc(C,#maxint,_,0,_,_), A=X+1, X=C+1. %samping kanan -- bawah -- atas :- arc(X,1,1,0,1,0), arc(A,1,_,_,_,0), arc(C,1,_,_,_,0), A=X+1, X=C+1. %samping kiri -- bawah -- atas :- arc(#maxint,Y,0,1,0,1), arc(#maxint,B,_,_,0,_), B=Y+1. %bagian bawah -- kanan :- arc(#maxint,Y,0,1,0,1), arc(#maxint,B,_,_,0,_), Y=B+1. %bagian bawah -- kiri :- arc(1,Y,0,1,0,1), arc(1,B,0,_,_,_), B=Y+1. %bagian atas -- kanan :- arc(1,Y,0,1,0,1), arc(1,B,0,_,_,_), Y=B+1. %bagian atas – kiri

38 39 40 41 42

arc(X,Y,1,1,_,_), arc(A,B,_,_,1,_), X=A+1, B=Y+1. arc(X,Y,1,1,_,_), arc(A,B,_,_,_,1), X=A+1, B=Y+1. arc(X,Y,1,1,_,_), arc(X,B,1,_,_,_), B=Y+1. arc(X,#maxint,1,1,_,_), arc(A,#maxint,_,1,_,_), X=A+1. arc(X,Y,_,1,1,_), arc(A,B,1,_,_,_), A=X+1, B=Y+1. arc(X,Y,_,1,1,_), arc(A,B,_,_,_,1), A=X+1, B=Y+1. arc(X,Y,_,1,1,_), arc(X,B,_,_,1,_), B=Y+1. arc(X,#maxint,_,1,1,_), arc(A,#maxint,_,1,_,_), A=X+1. arc(X,Y,_,_,1,1), arc(A,B,1,_,_,_), A=X+1, Y=B+1. arc(X,1,_,_,1,1), arc(A,1,_,_,_,1), A=X+1. arc(X,Y,_,_,1,1), arc(A,B,_,1,_,_), A=X+1, Y=B+1. arc(X,Y,_,_,1,1), arc(X,B,_,_,1,_), Y=B+1. arc(X,Y,1,_,_,1), arc(A,B,_,1,_,_), X=A+1, Y=B+1. arc(X,Y,1,_,_,1), arc(A,B,_,_,1,_), X=A+1, Y=B+1. arc(X,Y,1,_,_,1), arc(X,B,1,_,_,_), Y=B+1. arc(X,1,1,_,_,1), arc(A,1,_,_,_,1), X=A+1.

Pada baris 1 sampai baris 16 menunjukkan constraint untuk mencegah terjadinya cabang pada solusi slither link, dan pada baris 17 sampai baris 42 menunjukkan constraint untuk tetap menjaga agar solusi slither link merupakan sebuah garis yang kontinyu (tidak terputus).

21

Lampiran 6 Program DLV, constraint dari cell bernilai 2 yang bersebelahan dengan cell bernilai 0. 1 2 3 4

::::-

arc(#maxint,Y,1,0,1,0), arc(#maxint,Y,1,0,1,0), arc(#maxint,Y,0,1,0,1), arc(#maxint,Y,0,1,0,1),

5 6 7 8

::::-

arc(1,Y,1,0,1,0), arc(1,Y,1,0,1,0), arc(1,Y,0,1,0,1), arc(1,Y,0,1,0,1),

arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0),

arc(1,B,0,0,0,0), arc(1,B,0,0,0,0), arc(1,B,0,0,0,0), arc(1,B,0,0,0,0),

Y=B+1. B=Y+1. Y=B+1. B=Y+1.

Y=B+1. B=Y+1. Y=B+1. B=Y+1.

%bagian %bagian %bagian %bagian

%bagian %bagian %bagian %bagian

atas atas atas atas

bawah bawah bawah bawah

-----

kiri kanan kiri kanan

-- kiri -- kanan -- kiri – kanan

Baris 1 sampai baris 4 pada lampiran ini ditujukan untuk cell dengan posisi di bagian bawah slither link, dan baris 5 sampai baris 8 adalah constraint untuk cell dengan posisi di bagian atas slither link.

22

Lampiran 7 Pseudo code program C++ untuk membaca fakta slither link. 1 2 3 4 5

Set count to 1 FOR each string on data.dat Set titik[count] to string Increment count END FOR

6 7 8 9

Set k to 1 FOR each side on slither_link Set line_value[k] to 3 END FOR

Baris 1 sampai baris 5 pada lampiran ini digunakan untuk membaca fakta yang telah disimpan dalam file data.dat, dan pada bairs 6 sampai baris 9 digunakan untuk memberikan nilai default yaitu 3 pada setiap sisi pada cell.

23

Lampiran 8 Pseudo code program C++, modul basic_rule . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

//basic rule FOR each cell in slither_link IF cell_value is 0 THEN Set no_line on cell is TRUE ELSE IF cell_value is 1 THEN IF cell_position is 1 Set line_value on up to 0 Set line_value on left to 0 END IF ... ELSE IF cell_value is 2 THEN IF cell_position is 1 THEN IF line_value on up is 0 AND line_value on left is 0 THEN Set line_value on right to 1 Set line_value on bottom to 1 END IF END IF ... ELSE IF cell_value is 3 THEN IF cell_position is 1 Set line_value on up to 1 Set line_value on left to 1 END IF ... END IF END FOR

24

Lampiran 9 Pseudo code program C++, modul advance_rule . 1 //advance_rule 2 FOR each cell in slither_link 3 IF cell_value is 1 THEN 4 IF cell_position on up THEN 5 IF line_value on up_left is 0 THEN 6 Set line_value on up to 0 7 Set line_value on left to 0 8 END IF 9 END IF 10 .... 11 ELSE IF cell_value is 2 THEN 12 IF line_value on up is 1 AND line_value on bottom is 0 THEN 13 IF line_value on right is 0 THEN 14 Set line_value on left to 1 15 ELSE IF line_value on left is 0 THEN 16 Set line_value on right to 1 17 END IF 18 END IF 19 ... 20 ELSE IF cell_value is 3 THEN 21 IF cell_position on up THEN 22 IF line_value on up_left is 0 23 Set line_value on up to 1 24 Set line_value on left to 1 25 ELSE IF line_value on up_right is 0 26 Set line_value on up to 1 27 Set line_value on right to 1 28 END IF 29 END IF 30 ... 31 END IF 32 END FOR

25

Lampiran 10 Pseudo code program C++, modul cek_garis_cell . 1 //cek_garis_cell 2 FOR each cell in slither_link 3 IF cell_value is 1 THEN 4 IF line_value on up is 1 5 Set line_value on right, bottom, left to 0 6 END IF 7 ELSE IF cell_value is 2 THEN 8 IF line_value on up is 1 AND line_value on right is 1 THEN 9 Set line_value on bottom, left to 0 10 END IF 11 ELSE IF cell_value is 3 THEN 12 IF line_value on up is 0 THEN 13 Set line_value on right, bottom, left to 1 14 END IF 15 END IF 16 END FOR

26

Lampiran 11 Pseudo code program C++, modul sambung_garis dan modul cek_cabang. 1 2 3 4 5 6 7 8 9 10 11 12 13

//sambung_garis Set k to 1 Set n to puzzle_size FOR each side on slither_link IF line_value is 1 IF line[k] is horizontal THEN IF line_value[k-n] is 0 AND line_value[k+1] is 0 THEN set line_value[k+n+1] to 1 ELSE IF line_value[k+n+1] is 0 AND line_value[k+1] is 0 THEN set line_value[k-n] to 1 END IF END IF ... END IF END FOR

14 //cek_cabang 15 FOR each cell in slither_link 16 IF line_value[up] is 1 AND line_value[up_right] is 1 THEN 17 Set line_value that branch to 0 18 ELSE IF line_value[up] is 1 AND line_value[up_left] is 1 THEN 19 Set line_value that branch to 0 20 .... 21 END IF 22 END FOR

27

Lampiran 12 Pseudo code program C++, modul cek_logic dan fungsi sambung. 1 //cek_logic 2 FOR each cell in slither_link 3 IF cell_position is 1 4 IF line_value[up_right] is 1 AND Line_value[left_bottom] is 1 THEN 5 IF line_value[up] is 0 OR Line_value[left] is 0 6 Set line_value[bottom] to 1 7 Set line_value[right] to 1 8 ElSE IF line_value[right] is 0 OR Line_value[bottom] is 0 9 Set line_value[up] to 1 10 Set line_value[left] to 1 11 END IF 12 END IF 13 ELSE IF cell_position is puzzle_size 14 IF line_value[up_left] is 1 AND Line_value[right_bottom] is 1 THEN 15 IF line_value[up] is 0 OR line_value[right] is 0 THEN 16 Set line_value[bottom] to 1 17 Set line_value[left] to 1 18 ELSE IF line_value[left] is 0 OR line_value[bottom] is 0 THEN 19 Set line_value[up] to 1 20 Set line_value[right] to 1 21 END IF 22 END IF 23 ... 24 END IF 25 END FOR 26 27 28 29 30 31 32 33 34 35 36 37

//fungsi sambung Function sambung(puzzle_data) { Set status to 0 While status is 0 Do traversal until find a loop IF a loop satisfy the puzzle rule THEN Set status to 1 END IF END DO END WHILE }

28

PEMBANGKITAN DAN PENYELESAIAN SLITHER LINK DENGAN ANSWER SET PROGRAMMING DAN PROCEDURAL PROGRAMMING SALMAN FARIZI

Recommend Documents