Pemrograman Internet: ALGORITMA BACKTRAKING

ALGORITMA BACKTRAKING

Abstrak

Setiap manusia ingin menyelesaikan permasalahan yang dihadapi dengan secepat-cepatnya dan mendapatkan keuntungan sebanyak-banyaknya dengan mengefisienkan sumber daya yang dimiliki terhadap batasan-batasan yang ditemui pada suatu masalah. Khususnya permasalahan yang selalu terdapat pada bidang informatika adalah pencarian metode atau algoritma yang lebih mangkus untuk mencapai solusi. Oleh karena itu dibutuhkan langkah-langkah tertentu yang dapat dijadikan acuan untuk membantu pemecahan masalah tersebut. Salah satunya adalah pemecahan algoritma runut balik (backtracking) yang sering digunakan untuk membuat program khususnya permainan dan kecerdasan buatan. Algoritma-algoritma selain runut balik pun sebenarnya cukup mangkus untuk mencari solusi di antara kemungkinan solusi yang ada. Akan tetapi, waktu komputasi yang dibutuhkan algoritma lain biasanya akan meningkat dengan drastis seiring dengan pertambahan ukuran persoalan yang membesar. Karena itulah dibutuhkan metode untuk lebih memangkuskan algoritma tersebut. Salah satu metode yang dapat digunakan adalah menggunakan metode runut balik. Runut balik itu sendiri adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus. Dengan metode runut balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.

1 Algoritma Runut Balik (backtracking)

Algoritma runut balik pertama kali diperkenalkan oleh D.H Lehmer pada tahun 1950. Algoritma ini cukup mangkus untuk digunakan dalam beberapa penyelesaian masalah dan juga untuk memberikan kecerdasan buatan dalam game. Beberapa game populer semisal Sudoku, Labirin, Catur juga bisa diimplementasikan dengan menggunakan algoritma runut balik.

Algoritma runut balik (backtracking) merupakan algoritma yang digunakan untuk mencari solusi persoalan secara lebih mangkus daripada menggunakan algoritma brute force. Algoritma ini akan mencari solusi berdasarkan ruang solusi yang ada secara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang akan diproses. (Rinaldi Munir, Diktat Strategi Algoritmik, Teknik Informatika ITB. 2005).

Algoritma runut balik berbasis pada DFS (Depth First Search) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian mendalam. Simpul-simpul yang sudah dilahirkan (diperiksa) dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E atau Expand Node.

Algoritma backtracking mempunyai prinsip dasar yang sama seperti brute-force yaitu mencoba segala kemungkinan solusi. Perbedaan utamanya adalah pada ide dasarnya, semua solusi dibuat dalam bentuk pohon solusi (pohon ini tentunya berbentuk abstrak) dan algoritma akan menelusuri pohon tersebut secara DFS (depth field search) sampai ditemukan solusi yang layak.

Properti Umum Metode runut balik (Backtracking)

Untuk menerapkan metode runut-balik, properti berikut didefinisikan:

1. Solusi persoalan.

Solusi dinyatakan sebagai vektor n-tuple:

X=(x1, x2, ..., xn), xi anggota himpunan berhingga Si

Mungkin saja S1 = S2 = ... = Sn.

Contoh: Si = {0,1}

Si = 0 atau 1

1. Fungsi pembangkit nilai xk

Dinyatakan sebagai:

T(k)

T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi

2. Fungsi Pembatas (fungsi kriteria)

Dinyatakan sebagai:

B(x1, x2, ..., xk)

Fungsi pembatas menentukan apakah (x1, x2, ..., xk) mengarah ke solusi. Jika ya, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi jika tidak, maka (x1, x2, ..., xk) dibuang dan tidak dipertimbangkan lagi dalam pencarian solusi.

Pengorganisasian Solusi

Semua kemungkinan solusi dari persoalan disebut ruang solusi (solution space).

Jika x_iÎ S_i, maka S₁ ´ S₂ ´ … ´ S_n disebut ruang solusi. Jumlah anggota di dalam ruang solusi adalah | S₁| × | S₂| × … × | S_n |. Tinjau persoalan Knapsack 0/1 untuk n = 3. Solusi persoalan dinyatakan sebagai vektor (x₁, x₂, x₃) dengan x_i Î {0,1}. Ruang solusinya adalah

