Lampiran 1 Program DLV, modul pembangkitan

LAMPIRAN

16

Lampiran 1 Program DLV, modul pembangkitan. 1 2 3 4 5

arc(X,Y,1,0,0,0) C(X,Y,1). arc(X,Y,1,1,0,0) arc(X,Y,1,0,1,0) arc(X,Y,1,1,1,0) C(X,Y,3). arc(X,Y,0,0,0,0) arc(X,Y,1,0,0,0) arc(X,Y,1,1,0,0) arc(X,Y,1,0,1,0) arc(X,Y,1,0,1,1)

v arc(X,Y,0,1,0,0) v arc(X,Y,0,0,1,0) v arc(X,Y,0,0,0,1) :v arc(X,Y,0,1,1,0) v arc(X,Y,0,0,1,1) v arc(X,Y,1,0,0,1) v v arc(X,Y,0,1,0,1) :- C(X,Y,2). v arc(X,Y,0,1,1,1) v arc(X,Y,1,0,1,1) v arc(X,Y,1,1,0,1) ::- C(X,Y,0). v arc(X,Y,0,1,0,0) v arc(X,Y,0,1,1,0) v arc(X,Y,0,1,0,1) v arc(X,Y,1,1,0,1)

v v v v

arc(X,Y,0,0,1,0) v arc(X,Y,0,0,0,1) v arc(X,Y,0,0,1,1) v arc(X,Y,1,0,0,1) v arc(X,Y,1,1,1,0) v arc(X,Y,0,1,1,1) v arc(X,Y,0,0,0,0) :- C(X,Y,null).

Modul ini akan membangkitkan kemungkinan solusi dengan melihat angka di dalam cell slither link, baris pertama akan membangkitkan kandidat solusi untuk cell yang memiliki nilai 1 ditunjukkan oleh predikat C(X,Y,1), baris kedua akan membangkitkan kandidat solusi untuk cell dengan nilai 2, baris ketiga untuk cell dengan nilai 3, baris keempat untuk cell dengan nilai 0, dan baris kelima untuk cell dengan nilai null.

17

Lampiran 2 Program DLV, constraint cell dengan nilai 0, 1, 2, dan 3. 1 2 3 4

::::-

arc(X,Y,1,0,0,0), arc(X,Y,0,1,0,0), arc(X,Y,0,0,1,0), arc(X,Y,0,0,0,1),

arc(A,Y,_,_,0,_), arc(X,B,_,_,_,0), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_),

X=A+1. B=Y+1. A=X+1. Y=B+1.

5 6 7 8 9 10 11 12 13 14 15 16

::::::::::::-

arc(X,Y,1,1,0,0), arc(X,Y,1,1,0,0), arc(X,Y,0,1,1,0), arc(X,Y,0,1,1,0), arc(X,Y,0,0,1,1), arc(X,Y,0,0,1,1), arc(X,Y,1,0,0,1), arc(X,Y,1,0,0,1), arc(X,Y,1,0,1,0), arc(X,Y,1,0,1,0), arc(X,Y,0,1,0,1), arc(X,Y,0,1,0,1),

arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_), arc(X,B,_,_,_,0), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(A,Y,_,_,0,_), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(X,B,_,_,_,0),

B=Y+1. X=A+1. B=Y+1. A=X+1. Y=B+1. A=X+1. Y=B+1. X=A+1. X=A+1. A=X+1. Y=B+1. B=Y+1.

17 18 19 20 21 22 23 24 25 26 27 28

::::::::::::-

arc(X,Y,1,1,1,0), arc(X,Y,1,1,1,0), arc(X,Y,1,1,1,0), arc(X,Y,0,1,1,1), arc(X,Y,0,1,1,1), arc(X,Y,0,1,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,1,0,1), arc(X,Y,1,1,0,1), arc(X,Y,1,1,0,1),

arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,_,_,0), arc(X,B,_,0,_,_), arc(A,Y,0,_,_,_), arc(A,Y,_,_,0,_), arc(A,Y,0,_,_,_), arc(X,B,_,0,_,_), arc(X,B,_,0,_,_), arc(X,B,_,_,_,0), arc(A,Y,_,_,0,_),

B=Y+1. X=A+1. A=X+1. B=Y+1. Y=B+1. A=X+1. X=A+1. A=X+1. Y=B+1. Y=B+1. B=Y+1. X=A+1.

