1

BAB I

PENDAHULUAN

1.1 Latar Belakang Masalah

Sudoku adalah logical puzzle yang umumnya berukuran 9 x 9, seperti

gambar 1.1. Sudoku ini terdiri dari 9 baris, 9 kolom, dan 9 blok. Dari 9 baris dan

9 kolom tersebut akan terbentuk 81 kotak. Tiap 3 x 3 kotak diberi batas dan

dinamakan blok. Tugas pemain adalah melengkapi angka-angka, dari 1 sampai 9

di 81 kotak tersebut. Aturannya adalah pada tiap baris, kolom, dan blok tidak ada

angka yang sama. Teknik yang digunakan untuk melengkapi Sudoku teknik

Eliminasi. Ada beberapa teknik Elminasi, seperti Hidden Single, Naked Pair,

Triple Pair, dan yang lainnya.

6 1 4 5

8 3 5 6

2 1

8 4 7 6

6 3

7 9 1 4

5 2

7 2 6 9

4 5 8 7

Gambar 1.1 Sudoku

Constraint Statification Problem (CSP) merupakan salah satu jenis

pemodelan problem solving pada AI. Dengan memodelkan Sudoku sebagai CSP,

komputer akan menyelesaikan Sudoku dengan logika. Teknik CSP yang

digunakan untuk menyelesaikan Sudoku adalah metode Arc-consistency. Pada

kasus Sudoku, cara kerja metode Arc-consistency ini sama dengan teknik

2

Eliminasi, yaitu dengan mengeliminasi angka-angka yang tidak mungkin menjadi

jawaban. Merode Arc-consistency adalah teknik pemangkasan ruang cari solusi.

1.2. Perumusan Masalah

Berdasarkan latar belakang masalah di atas, maka dapat dirumuskan

beberapa masalah sebagai berikut :

- Bagaimana Sudoku dimodelkan sebagai CSP?

- Bagaimana algoritma Arc-Consistency (AC), yang meliputi General Arc-

Consistecy (GAC) dan Shaving General Arc-Consistency (SGAC) atau

teknik Eliminasi dipakai untuk menyelesaikan soal Sudoku?

1.3. Batasan Masalah

Batasan – batasan masalah dalam pembuatan permainan Sudoku adalah

sebagai berikut :

- Permainan Sudoku yang diselesaikan hanya Sudoku berukuran 4 x 4 dan

9 x 9.

- Metode yang digunakan adalah Arc-Consistency, yang meliputi General

Arc Consistency dan Shaving General Arc Consistency.

- Teknik shaving atau teknik Eliminasi yang dipakai, meliputi Hidden

Single, Locked Candidate, Naked Pair, Naked Triple, dan Hidden

Pair.

- Metode penyusunan soal tidak dibahas secara mendetail, metode yang

digunakan hanya brute force.

1.4. Tujuan Penelitian

Tujuan dari penulisan tugas akhir ini adalah :

- Sebagai syarat kelulusan yang ditetapkan oleh universitas.

- Memodelkan permainan Sudoku menjadi model CSP.

3

- Menerapkan algoritma AC, yaitu GAC dan SGAC pada permainan

Sudoku.

- Sebagai alternatif lain untuk menyelesaikan permainan Sudoku yang

sudah ada, yaitu menyelesaikan Sudoku tanpa metode pencarian.

1.5. Metode / Pendekatan

Melalui studi literatur dari modul – modul maupun literatur atau pustaka

yang berkaitan dengan permainan maupun algoritma yang digunakan untuk

membuat sistem ini.

Melakukan percobaan untuk pengujian kepada user setelah sistem jadi

untuk mengetahui apakah sistem sudah berjalan dengan baik atau belum.

Untuk memperlajari CSP, maka digunakan contoh kasus Sudoku. Maka

dalam pembuatan permainan Sudoku ini, terlebih dahulu Sudoku dimodelkan

secara CSP. Kemudian metode-metode problem solving pada CSP diterapkan

pada Sudoku. Metode problem solving pada CSP yang digunakan adalah teknik

tanpa pencarian. Metode pertama adalah GAC. Metode berfungsi untuk

menggurangi ruang cari. Kemudian ruang cari dipangkas lagi dengan metode

SGAC. Pemangkasan ruang cari dilakukan sampai Sudoku terisi semuanya.

Dengan demikian Sudoku terselesaikan tanpa pencarian.

1.6. Sistematika Penulisan

Sistematika penulisan dalam tugas akhir ini adalah sebagai berikut :

Bab I. Pendahuluan : Berisi tentang apa yang melatarbelakangai

penelitian ini, mengapa perlu untuk diadakan penelitian dan membahas

metode apa yang digunakan untuk melakukan penelitian.

4

Bab II. Landasan Teori : Berisi tentang tinjauan pustaka yang memuat

teori – teori yang akan digunakan dalam penelitian. Dan bagaimana teori

tersebut akan diterapkan pada penelitian

Bab III. Perancangan Sistem : Berisi tentang rancangan – rancangan form

input, proses dan output dari sistem yang akan dibuat , flowchart dari alur

kerja sistem. Berserta contoh langkah – langkah yang akan dilakukan

dalam proses.

Bab IV. Implementasi dan Analisis Sistem : Berisi tentang

pengimplementasian rancangan ke dalam sistem disertai dengan analisis

hasil penelitian dengan melibatkan sampel dari luar untuk menguji sistem.

Bab V. Kesimpulan dan Saran : Berisi tentang kesimpulan dari hasil

penelitian yang dilakukan dan saran – saran untuk pengembangan sistem

dimasa yang akan datang.