{0,1} ´ {0,1} ´ {0,1} = {(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1),

(0, 1, 1), (1, 1, 1)}.

Pada persoalan Knapsack 0/1 dengan n = 3 terdapat 2ⁿ = 2³ = 8 kemungkinan solusi, yaitu:

(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1), dan (1, 1, 1).

Penyelesaian secara exhaustive search adalah dengan menguji setiap kemungkinan solusi. Ruang solusi diorganisasikan ke dalam struktur pohon. Tiap simpul pohon menyatakan status (state) persoalan, sedangkan sisi (cabang) dilabeli dengan nilai-nilai x_i. Lintasan dari akar ke daun menyatakan solusi yang mungkin. Seluruh lintasan dari akar ke daun membentuk ruang solusi. Pengorganisasian pohon ruang solusi diacu sebagai pohon ruang status (state space tree). Tinjau kembali persoalan Knapsack 1/0 untuk n = 3. Ruang solusinya:

Gambar Ruang solusi untuk persoalan Knapsack 0/1 dengan n = 3

4 Prinsip Pencarian Solusi dengan Metode Runut Balik

Langkah-langkah pencarian solusi dengan metode runut balik adalah sebagai berikut:

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan yang dipakai adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidupm dan simpul hidup yang sedang diperluas dinamakan simpul-E. Simpul dinomori dari atas ke bawah sesuai dengan kelahirannya.

2. Jika lintasan yang diperluas yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Simpul yang sudah mati ini tidak akan diperluas lagi.

3. Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak lainnya. Bila tidak ada lagi simpul anak yang dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut-balik (backtracking) ke simpul hidup terdekat. Selanjutnya simpul ini menjadi simpul-E yang terbaru.

4. Pencarian dihentikan bila telah ditemukan solusi atau tidak ada lagi simpul hidup untuk runut balik (backtracking).

Tinjau persoalan Knapsack 0/1 dengan instansiasi:

n = 3

(w₁, w₂, w₃) = (35, 32, 25)

(p₁, p₂, p₃) = (40, 25, 50)

M = 30

Solusi dinyatakan sebagai X = (x₁, x₂, x₃), x_i Î {0, 1}. Fungsi pembatas:

Gambar (a) Pohon dinamis yang dibentuk selama pencarian untuk persoalan Knapsack 0/1 dengan n = 3,

w = (35, 32, 25) dan p = (40, 25, 50)

(b) Penomoran ulang simpul-simpul sesuai urutan pembangkitannya

Solusi optimumnya adalah X = (0, 0, 1) dan F = 50.

2.5 Skema Umum Algoritma Backtracking

(a) Versi rekursif

procedure RunutBalikR(input k:integer)

{Mencari semua solusi persoalan dengan metode runut-balik; skema rekursif

Masukan: k, yaitu indeks komponen vektor solusi, x[k]

Keluaran: solusi x = (x[1], x[2], …, x[n])

}

Algoritma:

for tiap x[k] yang belum dicoba sedemikian sehingga

( x[k]¬T(k)) and B(x[1], x[2], ... ,x[k])= true do

if (x[1], x[2], ... ,x[k]) adalah lintasan dari akar ke daun

then

CetakSolusi(x)

endif

RunutBalikR(k+1) { tentukan nilai untuk x[k+1]}

endfor

Pemanggilan prosedur pertama kali: RunutBalikR(1)

(b) Versi iteratif

procedure RunutBalikI(input n:integer)

{Mencari semua solusi persoalan dengan metode runut-balik; skema iteratif.

Masukan: n, yaitu panjang vektor solusi

Keluaran: solusi x = (x[1], x[2], …, x[n])

}

Delarasi:

k : integer

Algoritma:

k¬1

while k > 0 do

if (x[k] belum dicoba sedemikian sehingga x[k]¬T(k)) and

(B(x[1], x[2], ... ,x[k])= true)

then

if (x[1],x[2],...,x[k]) adalah lintasan dari akar ke daun

then

CetakSolusi(x)

endif

k¬k+1 {indeks anggota tupple berikutnya}

else {x[1], x[2], …, x[k] tidak mengarah ke simpul solusi }

k¬k-1 {runut-balik ke anggota tupple sebelumnya}

endif

endwhile

{ k = 0 }

procedure RunutBalikI(input n:integer)