29 30 31 32

::::-

arc(X,Y,0,0,0,0), arc(X,Y,0,0,0,0), arc(X,Y,0,0,0,0), arc(X,Y,0,0,0,0),

arc(X,B,_,_,_,1), arc(X,B,_,1,_,_), arc(A,Y,_,_,1,_), arc(A,Y,1,_,_,_),

B=Y+1. Y=B+1. X=A+1. A=X+1.

Bagian B=Y+1 menandakan bahwa posisi B ada di bawah Y, dan bagian X=A+1 menandakan bahwa posisi X ada di sebelah kanan A .Baris 1 sampai baris 4 pada lampiran ini menunjukkan constraint untuk cell bernilai 1, baris 5 sampai baris 16 menunjukkan constraint untuk cell bernilai 2, dan pada baris 17 sampai baris 28 constraint untuk cell bernilai 3. Baris 29 sampai baris 32 menunjukkan constraint untuk cell bernilai 0.

18

Lampiran 3 Program DLV, constraint mencegah local loop. 1 2 3 4

::::-

arc(X,Y,1,1,0,1), arc(X,Y,0,1,1,1), arc(X,Y,1,1,1,0), arc(X,Y,1,0,1,1),

arc(A,Y,0,1,1,1), arc(A,Y,1,0,1,1), arc(X,B,1,0,1,1), arc(X,A,1,1,1,0),

A=X+1. X=A+1. Y=B+1. A=Y+1.

5 6 7 8

::::-

arc(X,Y,1,1,1,0), arc(X,Y,0,1,1,1), arc(X,Y,1,0,1,1), arc(X,Y,1,1,0,1),

arc(X,B,_,1,_,_), arc(A,Y,_,_,1,_), arc(X,B,_,_,_,1), arc(A,Y,1,_,_,_),

Y X B A

= = = =

B+1. A+1. Y+1. X+1.

Baris 1 sampai baris 4 menunjukkan constraint untuk mencegah sebuah cell memiliki nilai 4 atau cell tersebut memilik 4 buah garis yang mengelilinginya, dan baris 5 sampai baris 8 menunjukkan constraint untuk mencegah dua buah cell bernilai 3 yang bertetangga dan keduanya membentuk loop.

19

Lampiran 4 Program DLV, constraint pada cell dengan posisi di pojok grid. 1 2 3 4 5 6 7 8

::::::::-

arc(1,1,1,0,0,0). arc(1,1,0,0,0,1). arc(1,1,0,0,1,1). arc(1,1,1,1,0,0). arc(1,1,1,1,1,0). arc(1,1,0,1,1,1). arc(1,1,0,1,0,1). arc(1,1,1,0,1,0).

9 10 11 12 13 14 15 16

::::::::-

