Tugas ke-4 dibawah ini dibuat untuk
memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan ( AI ) yang diampu oleh
Mia Kamayani ST,MT.
“ SUDOKU dengan BACKTRACKING ”
SUDOKU
Sudoku adalah permainan teka-teki
angka yang terdiri dari 81 kotak (9 x 9) yang berisi angka-angka antara 1
sampai 9 yang harus diisi penuh pada setiap kotaknya. Tujuan permainan ini
adalah refreshing dengan mengasah otak. Pemain sudoku diharuskan untuk mengisi
semua kotak kosong yang tersedia sedemikian setiap angkanya akan unik pada
baris, kolom, dan daerahnya (akan dijelaskan). Contoh sudoku dapat dilihat pada
gambar 1. Saat pertama memainkan sudoku, beberapa kotak sudah diisi angka yang
merupakan hints untuk mengisi kotak kosong lain hingga penuh. Pada gambar di
bawah, dapat kita lihat bahwa adanya perbedaan tebal garis kotak. Garis tebal
kotak menandakan batas daerah unik yang harus diisi angka yang unik dari 1-9.
Daerah unik terdiri dari 9 kotak (3x3). Sebagai contoh, Daerah unik pada posisi
terkiri-teratas terdiri dari angka 5,3,6,9, dan 8, untuk itu 4 kotak kosong
lain harus diisi dengan angka unik selain angka sudah ada pada daerah itu yaitu
1,2,4, dan 7. Setiap angka yang diisi pada suatu kotak harus unik secara
horizontal, vertikal, dan daerahnya. Kita harus mencari semua nilai yang unik
pada setiap kotak dengan strategi tertentu sehingga semua kotak kosong terisi
oleh angka.
Hasil
penyelesaian kasus sudoku pada gambar 1 ini dapat dilihat pada gambar 2 di
bawah ini. Angka yang berwarna merah adalah angka yang kita isikan pada kotak
kosong sudoku. Semua angka pada kotak sudoku memiliki nilai yang unik pada
baris, kolom, dan daerahnya. Dengan demikian sudoku telah berhasil
terselesaikan.
ALGORITMA DFS DAN BACKTRACKING
Pencarian
solusi Algoritma DFS menggunakan pendekatan pencarian solusi penelusuran solusi
pohon dinamis. Pada umumnya struktur pohon yang digunakan adalah pohon berakar.
Pencarian Solusi dilakukan dengan mengunjungi semua simpul pada pohon. Setiap
simpul diperiksa untuk memastikan apakah solusi telah dicapai. Pohon dibentuk
dengan dinamis selama solusi berlangsung. Bila sebuah simpul yang dibentuk
tidak mengarah ke solusi, maka pencarian solusi dilanjutkan dengan membentuk
simpul berikutnya. Teknik penelesuruan simpul yang digunakan pada algoritma DFS
adalah penelesuran “Mendalam”. Pencarian solusi dengan DFS dicirikan dengan
ekpansi simpul-simpul terdalam lebih dahulu. Mula-mula simpul akar dibangkitkan
pertama kali, kemudian sebuah simpul pada aras kedua, lalu sebuah simpul di
aras ketiga, dan seterusnya. Jadi, pencarian mengikuti sebuah lintasan tunggal
mulai dari simpul akar terus menurun ke “Bawah” ke simpul-simpul pada aras di
bawahnya. Sebagai contoh dapat dilihat pada gambar 3. Urutan penelesuran simpul
dapat dilihat pada angka yang muncul pada simpul tersebut. Definisi Kedalaman
(deept) atau tinggi (heigth) pohon berakar berdasarkan bahwa kedalaman simpul
akar adalah 0 dan kedalaman simpul lainnya adalah 1 + kedalaman simpul orang
tuanya. Model Pencarian solusi dengan melakukan penelesuran pada struktur pohon
ada juga yang dilakukan dengan cara “Melebar” yang biasa disebut Algoritma BFS.
Namun, Algoritma tersebut memiliki kelemahan yaitu lamanya waktu yang
dibutuhkan untuk menuju simpul solusi. Untuk itu penulis lebih prefer untuk
menggunakan algoritma pencarian solusi dengan DFS saja.
Penelusuran semua simpul pada DFS
jika dituliskan dengan bahasa pseudocode adalah sebagai berikut :
Procedure
DFS (input V : integer)
{mengunjungi
seluruh simpul graf dengan algoritma pencarian DFS
Masukan
: V adalah simpul awal kunjungan
keluaran
: Semua simpul yang dikunjungi ditulis layar
}
Deklarasi
w
: integer
Algoritma
write(v)
dikunjungi[v]
<- true
for
tiap simpul w yang bertetangga dengan simpul V do
if
not dikunjungi[w] then
DFS(w)
endif
endfor
|
Pencarian solusi dengan metode DFS
dilakukan dengan prosedur atau langkah-langkah sebagai berikut (Secara umum) :
1) Masukan simpul akar ke dalam
antrian Q. Jika simpul akar adalah simpul tujuan (goal node), maka solusi telah
ditemukan. Stop.
2) Jika Q kosong, tidak ada solusi.
Stop
3) Ambil simpul v dari kepala (head)
antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali
ke langkah 2.
4) Bangkitkan semua anak dari simpul
v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak
dari v di awal antrian Q.
5) Jika anak dari simpul v adalah
simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke
langkah 3.
Pada
dasarnya penerapan pohon DFS dengan backtracking hanya memerlukan sedikit
modifikasi saat terjadi deadend pada simpul. Jika simpul v tidak dapat
menciptakan simpul baru namun simpul v tersebut bukan merupakan solusi dari
persoalaan, maka simpul v dikatakan mencapai kondisi deadend. Simpul v akan
melakukan runut balik pada orang tua simpul v terdekatnya untuk menciptakan
simpul baru w yang setara kedalamannya dengan simpul v. Simpul w akan
bangkitkan semua anaknya untuk melakukan penelusuran solusi.
ALGORITMA untuk penerapan SUDOKU
dengan BACKTRACKING
Program
C++ ini menunjukkan Soal Sudoku menggunakan Backtracking.
Berikut adalah kode sumber C ++
Program untuk memecahkan Sudoku Masalah menggunakan backtracking. C ++
program berhasil dikompilasi dan dijalankan pada sistem Linux. Program
output juga ditunjukkan di bawah ini.
/*
* C++ Program to Solve Sudoku Problem using BackTracking
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define UNASSIGNED 0
#define N 9
bool
FindUnassignedLocation(int grid[N][N], int &row, int &col);
bool isSafe(int grid[N][N], int row, int col, int num);
/* assign values to all unassigned locations for Sudoku
solution
*/
bool SolveSudoku(int grid[N][N])
{
int row, col;
if (!FindUnassignedLocation(grid, row, col))
return true;
for (int num = 1; num <= 9; num++)
{
if (isSafe(grid, row, col, num))
{
grid[row][col] = num;
if (SolveSudoku(grid))
return true;
grid[row][col] = UNASSIGNED;
}
}
return false;
}
/* Searches the grid to find an entry that is still unassigned. */
bool
FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}
/* Returns whether any assigned entry n the specified row matches
the given number. */
bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry in the specified column
matches
the given number. */
bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry within the specified 3x3 box
matches
the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
/* Returns whether it will be legal to assign num to the given row,col
location.
*/
bool isSafe(int grid[N][N], int row, int col, int num)
{
return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row % 3 , col - col % 3, num);
}
/* print grid */
void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
cout<<grid[row][col]<<" ";
cout<<endl;
}
}
/* Main */
int main()
{
int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}};
if (SolveSudoku(grid) == true)
printGrid(grid);
else
cout<<"No solution exists"<<endl;
return 0;
}
|
Constraint
Satisfaction Problem terdiri dari 3 komponen:
o
Set
variabel = Kotak yang sudah diisi angka yang merupakan hints untuk mengisi
kotak kosong lain hingga penuh.
o
Set
domain = Angka-angka berwarna merah.
o
Set
constraint/batasan = Semua angka pada kotak Sudoku harus memiliki nilai yang
unik pada baris, kolom, dan daerahnya. Dengan demikian sudoku telah berhasil
terselesaikan.
Definisi problem 4 items :
1. Initial State :
2. Successor Function : angka yang
diisi dari baris teratas lalu diisi dari kiri ke kanan kemudian berpindah baris
lagi sampai semua kotak kosong terisi angka unik.
3.Path cost : menurut ( baris, kolom )
dalam suatu kumpulan kotak pada Sudoku.
4. Goal State :
SUMBER :
