Transcription
View metadata, citation and similar papers at core.ac.ukbrought to you byCOREprovided by Research Report - Engineering SciencePerjanjian No: III/LPPM/2014-03/40-pPENGEMBANGAN PROTOTIPE SUDOKU SOLVERBERBASIS SISTEM MULTI AGENDisusun Oleh:Luciana Abednego, S.Kom., M.T.Dr.rer.nat. Cecilia E. Nugraheni. S.T., M.T.Lembaga Penelitian dan Pengabdian kepada MasyarakatUniversitas Katolik Parahyangan2014
ABSTRAKSudoku adalah sejenis teka-teki logika yang tujuan akhirnya adalah mengisikan angka-angka 1sampai dengan 9 ke dalam suatu kotak berukuran 9x9. Kotak ini memiliki 9 sub-kotakberukuran 3x3. Syarat teka-teki ini adalah tidak ada angka yang berulang pada setiap baris,kolom, atau sub-kotak. Teka-teki Sudoku termasuk ke dalam permasalahan kombinatorial (NPcomplete). Solusi untuk teka-teki ini dapat dicari dengan bermacam-macam cara sepertialgoritma genetik, heuristik, dan sebagainya.Penelitian ini merupakan penelitian lanjutan dari penelitian sebelumnya yang berjudul“Pemodelan Permainan Sudoku sebagai Block-World Problem” yang telah menghasilkan tigamodel untuk Sudoku solver. Pada penelitian tersebut Block-World Problem dipandang sebagaisistem multi agen berparameter. Model ditulis secara formal dengan notasi TLA .Pada penelitian ini diusulkan satu model baru yang merupakan varian dari model yang sudahada. Penelitian ini juga menghasilkan sebuah framework Sudoku Solver yaitu program yangdapat digunakan untuk membangun sebuah solver berdasarkan model tertentu. Denganframework tersebut dikembangkan prototype Sudoku solver berdasarkan model yang telahdihasilkan. Keempat model yang telah diusulkan telah diimplementasikan pada frameworktersebut. Eksperimen terhadap kinerja dari seluruh solver dilakukan dengan melihatkeberhasilannya dalam mencari solusi untuk sekumpulan soal Sudoku dilihat dari sisi waktudan banyaknya permainan yang dapat diselesaikan. .ii
DAFTAR ISIHal.iiiiiiivVJudulAbstrakDaftar IsiDaftar GambarDaftar TabelBab 1 PENDAHULUAN1.1 Latar Belakang1.2 Rumusan Masalah1.3 Tujuan1.4 Kontribusi Penelitian1.5 Keluaran112333Bab II TINJAUAN PUSTAKA2.1 Permasalahan Sudoku2.2 Pemodelan Sudoku Sebagai Block World Problem2.2.1 Pemetaan Komponen Permainan Sudoku kedalam Block-World Problem2.2.2 Model 12.2.3 Model 22.2.4 Model 34455679Bab III METODE PENELITIAN11Bab IV HASIL YANG DICAPAI4.1 Usulan Model Baru4.2 Implementasi Framework4.3 Implementasi Solver4.4 Hasil Eksperimen1212132122Bab V SIMPULAN5.1 Kesimpulan5.2 Rencana Penelitian Lebih Lanjut252525DAFTAR PUSTAKA26iii
DAFTAR GAMBARGambar 1.1Gambar 1.2Gambar 2.1Gambar 2.2Gambar 2.3Gambar 2.4Gambar 2.5Gambar 4.1Gambar 4.2Gambar 4.3Contoh teka-teki Sudoku (a) dan solusinya (b)Block-world problemModifikasi Block World ProblemModifikasi Block World Problem untuk Model 1.Modifikasi Block World Problem untuk Model 2 dan 3.Contoh posisi valid untuk model 2.Contoh posisi valid untuk model 3.Contoh posisi valid untuk model 4.Arsitektur Sistem Multi AgenDiagram KelasivHal.12678910131415
DAFTAR TABELTabel 4.1Tabel 4.2Tabel 4.3Hal.222324Hasil Eksperimen 1Hasil Eksperimen 2Hasil Eksperimen 3v
BAB IPENDAHULUAN1.1 Latar BelakangSudoku adalah sejenis teka-teki logika yang tujuan akhirnya adalah mengisikan angka-angka 1sampai dengan 9 ke dalam suatu kotak berukuran 9x9. Kotak ini memiliki 9 sub-kotak berukuran3x3. Syarat teka-teki ini adalah tidak ada angka yang berulang pada setiap baris, kolom, atau subkotak. Pada saat awal, kotak sudoku belum terisi penuh dengan angka seperti terlihat pada gambar1.1 (a). Solusi untuk teka-teki Sudoku pada gambar 1.1 (a) dapat dilihat pada gambar 1.1 (b),ditandai dengan angka berwarna merah. Teka-teki Sudoku pertama kali dipopulerkan sebuahperusahaan teka-teki Jepang bernama Nikoli pada tahun 1986, yang kemudian mendunia padatahun 2005.Gambar 1.1. Contoh teka-teki Sudoku (a) dan solusinya (b)Teka-teki Sudoku termasuk ke dalam permasalahan kombinatorial (NP complete). Solusiuntuk teka-teki ini dapat dicari dengan bermacam-macam cara seperti algoritma genetik [6],Particle Swarm Optimization [9, 10], dan sebagainya. Pada penelitian ini akan dilakukan suatupendekatan yang berbeda untuk pencarian solusi dari permainan Sudoku, yaitu denganmemodelkannya sebagai Block-World Problem.vi
Pada Block-World Problem, terdapat sejumlah balok pada meja dengan susunan tertentu. Balokbalok tersebut kemudian diubah susunannya menjadi susunan balok akhir dengan bantuan duajenis robot. Robot pertama bertugas memindahkan balok dari tumpukan balok ke meja, sementararobot yang lain bertugas memindahkan balok dari meja ke atas tumpukan balok yang lain. Keduarobot saling bekerja sama dengan berkomunikasi untuk menghasilkan susunan balok akhir. Padasetiap saat, hanya terdapat satu balok yang dapat dipindahkan ke meja atau ke atas tumpukan balokyang lain. Balok yang berada di bawah balok yang lain tidak dapat langsung dipindahkan sebelumbalok-balok yang terdapat di atasnya dipindahkan. Gambar 1.2 memperlihatkan contoh tumpukanbalok awal (a) dan tumpukan balok akhir (b). Fokus dari permasalahan Block-world Problemadalah pencari solusi yang berupa urutan langkah mulai dari susunan awal sampai dengan susunanakhir.(a)(b)Gambar 1.2 Block-World Problem, (a) tumpukan balok awal, (b) tumpukan balok akhirPada penelitian sebelumnya permainan Sudoku telah berhasil dimodelkan sebagai Block-WorldProblem [11]. Model yang dihasilkan sebanyak tiga buah yang ditulis secara formal dalam notasiTemporal Logic of Actions (TLA ). Model yang dikembangkan mengikuti kerangka spesifikasiumum untuk parameterized systems yaitu salah satu kelas sistem reaktif yang terdiri atas beberapakomponen sejenis dengan banyaknya komponen dinyatakan sebagai parameter. Lebih lanjut,model dikembangkan dengan konsep multi-agent systems.1.2 Rumusan MasalahRumusan masalah yang diangkat pada penelitian ini adalah:1. Bagaimana mengimplementasikan model formal tersebut menjadi sudoku Solver denganbahasa pemrograman Java?vii
Terdapat perbedaan sudut pandang antara spesifikasi formal dengan TLA dengan bahasapemrograman Java. Salah satu hal penting yang harus diperhatikan pada saat implementasiadalah bagaimana mengimplementasikan pendekatan interleaving dan konsep multi-agentsystems dengan Java. Selain itu masalah yang harus diperhatikan adalah bagaimana masalahpenjadwalan robot dan bagaimana komunikasi antar robot.2. Bagaimana performansi dari ketiga model yang telah dikembangkan?Untuk menjawab pertanyaan ini perlu dilakukan eksperimen terhadap prototipe denganmencoba setiap model pada sekumpulan soal Sudoku.1.3 TujuanTujuan dari penelitian ini adalah1. Mengembangkan framework Sudoku Solver.2. Mengembangkan prototype Sudoku solver berdasarkan model yang telah dihasilkansebelumnya, dimana Sudoku dimodelkan sebagai permasalahan Block-World Problem.3. Melakukan eksperimen terhadap masing-masing solver untuk mengetahui kinerjanya.1.4 Kontribusi PenelitianSelain berkontribusi terhadap pengembangan ilmu pengetahuan, yaitu memperkaya alternatifpencarian solusi dari permasalahan Sudoku, penelitian ini juga akan menghasilkan sebuahframework Sudoku Solver yaitu sebuah program yang dapat digunakan untuk mengembangkanSudoku Solver. Framework ini bisa digunakan untuk mempermudah pengembangan Sudoku solveryang lain.1.5 KeluaranKeluaran yang ditargetkan dari penelitian ini adalah publikasi dalam konferensi yang relevan ataudalam jurnal ilmiah nasional/internasional.viii
BAB IITINJAUAN PUSTAKA2.1 Permasalahan SudokuStudi pustaka yang telah dilakukan sejauh ini adalah dengan mempelajari beberapa hasil penelitianyang dapat ditemukan di internet. Khususnya yang terkait dengan pendekatan/teknik/algoritma yang digunakan untuk pencarian solusi. Beberapa di antaranya adalah:1. Pada referensi [7] dibahas pendekatan pencarian solusi permainan Sudoku denganmenggunakan pendekatan pencarian berbasis stokastik, yaitu simulated annealing. Selain itu,pada penelitian ini juga diperkenalkan metode baru untuk membangkitkan papan permainanSudoku yang dapat diselesaikan dengan simulated annealing.2. Pada referensi [13] dibahas tentang penyelesaian permainan Sudoku dengan memandangSudoku sebagai Constraint Satisfaction Problem. Pendekatan yang digunakan adalahconstraint programming. Selain masalah pencarian solusi permainan Sudoku, pada makalahini juga dibahas tentang teknik untuk membangkitkan papan Sudoku dan menentukan tingkatkesulitan dari suatu permainan Sudoku.3. Pada referensi [5] permainan Sudoku dimodelkan sebagai suatu permasalahan SAT problem.Permainan Sudoku disini direpresentasikan sebagai sekumpulan proposisi dalam bentukConjunctive Normal Form (CNF) dari logika proposisi. Pencarian solusinya dilakukan denganprinsip inferensi dengan menggunakan teknik propagasi unit dan teknik lain yang lebihkompleks.4. Pada referensi [4, 6, 8, 14] diusulkan pendekatan untuk penyelesaian dan pembangkitanpermainan Sudoku dengan evolutionary algorithms, khususnya algoritma genetik. Tujuan daripenelitian yang dilakukan adalah menguji apakah algoritma genetic cukup efisien untukmemecahkan permainan Sudoku dan untuk membangkitkan papan permainan Sudoku.5. Sedangkan untuk Block-World problem, digunakan referensi [11]. Pada makalah ini dikajibagaimana Block-world Problem dapat dipandang sebagai suatu parameterized multi agentsystem dan bagaimana permasalahan tersebut dapat dinyatakan secara formal denganmenggunakan notasi Temporal Logic of Actions (TLA ).ix
2.2 Pemodelan Sudoku sebagai Block-World ProblemPada bagian akan diberikan dengan singkat pemodelan Sudoku sebagai Block-World Problemyang dilakukan pada penelitian sebelumnya.2.2.1 Pemetaan Komponen Permainan Sudoku kedalam Block-World ProblemDefinisi Sudoku yang digunakan pada penelitian ini mengikuti definisi dari [4], yaitu sbb.:Definisi 1.Diberikan sebuah n2xn2 sel yang terbagi atas n x n subblok berbeda, tujuan daripermainan Sudoku adalah mengisi setiap sel sedemikian sehingga kondisi berikut ini terpenuhi:1) Pada setiap baris sel terdapat satu sel yang bernomor 1 sampai n22) Pada setiap kolom sel terdapat satu sel yang bernomor 1 sampai n23) Pada setiap subblok terdapat satu sel yang bernomor 1 sampai n2Pada penelitian ini, diambil nilai n 3.Pada bagian awal laporan ini, telah diperkenalkan komponen dari Block-World Problem dan tujuandari permasalahan tersebut. Untuk memodelkan Sudoku kedalam permasalahan Block- WorldProblem, maka dilakukan modifikasi terhadap komponen dari Block-World Problem sbb.: Jumlah kotak di atas meja sebanyak 9 x 9. Setiap kotak diberi nomor antara 1 s/d 9. Setiap nomor b {1, ., 9} terdapat 9 kotak dengan nomor b. Terdapat bagian khusus pada meja yang disebut dengan papan yang terdiri atas 3 x 3 grid.Setiap grid disebut subblok dan setiap subblok terdiri atas 3 x 3 grid yang lebih kecil yangdisebut sel.Pada saat awal sebagian kotak sudah berada pada sel papan dan sebagian di luar papan. Kotakyang berada di luar papan disusun dalam sembilan tumpukan sesuai dengan nomor kotaknya. Hasilmodifikasi tersebut dapat digambarkan seperti tampak pada Gambar 2.1.Selanjutnya dilakukan juga modifikasi terhadap perilaku dari robot sbb. :x
Robot pertama berfungsi untuk mengambil sebuah kotak dari luar papan dan meletakkannyadi salah satu sel di papan sedemikian sehingga syarat-syarat yang dinyatakan pada Definisi 1dapat terpenuhi. Robot kedua berfungsi untuk mengambil sebuah kotak dari sel pada papan danmengembalikannya ke tumpukan luar papan sesuai dengan nomor kotak yang diambil.Dengan modifikasi tersebut maka Block-World Problem menjadi teka-teki Sudoku.Gambar 2.1. Modifikasi Block-World ProblemSelanjutnya akan dijelaskan tiga model solver yang diusulkan pada untuk menyelesaikanpermasalahan Sudoku. Ketiga model ini berbeda dari jumlah robot dan tugas dari robotnya.2.2.2 Model 1Mirip dengan Block-world problem yang asli pada model ini digunakan dua buah robot yangberbeda jenis. Robot ini akan secara bergiliran menjalankan tugasnya dengan aturan sbb.: Robot pertama mendapat giliran lebih dulu. Tugas robot ini adalah mengisi sel yang kosongdengan sebuah kotak dari tumpukan di luar papan tanpa melanggar syarat yang ditetapkan.Robot pertama ini akan bekerja terus-menerus sampai salah satu kondisi berikut:1. Semua sel papan telah terisi dengan kotak, yang berarti teka-teki berhasil dipecahkan. Jikakondisi ini tercapai, maka robot satu akan melaporkan bahwa solusi ditemukan.2. Tidak ada lagi sel yang dapat diisi dengan kotak di luar papan. Jika kondisi ini tercapai,maka robot satu akan melaporkan telah terjadi kegagalan dalam pencarian solusi.xi
Dalam proses pencarian sel yang kosong, robot pertama ini akan memilih sel dengan posisiterkecil. Didefinisikan posisi terkecil adalah (1,1) dan terbesar adalah (9,9). Robot ini akanmencatat sel yang kosong dan yang sudah terisi selama proses pencarian solusi berlangsung.Gambar 2.2. Modifikasi Block-World Problem untuk Model 1.Robot kedua bertugas bilamana robot pertama gagal menemukan sel kosong yang dapat diisidengan kotak. Robot ini bertugas untuk mengambil sebuah kotak di sel dan mengembalikan ketumpukan yang sesuai untuk kotak tersebut. Pada model ini digunakan aturan kotak yang diambiladalah kotak yang paling akhir diletakkan oleh robot pertama. Untuk itu robot kedua memerlukaninformasi tentang urutan penempatan kotak oleh robot pertama.2.2.3 Model 2Berbeda dengan model pertama, model 2 dan model3 menggunakan sembilan robot dengan tipeyang sama. Setiap robot bertanggung jawab terhadap kotak-kotak yang berada pada sebuahtumpukan kotak yang sesuai dengan nomernya. Semua robot mempunyai tugas yang sama yaituberusaha meletakkan sebuah kotak dari tumpukannya ke sel di papan tanpa melanggar aturan yangberlaku.Pada model 2 dan 3 digunakan prinsip fixed-point. Pencarian solusi dilakukan dengan melakukaniterasi sampai kondisi berhenti tercapai. Dalam setiap iterasi, setiap robot i mencari sel atau sebuahposisi valid yang dapat ditempati oleh kotak bernomor i. Jika pencarian sel berhasil, maka robot ixii
akan meletakkan kotak i pada sel tersebut. Setelah melakukan tugasnya, robot i memberikan giliranke robot berikutnya. Setelah robot 9 melakukan tugasnya, akan ditentukan apakah iterasidilanjutkan atau dihentikan. Jika dalam suatu iterasi tidak ada satu robot pun yang berhasilmeletakkan sebuah kotak, maka iterasi dihentikan, iterasi dilanjutkan untuk kondisi sebaliknya.Gambar 2.3. Modifikasi Block-World Problem untuk Model 2 dan 3.Perbedaan antara model 2 dan model 3 terletak pada definisi posisi valid. Untuk model 2 posisivalid didefinisikan sbb.:Definisi 2. Sebuah robot i menyebut sebuah posisi (x,y) valid untuk kotak bernomor i jika kondisikondisi berikut ini terpenuhi:1. Sel pada posisi tersebut kosong.2. Baris x tidak mengandung kotak bernomor i.3. Kolom y tidak mengandung kotak bernomor i.4. Subblok dimana posisi (x,y) berada tidak mengandung kotak bernomor i5. Untuk setiap baris r yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i.6. Untuk setiap kolom c yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i.xiii
Gambar 2.4 menampilkan contoh posisi valid untuk model 2. Posisi (9,7) adalah posisi valid bagirobot 4. Tampak pada gambar tersebut setiap baris pada subblok dimana (9,7) berada, yaitu baris7 dan 8, masing-masing mengandung kotak bernomor 4. Demikian juga pada setiap kolom padasubblok dimana (9,7) berada, yaitu kolom 8 dan kolom 9 masing-masing mengandung kotakbernomor 4.Gambar 2.4. Contoh posisi valid untuk model 2.2.2.4 Model 3Model 3 ini sangat mirip dengan model 2. Perbedaannya hanya terletak pada definisi posisi valid.Untuk model 3 digunakan definisi berikut untuk menyatakan sebuah posisi valid atau tidak.Definisi 3. Sebuah robot i menyebut sebuah posisi (x,y) valid jika kondisi-kondisi berikut initerpenuhi:1. Sel pada posisi tersebut kosong.2. Baris x tidak mengandung kotak bernomor i.3. Kolom y tidak mengandung kotak bernomor i.4. Subblok dimana posisi (x,y) berada tidak mengandung kotak bernomor i5. Untuk setiap baris r yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i atau sel pada posisi (r,y) tidak kosong.xiv
6. Untuk setiap kolom c yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i atau sel pada posisi (x,c) tidak kosong.Contoh posisi valid untuk model 3 diberikan pada Gambar 2.5. Mirip dengan contoh posisi validuntuk model 2 (gambar 2.4), robot 4 dapat menyatakan posisi (9,7) adalah posisi yang valid.Meskipun tidak terdapat sel bernomor 4 pada baris 7, tetapi posisi (7,7) tidak kosong sehinggadapat dipastikan kotak bernomor 4 tidak akan dapat diletakkan pada posisi (7,7) tersebut.Gambar 2.5. Posisi valid untuk model 3.xv
BAB IIIMETODE PENELITIANMetode penelitian pada penelitian ini adalah: Studi literaturStudi literatur dilakukan dengan mempelajari makalah-makalah yang terkait dengan topikpenelitian. Pengembangan framework dan prototype solverUntuk pengembangan framework akan digunakan tahapan yang umum dilaksanakan dalampengembangan perangkat lunak, khususnya tahapan analisis, perancangan, implementasi, danpengujian. EksperimenEksperimen dilakukan dengan mencoba sekumpulan soal Sudoku yang dapat ditemukan diinternet atau dari buku-buku kumpulan soal Sudoku. Eksperimen ini bertujuan untukmenentukan sejauh mana model yang dibuat dapat menyelesaikan soal-soal Sudoku tersebut.Dari hasil eksperimen ini akan disimpulkan kinerja dari setiap model, dengan melihatprosentase soal yang berhasil diselesaikan, banyaknya sel kosong papan Sudoku yang berhasildiisi, dan dari sisi waktu yang diperlukan untuk menyelesaikan soal Sudoku.xvi
BAB IVHASIL YANG DICAPAIPada bagian ini dijelaskan hasil yang dicapai pada penelitian yang telah dilakukan. Terdapat empathasil yang dapat dilaporkan, yaitu:1. Usulan model solver yang baru.2. Pengembangan framework3. Pengembangan Sudoku solver.4. Hasil eksperimen terhadap performansi masing-masing solver.4.1 Usulan Model BaruPada penelitian ini diusulkan sebuah model baru yang merupakan pengembangan dari model 3.Seperti model 3, pada model 4 ini digunakan sembilan robot dengan tugas yang sama yaitumengambil sebuah kotak dari tumpukan di luar papan, dan meletakkannya pada salah satu sel dipapan sedemikian sehingga tidak melanggar aturan Sudoku. Perbedaan model 4 ini dengan model2 adalah pada definisi posisi valid.Definisi posisi valid untuk model 4 adalah sbb.:Definisi 4. Sebuah robot i menyebut sebuah posisi (x,y) valid jika kondisi-kondisi berikut initerpenuhi:1. Sel pada posisi tersebut kosong.2. Baris x tidak mengandung kotak bernomor i.3. Kolom y tidak mengandung kotak bernomor i.4. Subblok dimana posisi (x,y) berada tidak mengandung kotak bernomor i5. Untuk setiap baris r yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i atau sel pada posisi (r,y) tidak kosong atau semua sel pada padabaris r tidak kosong .xvii
6. Untuk setiap kolom c yang berada pada subblok dimana (x,y) berada terdapat satu sel yangmengandung kotak bernomor i atau sel pada posisi (x,c) tidak kosong atau semua sel padakolom c tidak kosong.Gambar 4.1 memperlihatkan contoh posisi valid bagi robot 5 untuk model 4. Tampak pada gambar,posisi (7,4) termasuk posisi valid. Meskipun tidak ada sel yang mengandung kotak bernomor 5pada baris 8 dan kolom 6, robot 5 masih dapat menemukan posisi untuk meletakkan kotakbernomor 4 pada posisi ini karena semua sel pada baris 8 dan kolom 6 tidak kosong.Gambar 4.1. Contoh posisi valid untuk model 4.4.2 Implementasi FrameworkPada [11] Sudoku solver dimodelkan sebagai sebuah sistem multi agen berparameter. Sebuahsistem multi agen berparameter adalah sebuah sistem yang terdiri atas sejumlah komponen(subsistem) yang mirip yang bekerja bersama-sama, jumlah komponen dinyatakan sebagaiparameter masukan dari sistem. Agennya adalah robot, lingkungannya adalah papan dan kotak.Model ditulis dengan menggunakan TLA sebagai bahasa spesifikasi.xviii
Terdapat beberapa aspek penting yang harus dipertimbangkan dalam mengimplementasikansistem multi agen berparameter tersebut, seperti arsitektur, komunikasi antar agen, danpenjadwalan agen. Pada penelitian ini karena penekanannya lebih kepada pengukuran performansidari masing-masing model, maka diambil pendekatan yang sederhana dalam implementasi.Adapun pendekatan yang diambil adalah sbb.:1. Berdasarkan prinsip kerja dari sistem multi agen berparameter yang diacu, digunakanprinsip interleaving, yang berarti agen akan bekerja secara bergiliran, setiap saat hanya adamaksimal satu agen yang aktif.2. Penjadwalan menggunakan prinsip ring counter dan token based yaitu setiap agen akandiberi nomor identifikasi dan pengaktifan agen dilakukan secara berurutan mulai darinomor terkecil sampai terbesar, setelah itu kembali ke nomor terkecil dst. Untukmemberitahu kapan sebuah agen aktif, digunakan token. Agen yang sedang memegangtoken berhak untuk melakukan aktivitas. Jika aktivitasnya telah selesai, agen akanmemberikan token tersebut ke agen berikutnya.3. Komunikasi antar agen, dalam hal ini adalah pemberian token kepada agen berikutnya,dilakukan secara tidak langsung, yaitu melalui koordinator (mediator). Dapat dikatakanbahwa koordinator inilah yang berfungsi untuk mengatur giliran agen.Dengan pendekatan tersebut, maka arsitektur sistem multi agen yang digunakan pada frameworkyang dibangun dapat dijelaskan secara sederhana seperti pada gambar 4.2.KoordinatorAgen 1Agen 2.Agen nGambar 4.2 Arsitektur Sistem Multi Agen.xix
Gambar 4.3 adalah diagram kelas dari sistem yang dikembangkan. Terdapat sembilan kelas yaituBox, Cell, Environment, List, ListElement, Position, Robot, Scheduler, dan Sudoku. Penjelasandari masing-masing kelas adalah sebagai berikut diberikan pada ttersebut adalah sbb.:Gambar 4.3. Diagram Kelas.Daftar atribut dan metode dari masing-masing kelasKelas BoxBox adalah kelas yang merepresentasikan kotak pada permasalahan block-worldproblemAtribut int Valuemenyimpan nilai kotak int agentTypemenyimpan tipe agenMetode Box (int v)Mendefinisikan sebuah Box dengan Value v. Box (int v, int a)Mendefinisi sebuah Box dengan Value v dan agentType a. int getValue()Mengembalikan Value dari sebuah Box. void setValue(int v)Mengisi Value dengan v.xx
int getAgentType()Mengembalikan agentType dari sebuah Box.void setAgentType(int a)Mengisi agentType dengan a.void printBox()Mencetak informasi dari sebuah Box.void printValue()Mencetak Value dari sebuah Box.Kelas CellCell adalah kelas yang merepresentasikan kotak pada papan permainan Sudoku.Atribut Box boxMenyimpan box yang diletakkan pada sebuah sel. Boolean fixedApakah isi sel tetap atau bisa berubah. Position posMenyimpan posisi sel pada papan Sudoku.Metode Cell()Mendefinisikan sebuah sel kosong. Cell (int x, int y)Mendefinisikan sebuah sel pada posisi (x,y). Cell (int x, int y, int v)Mendefinisikan sebuah sel pada posisi (x,y) dengan nilai box v. Cell (Position p)Mendefinisikan sel kosong pada posisi p. Cell (Position p, Box b)Mendefinisikan sebuah sel pada posisi p dengan box b. Box getBox()Mengembalikan box dari sebuah sel. Position getPosition()Mengembalikan posisi sebuah sel. boolean isFixed()Mengembalikan nilai fixed. boolean isEmpty()Menguji apakah sel sudah terisi box atau belum. void setBox(Box b)Mengisi sel dengan box b. void setEmpty()Mengosongkan sel. void setFixed()Sel tidak boleh berubah. void setPosition(int x, int y)Menetapkan posisi sebuah sel. void printCell()Mencetak informasi sebuah sel.xxi
Kelas EnvironmentEnvironment adalah kelas yang menyimpan informasi tentang lingkungan permainanSudoku.Atribut int SIZEUkuran papan Sudoku. int numbers []Banyaknya kota pada setiap tumpukan. List FreeCellListDaftar sel yang masih kosong. Cell [][] BoardPapan Sudoku. Box [][] bStackTumpukan kotak di luar papan Sudoku. boolean backtrackIndikator terjadi backtrack.Metode Environment()Mendefinisikan sebuah lingkungan permainan Sudoku. boolean isValidCell(int i, int j)Menguji apakah sel pada posisi (i,j) adalah sebuah sel yang valid. boolean isValidPuzzle()Menguji apakah puzzle valid atau tidak. void SetupBoxStacks()Mendefinisikan tumpukan kotak di luar papan Sudoku. boolean isValidNumber(int x)Menguji apakah x adalah nilai kotak yang valid. boolean emptyStacks()Menguji apakah seluruh tumpukan kotak kosong. boolean isInRow(int x, int id)Menguji apakah sebuah row x mengandung angka id. boolean isRowFull(int x, int y)Menguji apakah seluruh baris pada subblok (x,y) sudah terisi kotak. boolean isColumnFull(int x, int y)Menguji apakah seluruh kolom pada subblok yang mengandang posisi (x,y)sudah terisi kotak. boolean isInColumn(int x, int id)Menguji apakah sebuah kolom mengandung angka id. boolean isInSubblock(Position p, int id)Menguji apakah sebuah subblok yang mengandung posisi p terdapat kotakdengan angka id. boolean isSolved()Menguji apakah permainan Sudoku sudah terpecahkan. int getSize()Mengembalikan ukuran papan Sudoku. boolean readAPuzzle(String fileName)Membaca permainan Sudoku dari file. void setBacktrack (boolean b)Memberi nilai backtrack dengan nilai b. boolean isBacktrack()Menguji apakah backtrack bernilai true. void printBoard()Mencetak isi papan Sudoku.xxii
Kelas ListKelas list digunakan untuk menyimpan daftar sel.Atribut int firstIndeks elemen pertama list. int lastIndeks elemen terakhir list. int lengthPanjang list. ListElement[] ContentIsi list.Metode List (int size)Mendefinisikan list dengan ukuran size. int getFirst()Mengembalikan indeks elemen pertama. void setFirst (int i)Menetapkan indeks elemen pertama. int getLast()Mengembalikan indeks elemen terakhir. void setLast(int i)Menetapkan indeks elemen terakhir. int getLength()Mengembalikan panjang list. void decLength()Mengurangi panjang list dengan satu. ListElement [] getContent()Mengembalikan isi list. ListElement getFirstElement()Mengembalikan elemen pertama list. ListElement getElement (int i)Mengembalikan elemen list ke-i. void InsertLastElement (Cell c)Menyisipkan sel c ke akhir list. void InsertFirstElement (Cell c)Menyisipkan sel c di awal list. void InsertElement (Cell c)Menyisipkan sel c kedalam list. void InsertLast (Cell c)Menyisipkan sel c di akhir list dengan menguji kondisi list terlebih dulu. boolean InsertElement (ListElement le)Penyisipan elemen pada proses backtrack. int findPosition (ListElement le)Mencari indeks sebuah elemen list. void delFirst()Menghapus elemen pertama list. void pushElement (Box b)Menyisipkan elemen dengan isi box b ke akhir list.xxiii
Kelas ListElementKelas ListElement merepresentasikan isi list.Atribut Cell cellSel yang disimpan oleh elemen list. int nextindeks dari elemen di belakangnya.Metode ListElement (Cell c, int n)Mendefinisikan sebuah elemen list berisi cell c dan next n. Cell getCell()Mengembalikan cell dari elemen list. Int getNext()Mengembalikan next dari elemen list. void setNext(int i)Menetapkan nilai next dengan i.Kelas PositionKelas Position merepresentasikan sebuah posisi di papan Sudoku.Atribut int posXBaris pada papan Sudoku. int posYKolom pada papan Sudoku.Metode Position (int x, int y)Mendefinisikan sebuah posisi pada baris x dan kolom y. int getPosX()Mengembalikan baris. int getPosY()Mengembalikan kolom. void setPosX (int x)Menetapkan baris. void setPosY (int y)Menetapkan kolom.Kelas RobotKelas Robot merepresentasikan agen/robot dari block-world problem.Atribut Thread tThread dari robot. String threadNameNama thread. int typeTipe agent/robot. Sudoku SPermainan Sudoku. Cell resCellSel hasil pencarian untuk ditempati sebuah kotak dengan nomor tertentu.xxiv
Metode Robot (Sudoku S, int i)Mendefinisikan sebuah robot dari permainan S dan bertipe i. void start() thread getThread()Mengembalikan thread. void run()Menjalankan/mengaktifkan robot. boolean putOn()Mencari sel yang dapat diisi dengan kotak dengan nomor tertentu. boolean takeBack()Mengambil sebuah kotak dari papan Sudoku. boolean Action()Aksi dari robot. int getValidNumber(ListElemen le) ListElement getValidFreeCell()Mengembalikan sebuah isi list yang kotaknya dapat diletakkan pada papanSudoku.boolean isValidPosition (Position pos)Menguji apakah pos adalah sebuah posisi yang valid.Kelas SchedulerKelas Scheduler merepresentasikan agen yang mengatur giliran kerja dari agen.Atribut int turn boolean [] hasTurn boolean [] resAction int [] boxes Sudoku sudokuMetode Scheduler (Sudoku S)Mendefinisikan sebuah Scheduler untuk permainan Sudoku S. int getTurn()Mengembalikan giliran saat itu. void setTurn()Menetapkan giliran. void nextTurn()Meneruskan giliran. void setHasTurn(int i)Menetapkan urutan berikutnya dari sebuah agen. void setResAction (int i, boolean res)Menetapkan aksi yang dilaksanakan oleh agen. boolean parAction ()Aksi-aksi yang dapat dilaksanakan oleh para agen.xxv
Kelas SudokuKelas Sudoku adalah kelas utama yang merepresentasikan permainan Sudoku.Atribut int modelModel yang digunakan. int agentNumBanyaknya agen yang digunakan. String fileNameFile permainan Sudoku. Environment PuzzleEnvironment. Robot [] AgentAgen-agen yang digunakan. Scheduler schScheduler dari permainan Sudoku.Metode Sudoku ()Mendefinisikan Sudoku standar. Sudoku (int model)Mendefinisikan Sudoku dengan model tertentu. Sudoku (int model, String fN)Mendefinisikan Sudoku dengan model tertentu dan puzzle diambil dari filefN. void setModel (int m)Menentukan model yang digunakan. void defineAgents()Mendefinisikan agen-agen yang digunakan. void killAgents()Menghapus agen-agen yang digunakan. void loadPuzzle()Mengambil permainan Sudoku. void main(String [] args)Memulai program. Scheduler getScheduler()Mengembalikan Scheduler dari permainan Sudoku. Environment getEnvironment()Mengembalikan Environment dari permainan Sudoku. int getModel()Mengembalikan model yang digunakan. int getAgentNum()Mengembalikan jumlah agen. void run()Menjalan agen-agen.4.3 I
mencoba setiap model pada sekumpulan soal Sudoku. 1.3 Tujuan Tujuan dari penelitian ini adalah 1. Mengembangkan framework Sudoku Solver. 2. Mengembangkan prototype Sudoku solver berdasarkan model yang telah dihasilkan sebelumnya, dimana Sudoku dimodelkan sebagai permasalahan Block-World Problem. 3.