{Mencari semua solusi persoalan dengan metode runut-balik; skema iteratif.

Masukan: n, yaitu panjang vektor solusi

Keluaran: solusi x = (x[1], x[2], …, x[n])

}

Delarasi:

k : integer

Algoritma:

k¬1

while k > 0 do

if (x[k] belum dicoba sedemikian sehingga x[k]¬T(k)) and

(B(x[1], x[2], ... ,x[k])= true)

then

if (x[1],x[2],...,x[k]) adalah lintasan dari akar ke daun

then

CetakSolusi(x)

endif

k¬k+1 {indeks anggota tupple berikutnya}

else {x[1], x[2], …, x[k] tidak mengarah ke simpul solusi }

k¬k-1 {runut-balik ke anggota tupple sebelumnya}

endif

endwhile

{ k = 0 }

Pemanggilan prosedur pertama kali: RunutBalikI(n)

· Setiap simpul dalam pohon ruang status berasosiasi dengan sebuah pemanggilan rekursif.

· Jika jumlah simpul dalam pohon ruang status adalah 2ⁿ atau n!, maka untuk kasus terburuk, algoritma runut-balik membutuhkan waktu dalam O(p(n)2ⁿ) atau O(q(n)n!), dengan p(n) dan q(n) adalah polinom derajat n yang menyatakan waktu komputasi setiap simpul.

Pembuatan algoritma dengan menggunakan prinsip backtracking banyak digunakan dalam menyelesaikan berbagai masalah. Adapun masalah-masalah yang dapat diselesaikan dengan teknik tersebut, antara lain:

1. Banyaknya Himpunan Bagian Suatu Himpunan (Sum Of Subsets)

Masalah utama dari Sum Of Subsets adalah jika terdapat n bilangan real dan ingin dihitung semua kombinasi yang mungkin dari himpunan bilangan tersebut. Kombinasi yang diinginkan yaitu kombinasi yang jumlah seluruh elemennya sama dengan M (tertentu).

Sebelum kita selesaikan masalah tersebut dengan menggunakan teknik backtracking, perhatikan terlebih dahulu penyajian permasalahan dan penyelesaiannya dalam bentuk pohon.

Misalkan banyaknya bilangan real tersebut adalah 4 (n=4) akan ditentukan lebih dahulu kombinasi-kombinasi dari elemen-elemen bilangan tersebut. hal itu dikenal dengan istilah himpunan bagian (subsets). Dari pohon berikut digambarkan bahwa setiap ruas (edge) diberi label sedemikian sehingga ruas dari simpul (vertex/node) tingkat I ke simpul tingkat I + 1 akan mewakili nilai dari x_i. Pada setiap simpul, ruang penyelesaian dibagi (dipartisi) menjadi ruang-ruang penyelesaian bagian. Ruang penyelesaian didefinisikan oleh semua jalur dari akar simpul (node root) ke simpul lainnya di dalam pohon tersenut. Kemungkinan jalur-jalur tersebut adalah () atau kosong, ini berarti tidak ada jalur dari akar simpul ke dirinya sendiri (1), (1,2), (1,2,3), (1,2,3,4), (1,2,4), (1,3,4), (2), (2,3), (2,3,4) dan seterusnya.Jalur-jalur tersebut mempunyai ukuran tuple yang berbeda-beda, yang merupakan ruang penyelesaiannya. Secara struktur data, pencari ruang solusi di atas menggunakan queue, yang disebut juga dengan breadth first search (BFS)

Gambar Pohon dari ruang penyelesaian dalam breadth first search (BFS)
Adapun bentuk penyajian lain dari pencarian ruang penyelesaian permasalahan tersebut di atas, adalah dengan menggunakan ukuran tuple yang sama (tetap). Bahwa untuk setiap ruas dari simpul-simpul tingkat I ke simpul-simpul tingkat i+1 diberi nama dengan nilai X_i=0 atau X_i=1. Semua jalur dari akar ke daun didefenisikan sebagai ruang penyelesaian. Pohon bagian (sub tree) di sebelah kiri dari akar sama dengan semua himpunan bagaian yang berisi W₁. sementara itu untuk pohon bagaian disebelah kanannya adalah merupakan semua himpunan bagaian yang tidak mengandung W₁ dan seterusnya. Pendarian simpul-simpul dari pohon tersebut sehingga diperoleh ruang penyelesaiannya menggunakan metode stack. Hal I tersebut dinamakan juga dengan istilah Depth First Search (DFS).

