SISTEM PEMECAHAN MASALAH SODOKU - Kecerdasan Buatan

PENDAHULUAN

                       

1.1  Latar Belakang

Kecerdasan buatan (Artificial Intelligence) merupakan sistem yang berpikir dan bertindak   seperti   manusia  atau   secara   rasional   (Russel,1995). Kecerdasan buatan dapat digunakan untuk menyelesaikan persoaalan-persoalan yang dapat diselesaikan oleh manusia. Persoalan-persoalan tersebut dapat berbentuk permainan kecerdasan seperti catur, Sudoku dan permainan-permainan lain. Sudoku merupakan salah satu jenis kecerdasan, dimana pemain harus menempatkan angka-angka (dari “1” sampai “9”angka) pada kotak-kotak yang  disediakan dengan aturan angka tersebut tidak boleh ada yang sama dalam 1 baris, kolom dan blok diposisinya berada.

Sudoku adalah suatu permainan teka-teki yang berasal dari Jepang. Permainan ini mengharuskan pemain mengisi sejumlah kotak-kotak kecil sebanyak 9 dengan angka dari 1 sampai 9 dengan memenuhi syarat permainan. Syarat pengisian kotak-kotak tersebut adalah :

1. Tidak boleh ada angka yang berulang dalam suatu  baris, dan dalam satu baris harus ada angka 1 sampai 9.
2. Tidak boleh ada angka yang berulang dalam suatu kolom, dan dalam satu kolom harus ada angka 1 sampai 9.
3. Tidak boleh ada angka yang berulang dalam  kotak besar, dan dalam satu kotak besar harus ada angka dari 1 sampai 9.
4. Sebuah kotak besar adalah kumpulan 9 kotak kecil yang membentuk kotak yang lebih besar  dan dalam permainan terdapat 9 kotak besar.

Sudoku bukan merupakan permainan matematis, melainkan permainan logika, walaupun didalam permainan,  pemain mengisikan   angka-angka kedalam papan permainan. Adapun aplikasi yang dapat menyelesaikan permainan dengan menggunakan metode algoritma Best First Search (BFS).

Algoritma Best First  Search merupakan   sebuah   algoritma   yang   dapat digunakan   untuk   mencari   sebuah   penyelesaian   dari   permasalahan.   Permasalahan yang diselesaikan dengan metode Best First Search memiliki keadaan sementara yang dihasilkan oleh   kejadian,  yang menghasilkan beberapa   keadaan   lain   yang memiliki bobot. Bobot ini akan digunakan sebagai penentu pilihan yang dilakukan oleh algoritma Best First Search. Persoalan sudoku   memiliki keadaan sementara yaitu pengisian sebuah angka disetiap kotak kosong dengan bobot, yaitu banyaknya kemungkinan angka yang dapat diisikan kedalam kotak kosong lain, setelah jawaban sementara tersebut diterima.

1.1  Rumusan Masalah

Pembahasan penulis mengenai penerapan Best First Search dalam penyelesaian permainan Sudoku dirumuskan dalam rumusan masalah, “Bagaimana menerapkan algoritma Best First Search dalam penentuan angka untuk menyelesaikan permainan Sudoku?”.

1.2  Batasan Masalah

Adapun batasan masalah pada pemecahan masalah metode Sodoku. pengguna berperan sebagai pemberi masalah dan program akan berperan sebagai penyelesai masalah.

BAB II

PEMBAHASAN

2.1  Metode Proses Pemecahan

Soal Pada proses input masalah/soal sudoku, program mengambil hasil input dari user dengan menggunakan bahasa pemrograman HTML dan kemudian data tersebut disusun   ke   dalam   sebuah   array   2   dimensi   dimana   urutan   atau   dimensi   dari   array tersebut merupakan koordinat dari lokasi cell pada tampilan data. Contohnya adalah seperti bilangan dibawah ini  dan dapat dibuat susunan array seperti berikut :

cell [1][1] = 0

cell [1][2] = 0

cell [1][3] = 4

cell [1][4] = 0

cell [1][5] = 5

cell [1][6] = 3

cell [2][1] = 0...

2.1  Pemeriksaan Nilai Heuristik Pada Tiap Kotak

