Constraint Satisfaction Problems (CSP) Game Sudoku ~ Dey's

Constraint Satisfaction Problems merupakan pengertian problem matematika yang dijadikan sebagai sekumpulan objek yang harus memenuhi beberapa batasan. CSP juga mewakili mewakili entitas dalam masalah sebagai sekumpulan kendala terbatas yang homogen terhadap variabel, yang diselesaikan oleh metode constraint satisfaction. CSP merupakan subjek dari riset intensif dalam artificial intelligence dan operations research, sejak sejak regularitas dalam formula mereka melengkapi basis dari analisis dan menyelesaikan masalah dari banyak unrelated family. CSP sering menunjukan kompleksitas yang tinggi, membutuhkan kombinasi dari metode heuristics dan combinatorial search untuk diselesaikan dalam waktu yang wajar. Boolean satisfiability problem (SAT), Satisfiability Modulo Theories (SMT) dan Answer set Programming (ASP) secara kasar dapat dianggap sebagai beberapa bentuk dari Constraint Satisfaction Problem.

Contoh masalah simpel yang dapat dibentuk menjadi Constraint Satisfaction Problem,

- Eight queens puzzle ,

- Map coloring problem ,

- Crosswords, Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato dan masih banyak yang lainnya.

Game Sudoku juga termaksuk contoh dari CSP, Sudoku dikenal sebagai Number Place atau Nanpure, adalah sejenis teka-teki logika. Tujuannya adalah untuk mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

Untuk memecahkan teka-teki Sudoku, dapat digunakan Algoritma Backtracking

(runut-balik). Algoritma ini merupakan perbaikan dari Algoritma Brute Force, dimana solusi dapat ditemukan dengan penelusuran yang lebih sedikit dan dapat mencari solusi permasalahan secara lebih efektif karena tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang perlu dipertimbangkan.

Komponen Constraint Satisfaction Problem pada Game Sudoku :

> Variabel : Angka 1-9.

> Domain : Terdapat 9x9 kotak.

> Constraint : Mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

Definisi masalah pada game Sudoku tersebut yaitu:

A.) Initial state ( keadaan awal).

Sudoku terdiri dari 3x3 kotak, masing-masing terbagi lagi menjadi 9x9 kotak lebih kecil yang terdapat beberapa angka 1-9 secara acak.

B.) Successor function.

Mengisikan angka-angka dari 1 sampai 9 ke dalam jaring-jaring 9×9 yang terdiri dari 9 kotak 3×3 tanpa ada angka yang berulang di satu baris, kolom atau kotak.

C.) Goal test.

Akhir pada game Sudoku semua kotak terisi penuh dengan angka tanpa ada angka yang sama.

D.) Path cost.

Pada game Sudoku terdapat 9 proses untuk menyelesaikan game.

1.) Pencarian sel yang kosong.

Sel pertama yang kosong adalah pada baris ke-1 kolom ke-2.

2.) Angka yang akan diisikan adalah 1,2,3,4,5,6,7,8,9.

3.) Pencarian kandidat angka yang akan diisikan.

Kandidat angka yang mungkin adalah sebagai berikut:

Baris ke-1, kolom ke-2 (S1,2)

a. Kandidat yang mungkin pada baris ke-1, B={3,6,9}

b. Kandidat yang mungkin pada kolom ke-2, K={3,4,7,8,9}

c. Kandidat yang mungkin pada blok ke-1, G={1,5,7,9}

4.) Pengecekan.

Pengecekan dapat direpresentasikan dengan himpunan seperti pada gambar

berikut:

Himpunan A = {3,6,9}

Himpunan B = {3,4,7,8,9}

Himpunan C = {1,5,7,9}

A ∩ B ∩ C = {9}

Jadi, solusinya adalah 9.

5.) Solusi diisikan pada sel tersebut.

6.) Selanjutnya melakukan pencarian sel yang kosong berikutnya yaitu sel pada

baris ke-1 kolom ke-6. Proses dilakukan berulang-ulang sampai didapatkan

solusi untuk sel yang kosong pada baris ke-1:

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

7.) Pencarian solusi pada baris ke-2 akan dihadapkan pada kasus yang berbeda yaitu terdapat himpunan solusi yang lebih dari satu. Dalam hal ini akan dilakukan

backtrack ke kandidat angka yang lain. Hasil pengecekan berupa himpunan

solusi akan disimpan yang kemudian dapat digunakan untuk proses

backtracking.

Pencarian kandidat angka untuk baris ke-2:

S2,2 = {7}, S2,3 = {1,5}, S2,5 = {6,8,9}, S2,6 = {2,6,8,9},

S2,7 = {6,9}, S2,8 = {5,6}, S2,9 = {5}

8.) Selanjutnya dilakukan backtrack berdasarkan himpunan solusi yang telah ada

untuk masing-masing sel. Sehingga didapatkan solusi:

S2,2 = {7}, S2,3 = {1}, S2,5 = {8}, S2,6 = {2}, S2,7 = {9}

S2,8 = {6}, S2,9 = {5}