Gambar Pohon Dari Penyelesaian Ruang DFS

Kedua bentuk penyajian pohon dari persoalan sum of subsets, merupakan tahapan pertama dalam proses mendapatkan solusi sesungguhnya (solusi optimal). Untuk mendapatkan solusi yang optimal dari ruang penyelesaian digunakan suatu algoritma lain. Algoritma tersebut menggunakan teknik backtracking, yang selanjutnya disebut dengan algoritma SUMOFSUB.

PROCEDURE SUMOFSUB(s,k,r)

GLOBAL INTEGER M,n

GLOBAL REAL W(1:n)

GLOBAL BOOLEAN X(1:n)

REAL r,s; INTEGER k,j

X(k) = 1

IF s + W(k) = M THEN PRINT (X(j), j ← 1 TO k)

ELSE

IF s + W(k) + W(k+1) ≤ M THEN

CALL SUMOFSUB(s+W(k), k+1, r-W(k))

ENDIF

IF s + r - W(k) ≥ M AND s + W(k) ≤ M THEN

X(k) 0

CALL SUMOFSUB(s, k+1, r-W(k))

ENDIF

END SUMOFSUB

1. Pewarnaan Graph (Graph Coloring)

Misalkan G adalah sebuah graph dan m adalah bilangan yang positif. Kita ingin menemukan simpul-simpul dari G yang dapat diwarnai sedemikian rupa sehingga dua simpul yang berdampingan tidak mempunyai warna yang sama, sehingga hanya m warna yang dipakai. Masalah keputusan pewarnaan m bertujuan untuk menanyakan bilangan yang terkesil dimana graph G dapat diwarnai. Bilangan ini disebut sebagai bilangan khromatik dari sebuah graph.

Sebuah graph dikatakan planar jika tidak ada dua buah titik yang saling berpotongan. Sebuah kasus yang terkenal dari “m colorability decision problem” yaitu masalah 4 warna dari suatu graph planar. Masalah ini disertai pertanyaan sebagai berikut: berikan beberapa map yang dapat menimbulkan daerah-daerah yang diwarnai sedemikian rupa sehingga daerah-daerah yang berdampingan tidak memiliki warna yang sama, tapi hanya empat buah warna yang dipakai oleh sebuah masalah dimana graph- graph masalah itu berubah menjadi sangat berguna, karena sebuah map dapat dengan mudah dirubah bentuknya menjadi sebuah graph.

Masing-masing daerah dari map itu menjadi sebuah titik dan jika dua buah daerah berdampingan maka kedua buah titiknya berhubungan, kemudian kedua titik itu dihubungkan dengan sebuah edge.

Dalam bagaian ini kita mempertimbangkan tidak hanya graph- graph yang dibuat untuk map-map tetapi semua graph diperhitungkan juga.

Kita tarik dalam mendeterminankan semua cara-cara yang berbeda yang mana graph tampil mungkin dengan memakai yang terbanyak m warna.

Gambar Sebuah map dan representasi graph planarnya