Pada program ini, nilai heuristik yang digunakan adalah jumlah kemungkinan angka yang diperbolehkan dalam satu kotak. Berdasarkan gambar/bilangan diatas, dapat diketahui bahwa angka-angka yang diperbolehkan untuk mengisi cell   [1][1]   adalah   2   dan   6. Sehingga   didapat   jumlah kemungkinan  angka   pada cell [1][1]   adalah   2.  Berdasarkan   contoh  tersebut, dapat disimpulkan bahwa semakin kecil jumlah angka yang diperbolehkan dalam pengisian, maka peluang terjadinya kesalahan dalam pengisian akan semakin kecil pula.

Proses pemeriksaan nilai heuristik pada program akan berjalan terus-menerus memeriksa kemungkinan angka-angka pada setiap kotak-kotak yang kosong. Setelah itu, program akan membandingkan tiap-tiap kemungkinan pada masing-masing kotak kosong   untuk   memilih   kotak   mana   yang   memiliki   nilai   heuristic yang paling baik sehingga diketahui kotak mana yang   harus di isi terlebih dahulu dengan cara menyimpan lokasi koordinat dari kotak yang akan di isi nilainya.

2.2  Sejarah Sodoku

Sudoku memiliki sejarah yang menarik. Teka-teki angka pertama muncul dalam surat kabar pada akhir abad ke-19 Prancis 1892. Seiring berjalannya pekembangan permainan sodoku, beberapa tahun kemudian, Wayne Gould seorang pensiunan hakim dari Hong Kong yang aslinya berasal dari Selandia Baru mengembangkan permainan Sudoku menjadi program/games komputer.

Dan pada tahun 2005, untuk pertama kalinya permainan Sudoku menjadi bagian dari acara TV berjudul Sudoku Show, Sudoku Live. Permainan ini sangat popular di Jepang dan meluas hingga ke seluruh dunia. Di Indonesiapun permainan ini banyak digemari oleh para pecinta permainan teka-teki.

2.3  Aturan Permainan Sudoku

Aturan permainan untuk puzzle ini sangat sederhana, untuk menyelesaikan permainan ini tidak diperlukan pengetahuan umum, kepandaian atas bahasa tertentu, juga kemampuan matematika. Tetapi hanya memerlukan kecermatan, kesabaran, dan logika. Papan Sudoku terbuat dari sembilan buah kotak berukuran 3×3 (disebut blok/subgrid ) yang disusun sedemikian rupa sehingga menghasilkan kotak besar berukuran 9×9. Beberapa kotak sudah diisi sebagai petunjuk awal dan tugas pemain adalah melengkapi angka-angka pada kotak yang lain sehingga keseluruhan papan permainan terisi angka secara lengkap. Aturan permainannya sangatlah sederhana:

1. Kotak-kotak pada setiap baris, kolom, dan blok/subgrid  harus berisi sebuah angka – angka.
2. Angka-angka yang diisikan harus unik dari 1 hingga 9 sehingga dalam 1 blok/subgrid hanya terdiri atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1 baris maupun kolom.

Angka-angka ini sebenarnya tidak memilki hubungan aritmetis satu samalain. Anda boleh menggantinya dengan 9 huruf, lambang, atau warna yang berbeda. Tujuannya adalah untuk mengisi Sembilan grid sehingga tiap kolom mengandung angka satu sampai sembilan masing-masing hanya satu kali, dimana tiap-tiap grid juga mengandung angka satu sampai sembilan.

Hal yang membuat permainan Sudoku menarik adalah Sudoku memiliki peraturan yang mudah untuk dimengerti, tetapi untuk mendapatkan jawaban yang benar dan tepat ternyata sangat kompleks dan tidaklah mudah. Tingkat kesulitan pada permainan Sudoku dapat juga disesuaikan dengan kemampuan dari pemain.

BAB III

PENUTUP

3.1  Kesimpulan

Pencarian solusi suatu permasalah dengan menggunakan Permainan Sodoku dapat meningkatkan logika/cara berfikir ataupun, memerlukan kecermatan, melatih sabar, tepat dalam menyelesaikan suatu permasalahan.

Adapun keterkaitan sodoku terhadap Kecerdasan Buatan, menjadi suatu pola Ilmu pengetahuan yang saling berhubungan untuk memecahkan persoalan/masalah yang rumit dengan langkah-langkah tertentu.

3.2  Saran

Keseluruhan isi dari makalah ini harus dibaca dan dimengerti agar pembaca, baik itu mahasiswa, maupun pengajar (dosen) dapat mamahami konsep dan penerapan dari metode pemecahan masalah Sodoku.