arc(1,#maxint,1,0,0,0). arc(1,#maxint,0,1,0,0). arc(1,#maxint,1,0,0,1). arc(1,#maxint,1,0,1,1). arc(1,#maxint,0,1,1,1). arc(1,#maxint,0,1,0,1). arc(1,#maxint,1,0,1,0). arc(1,#maxint,0,1,1,0).

17 18 19 20 21 22 23 24

::::::::-

arc(#maxint,1,0,0,0,1). arc(#maxint,1,0,0,1,0). arc(#maxint,1,0,1,1,0). arc(#maxint,1,1,0,0,1). arc(#maxint,1,1,1,1,0). arc(#maxint,1,1,1,0,1). arc(#maxint,1,0,1,0,1). arc(#maxint,1,1,0,1,0).

25 26 27 28 29 30 31 32

::::::::-

arc(#maxint,#maxint,0,1,0,0). arc(#maxint,#maxint,0,0,1,0). arc(#maxint,#maxint,0,0,1,1). arc(#maxint,#maxint,1,1,0,0). arc(#maxint,#maxint,1,0,1,1). arc(#maxint,#maxint,1,1,0,1). arc(#maxint,#maxint,0,1,0,1). arc(#maxint,#maxint,1,0,1,0).

Pada baris 1 sampai baris 8 menunjukkan constraint untuk cell dengan posisi di pojok kiri atas grid (1,1), kemudian baris 9 sampai baris 16 adalah constraint untuk cell dengan posisi di pojok kanan atas grid dimana #maxint adalah ukuran dari slither link, baris selanjutnya yaitu baris 17 sampai baris 24 adalah constraint untuk cell dengan posisi di pojok kiri bawah grid, dan baris 25 sampai baris 32 pada lampiran menunjukkan constraint untuk cell dengan posisi di pojok kanan bawah grid.

20

Lampiran 5 Program DLV, constraint untuk mengantisipasi cabang dan ketersambungan garis. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

::::::::::::::::-

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

:- arc(X,Y,1,_,_,0), arc(A,B,_,M,N,_), M=N, X=A+1, Y=B+1. %kiri atas :- arc(X,Y,1,0,_,_), arc(A,B,_,_,M,N), M=N, X=A+1, B=Y+1. %kanan atas :- arc(1,Y,1,0,_,_), arc(1,B,0,_,_,_), B=Y+1. %atas -- kanan :- arc(1,Y,1,_,_,0), arc(1,B,0,_,_,_), Y=B+1. %atas -- kiri :- arc(X,#maxint,1,0,_,_), arc(A,#maxint,_,0,_,_), X=A+1. %bagian kanan -- atas :- arc(X,Y,0,1,_,_), arc(A,B,_,_,M,N), M=N, X=A+1, B=Y+1. %kanan atas :- arc(X,#maxint,_,1,0,_), arc(A,#maxint,_,0,_,_), A=X+1. %bagian kanan -- bawah :- arc(#maxint,Y,_,1,0,_), arc(#maxint,B,_,_,0,_), B=Y+1. %bagian bawah -- kanan :- arc(X,#maxint,0,1,_,_), arc(A,#maxint,_,0,_,_), X=A+1. %bagian kanan -- atas :- arc(1,Y,0,1,_,_), arc(1,B,0,_,_,_), B=Y+1. %bagian atas -- kiri :- arc(X,Y,_,_,1,0), arc(A,B,M,N,_,_), M=N, A=X+1, Y=B+1. %kiri bawah :- arc(X,Y,_,0,1,_), arc(A,B,M,_,_,N), M=N, A=X+1, B=Y+1. %kanan bawah :- arc(#maxint,Y,_,0,1,_), arc(#maxint,B,_,_,0,_), B=Y+1. %bawah -- kanan :- arc(#maxint,Y,_,_,1,0), arc(#maxint,B,_,_,0,_), Y=B+1. %bawah -- kiri :- arc(X,Y,0,_,_,1), arc(A,B,_,M,N,_), M=N, X=A+1, Y=B+1. %atas -- kiri :- arc(X,Y,_,_,0,1), arc(A,B,M,N,_,_), M=N, A=X+1, Y=B+1. %bawah -- kiri :- arc(X,1,_,_,0,1), arc(A,1,_,_,_,0), A=X+1. %samping kiri -- bawah :- arc(X,1,0,_,_,1), arc(A,1,_,_,_,0), X=A+1. %samping kiri - atas :- arc(X,1,1,_,_,0), arc(A,1,_,_,_,0), X=A+1. %samping kiri -- atas :- arc(X,1,_,_,1,0), arc(A,1,_,_,_,0), A=X+1. %samping kiri -- bawah :- arc(X,#maxint,1,0,1,0), arc(A,#maxint,_,0,_,_), arc(C,#maxint,_,0,_,_), A=X+1, X=C+1. %samping kanan -- bawah -- atas :- arc(X,1,1,0,1,0), arc(A,1,_,_,_,0), arc(C,1,_,_,_,0), A=X+1, X=C+1. %samping kiri -- bawah -- atas :- arc(#maxint,Y,0,1,0,1), arc(#maxint,B,_,_,0,_), B=Y+1. %bagian bawah -- kanan :- arc(#maxint,Y,0,1,0,1), arc(#maxint,B,_,_,0,_), Y=B+1. %bagian bawah -- kiri :- arc(1,Y,0,1,0,1), arc(1,B,0,_,_,_), B=Y+1. %bagian atas -- kanan :- arc(1,Y,0,1,0,1), arc(1,B,0,_,_,_), Y=B+1. %bagian atas – kiri

38 39 40 41 42

arc(X,Y,1,1,_,_), arc(A,B,_,_,1,_), X=A+1, B=Y+1. arc(X,Y,1,1,_,_), arc(A,B,_,_,_,1), X=A+1, B=Y+1. arc(X,Y,1,1,_,_), arc(X,B,1,_,_,_), B=Y+1. arc(X,#maxint,1,1,_,_), arc(A,#maxint,_,1,_,_), X=A+1. arc(X,Y,_,1,1,_), arc(A,B,1,_,_,_), A=X+1, B=Y+1. arc(X,Y,_,1,1,_), arc(A,B,_,_,_,1), A=X+1, B=Y+1. arc(X,Y,_,1,1,_), arc(X,B,_,_,1,_), B=Y+1. arc(X,#maxint,_,1,1,_), arc(A,#maxint,_,1,_,_), A=X+1. arc(X,Y,_,_,1,1), arc(A,B,1,_,_,_), A=X+1, Y=B+1. arc(X,1,_,_,1,1), arc(A,1,_,_,_,1), A=X+1. arc(X,Y,_,_,1,1), arc(A,B,_,1,_,_), A=X+1, Y=B+1. arc(X,Y,_,_,1,1), arc(X,B,_,_,1,_), Y=B+1. arc(X,Y,1,_,_,1), arc(A,B,_,1,_,_), X=A+1, Y=B+1. arc(X,Y,1,_,_,1), arc(A,B,_,_,1,_), X=A+1, Y=B+1. arc(X,Y,1,_,_,1), arc(X,B,1,_,_,_), Y=B+1. arc(X,1,1,_,_,1), arc(A,1,_,_,_,1), X=A+1.

Pada baris 1 sampai baris 16 menunjukkan constraint untuk mencegah terjadinya cabang pada solusi slither link, dan pada baris 17 sampai baris 42 menunjukkan constraint untuk tetap menjaga agar solusi slither link merupakan sebuah garis yang kontinyu (tidak terputus).

21

Lampiran 6 Program DLV, constraint dari cell bernilai 2 yang bersebelahan dengan cell bernilai 0. 1 2 3 4

::::-

arc(#maxint,Y,1,0,1,0), arc(#maxint,Y,1,0,1,0), arc(#maxint,Y,0,1,0,1), arc(#maxint,Y,0,1,0,1),

5 6 7 8

::::-

arc(1,Y,1,0,1,0), arc(1,Y,1,0,1,0), arc(1,Y,0,1,0,1), arc(1,Y,0,1,0,1),

arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0), arc(#maxint,B,0,0,0,0),

arc(1,B,0,0,0,0), arc(1,B,0,0,0,0), arc(1,B,0,0,0,0), arc(1,B,0,0,0,0),

Y=B+1. B=Y+1. Y=B+1. B=Y+1.

Y=B+1. B=Y+1. Y=B+1. B=Y+1.

%bagian %bagian %bagian %bagian

%bagian %bagian %bagian %bagian

atas atas atas atas

bawah bawah bawah bawah

-----

kiri kanan kiri kanan

-- kiri -- kanan -- kiri – kanan

Baris 1 sampai baris 4 pada lampiran ini ditujukan untuk cell dengan posisi di bagian bawah slither link, dan baris 5 sampai baris 8 adalah constraint untuk cell dengan posisi di bagian atas slither link.

22

Lampiran 7 Pseudo code program C++ untuk membaca fakta slither link. 1 2 3 4 5

Set count to 1 FOR each string on data.dat Set titik[count] to string Increment count END FOR

6 7 8 9

Set k to 1 FOR each side on slither_link Set line_value[k] to 3 END FOR

Baris 1 sampai baris 5 pada lampiran ini digunakan untuk membaca fakta yang telah disimpan dalam file data.dat, dan pada bairs 6 sampai baris 9 digunakan untuk memberikan nilai default yaitu 3 pada setiap sisi pada cell.

23

Lampiran 8 Pseudo code program C++, modul basic_rule . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

//basic rule FOR each cell in slither_link IF cell_value is 0 THEN Set no_line on cell is TRUE ELSE IF cell_value is 1 THEN IF cell_position is 1 Set line_value on up to 0 Set line_value on left to 0 END IF ... ELSE IF cell_value is 2 THEN IF cell_position is 1 THEN IF line_value on up is 0 AND line_value on left is 0 THEN Set line_value on right to 1 Set line_value on bottom to 1 END IF END IF ... ELSE IF cell_value is 3 THEN IF cell_position is 1 Set line_value on up to 1 Set line_value on left to 1 END IF ... END IF END FOR

24

Lampiran 9 Pseudo code program C++, modul advance_rule . 1 //advance_rule 2 FOR each cell in slither_link 3 IF cell_value is 1 THEN 4 IF cell_position on up THEN 5 IF line_value on up_left is 0 THEN 6 Set line_value on up to 0 7 Set line_value on left to 0 8 END IF 9 END IF 10 .... 11 ELSE IF cell_value is 2 THEN 12 IF line_value on up is 1 AND line_value on bottom is 0 THEN 13 IF line_value on right is 0 THEN 14 Set line_value on left to 1 15 ELSE IF line_value on left is 0 THEN 16 Set line_value on right to 1 17 END IF 18 END IF 19 ... 20 ELSE IF cell_value is 3 THEN 21 IF cell_position on up THEN 22 IF line_value on up_left is 0 23 Set line_value on up to 1 24 Set line_value on left to 1 25 ELSE IF line_value on up_right is 0 26 Set line_value on up to 1 27 Set line_value on right to 1 28 END IF 29 END IF 30 ... 31 END IF 32 END FOR

25

Lampiran 10 Pseudo code program C++, modul cek_garis_cell . 1 //cek_garis_cell 2 FOR each cell in slither_link 3 IF cell_value is 1 THEN 4 IF line_value on up is 1 5 Set line_value on right, bottom, left to 0 6 END IF 7 ELSE IF cell_value is 2 THEN 8 IF line_value on up is 1 AND line_value on right is 1 THEN 9 Set line_value on bottom, left to 0 10 END IF 11 ELSE IF cell_value is 3 THEN 12 IF line_value on up is 0 THEN 13 Set line_value on right, bottom, left to 1 14 END IF 15 END IF 16 END FOR

26

Lampiran 11 Pseudo code program C++, modul sambung_garis dan modul cek_cabang. 1 2 3 4 5 6 7 8 9 10 11 12 13

//sambung_garis Set k to 1 Set n to puzzle_size FOR each side on slither_link IF line_value is 1 IF line[k] is horizontal THEN IF line_value[k-n] is 0 AND line_value[k+1] is 0 THEN set line_value[k+n+1] to 1 ELSE IF line_value[k+n+1] is 0 AND line_value[k+1] is 0 THEN set line_value[k-n] to 1 END IF END IF ... END IF END FOR

14 //cek_cabang 15 FOR each cell in slither_link 16 IF line_value[up] is 1 AND line_value[up_right] is 1 THEN 17 Set line_value that branch to 0 18 ELSE IF line_value[up] is 1 AND line_value[up_left] is 1 THEN 19 Set line_value that branch to 0 20 .... 21 END IF 22 END FOR

27

Lampiran 12 Pseudo code program C++, modul cek_logic dan fungsi sambung. 1 //cek_logic 2 FOR each cell in slither_link 3 IF cell_position is 1 4 IF line_value[up_right] is 1 AND Line_value[left_bottom] is 1 THEN 5 IF line_value[up] is 0 OR Line_value[left] is 0 6 Set line_value[bottom] to 1 7 Set line_value[right] to 1 8 ElSE IF line_value[right] is 0 OR Line_value[bottom] is 0 9 Set line_value[up] to 1 10 Set line_value[left] to 1 11 END IF 12 END IF 13 ELSE IF cell_position is puzzle_size 14 IF line_value[up_left] is 1 AND Line_value[right_bottom] is 1 THEN 15 IF line_value[up] is 0 OR line_value[right] is 0 THEN 16 Set line_value[bottom] to 1 17 Set line_value[left] to 1 18 ELSE IF line_value[left] is 0 OR line_value[bottom] is 0 THEN 19 Set line_value[up] to 1 20 Set line_value[right] to 1 21 END IF 22 END IF 23 ... 24 END IF 25 END FOR 26 27 28 29 30 31 32 33 34 35 36 37

//fungsi sambung Function sambung(puzzle_data) { Set status to 0 While status is 0 Do traversal until find a loop IF a loop satisfy the puzzle rule THEN Set status to 1 END IF END DO END WHILE }

28