Jika kita unpamakan sebuah graph dengan matrik adjacency GRAPH (1:n, 1:n), dimana graph (I,j) = benar jika (I,j) adalah sebuah garis dari G dan graph (I,j) yang lainnya adalah salah. Kita labih senang menggunakan nilai-nilai dari Boolean sejak algoritma hanya akan menarik dengan ada atau tidaknya sebuah titik. Warna-warna tersebut diumpakan dengan bilangan 1,2,2,…,m dan pemecahan akan diberikan dengan n-tuple. (x(1),… x(n0 dimana x(i) adalah warna dari node(i).

Dengan mempergunakan rumus backtracking seperti yang telah diberikan dalam algoritam maka hasil dari program tersebut adalah MCOLORING. Disebutkan bahwa state space tree yang sering dipergunakan adalah sebuah tree dengan tingkat m dan panjang = n+1.

Procedure MCOLORING (k)

Global integer m,n, X(1:n) boolean GRAPH (1:n,1:n)

Integer k

Loop

Call NEXTVALUE (k)

if X(k) = 0 then Exit

Andif

if k = n

then print (X)

else call MCOLORING (k+1)

endif

repeat

end MCOLORING

Prosedur MCOLORING dimulai pertama-tama dengan pembagian graph untuk matrik adjacency-nya, membuat harga x = 0, dan kemudian memanggil statement call MCOLORING.

Prosedur NEXTVALUE menghasilkan kemungkinan warna-warna untuk X9k) setelah X(1) samapi X(k-1).

Gambar State space tree untuk MCOLORING ketika n=3 dan m=3

Loop yang utama dari MCOLORING secara berulang mengambil sebuah elemen, dari berbagai kemungkin-kemungkinan, kemudian membaginya ke dalam X(k) dan kemudian memanggil MCOLORING.

Procedure NEXTVALUE (k)

Global integer m,n, X(1:n) boolean GRAPH (1:n,1:n)

Integer k

Loop

X(k) –(X(k)+1) mod (m+1)

if X(k) = 0 then return andif

for j-1 to n do

if GRAPH(k,j) and X(k) = X(j)

then exit endif

repeat

if j = n+1 then return endif

repeat

end NEXTVALUE

Setiap path untuk sebuah daun diwakili dengan sebuah pewarna yang memakai tiga warna. Bahwa hanya 12 warna penyelesaian yang keluar dengan tepat tiga warna.

Gambar Sebuah graph dengan 4 node dan 3 pewarnaan yang mungkin

1. Lingkaran Hamiltonian (Hamilton Cyclles)

Misal G = (V,E) adalah graph terhubung dengan vertice. Lingkaran Hamilton (diciptakan oleh Sir William Hamilton) adalah buah circuit dengan n edge dari G yang dikunjungi sekali oleh setiap vertex dan kembali pada posisi semula. Dengan perkataan lain jika sebuah lingkaran Hamilton dimulai dengan beberapa vertex v₁dan v_n+1 yang sama.

Kita sekarang akan melihat pada algoritma backtracking yang menemukan semua lingkaran Hamilton ini di dalam Graph. Graph itu mungkin terhubung tetapi mungkin saja tidak. Hanya circuit yang berbeda yang akan menjadi keluarannya.

Gambar Dua graph, hanya satu yang mengandung lingkaran Hamilton Pemecahan dengan backtracking vector (x_i, …, x_n) telah dibatasi sehingga x₁yang diwakilkannya telah dikunjungi vertex dari rencana circuit. Sekarang yang perlu kita lakukan adalah menyelesaikan bagaimana menghitung vertice yang mungkin dari x_kjika x₁, x₂, …,x_k-1 siap dipilih.

Jika k=1, maka x(1) didapatkan n vertex.

Cara lainnya untuk menghindarkan n kali bekas-bekas lingkaran yang sama, kita menghendaki x(1)=1.

Jika 1 k n, kemudian X(k) menjadi beberapa vertex v yang berbeda dari x(1), x(2),…, x(k-1) dan v dihubungkan dengan sebuah edge untuk x(k-1).

X(n) hanya dapat menjadi satu-satunya vertex dan merupakan hubungan dari x(n-1) dan x(1). Kita mulai dengan prosedur NEXTVALUE yang menyelesaikan vertex selanjutnya yang mungkin, dari circuit yang sudah direncanakan.

Procedure NEXTVALUE (k)

Global integer n, x(1:n) boolean GRAPH (1:n,1:n)

Integer k, j

Loop

X(k) –(X(k)+1) mod (n+1)

if x(k) = 0 then return andif

if GRAOH(x(k)-1), x(k))

then for j-1 to k-1 do

if x(j)=x(k)

then exit

endif

repeat

if j=k

then if k n or (k=n and GRAPH (x(n),1))

then return

endif

repeat

end NEXTVALUE

Dengan memakai prosedur NEXTVALUE kita dapat menyebutkan satu demi satu skema backtracking secara rekursif untuk menemukan semua Hamiltonian cycle.

Procedure HAMILTONIAN (k)

Global integer x(1:n)

Local integer k,n

Loop

Call NEXTVALUE(k)

If x(k)=0 then return andif

If x(k)=n

Then print (x,’1’)

Else call HAMILTONIAN (k+1)

Endif

Repeat

And HAMILTONIAN

Prosedur ini dimulai matrik adjacency GRAPH (1:n, 1:n), kemudian memasukkan x(2:n) ß0, x(1) ß1 dan kemudian melakukan call HAMILTONIAN(2).

1. Masalah Knapsack (Knapsack Problem)

Persoalan knapsack ini mempertimbangkan kembali section, yang mana akan didefinisikan serta memecahkan permasalahan algoritma pemrograman secara dinamika. The Zero-One yaitu mencari hasil yang paling baik secara zero-one pada knapsack tersebut.

Procedure BOUND (p,n,k,m) determinan upper bound didapat solusi yang lebih baik. Dengan perkembangan node z pada level k+1 dari space state tree. Hal yang utama berat dan totalnya W(i) dan P(i).

(i) dan dengan asumsi itu P(i)/W(i) ≥ P(i+1)/W(i+1)

Procedure BOUND (k)

Global integer n, PC(1:n),W(1:n)

integer k,i: rela b,c,p,w,M

b ßp ; c ßW

for i ß k+1 to n do

c ß cw(i)

if c < M then d ß p + P(i)

else return (b+(1-(c-M)/W(i)) * p(i))

endif

repeat

return (b)

end BOUND

4 Implementasi Algoritma runut balik

Algoritma runut balik ini banyak digunakan pada beberapa program, seperti program permainan sudoku, program permainan kuda menyebrang jembatan dengan lintasan Hamilton, program pencarian solusi game maz (labirin), dan juga digunakan dalam gerak animasi 3D, dan beberapa program yang lainnya.

2.4.1 Program permainan Sudoku

2.4.1.1 Gambaran umum teka-teki Sudoku

Sudoku adalah suatu permainan teka-teki yang memiliki aturan sederhana. Teka-teki ini terdiri atas 9 buah blok yang berupa tabel 3 × 3. Sebagian sel tabel dalam teka-teki ini telah diisi dengan angka-angka yang berupa patokan untuk menyelesaikan teka-teki. Tujuan permainan ini adalah untuk mengisi setiap sel tabel yang masih kosong dengan angkaangka, sedemikian sehingga dalam 1 blok hanya terdiri atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1 baris maupun kolom. Meskipun aturannya sederhana namun penyelesaian teka-teki ini tidak semudah aturannya. Tentu saja tingkat kesulitan tiap teka-teki dapat bervariasi. 2.2 Strategi umum penyelesaian teka-teki Sudoku Secara umum, Sudoku dapat diselesaikan dengan kombinasi teknik pemindaian (scanning), penandaan ( marking), dan analisa (analysing). Beberapa tekiteki Sudoku yang tergolong mudah dapat diselesaikan hanya dengan salah satu proses, namun pada umumnya kita harus mengkombinasikan ketiga teknik tersebut.

a. Pemindaian

Berupa proses memindai baris atau kolom untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin.

b. Penandaan

Berupa analisa logika, dengan menandai kandidat angka yang dapat dimasukkan dalam sebuah sel.

c. Analisa

Berupa eliminasi kandidat, dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya 1 kandidat.

N : integer

{adalah ukuran papan sudoku }

tabel : array[1.. N2] of

array[1..N2]

{representasi papan sudoku}

Tutorial cara Menginstal Windows 7 Lengkap Dengan Gambar-Operating System Widonws 7 merupakan salah satu dari beberapa produk Microsoft yang pada saat ini lagi booming, paling banyak penggunanya.

Ok brother kita mulai belajar nya...

berikut langkah instal windowns 7 lengkap:

1.pastikan dari BIOS booting komputer anda di setting untuk DVD

2.masukkan DVD windows 7

3.tekan sembarang tombol saat muncul boot from cd or dvd

4.akan terlihat gambar seperti gambar dibawah ini

5.pililah indonesian pada language,time,currency,and location

6. Tekan tombol install now

7.tunggu beberapa saat proses ini

8.centang pada I accept the license term sebagai persetujuan penggunaan windows 7 kemudian klik next

9.karena sedang melakukan clean install pilih saja custom (advanced) untuk memilih di drive mana windows 7 akan di install

10.Ditahap ini kamu bisa melakukan partisi atau membagi Hardisk kedalam beberapa drive, dimana nanti untuk windows 7 berada pada drive (c) dan sisanya drive (D) untuk penyimpanan data kamu nantinya.Atau jika kamu partisinya belakangan