Laman

Sabtu, 23 Juni 2012

Knight Tour menggunakan algoritma Depth First Search(DFS)

Sudah lama sejak terakhir posting karena disibukan oleh tugas-tugas dan project yang menumpuk semester kemaren akhirnya bisa posting lagi..

Apa sih Knight Tour itu?? pasti uda pada tau semuanya kan. Bagi yang belum tau Knight Tour itu adalah semacam permainan yang mengharuskan kita menjalankan bidak kuda (itu loh yang ada di catur yang bentuk kuda pastinya. Yang jalannya bentuk “L”) melewati semua kotak yang ada di papan catur tanpa ada satu kotak yang dilewati 2 kali. Ngertikan?? pasti pada ngerti dong..
Oke aku bikin program ini menggunakan algoritma Depth First Search, penjelasannya teman-teman bisa lihat disini.

Jadi program yang saya bikin kayak gini


  1. public void processKnightTour(int indexX, int indexY, int size){  
  2.     int[] x={2,2,-2,-2,1,1,-1,-1};  
  3.     int[] y={1,-1,1,-1,2,-2,2,-2};  
  4.     countStep=0;  
  5.     int indexList,i,j;  
  6.     int sizeBoard=size;  
  7.     workList = new ArrayList();  
  8.     node[indexX][indexY] = 1;  
  9.     workList.add(new Coordinate(indexX, indexY));  
  10.     current =(Coordinate) workList.get(workList.size()-1);  
  11.     boolean statusChild;  
  12.     //int nilaiCurrent;  
  13.     while(node[current.getRow()][current.getColumn()] != sizeBoard*sizeBoard){  
  14.         //nilaiCurrent = node[current.getRow()][current.getColumn()];  
  15.         statusChild = false;  
  16.         for(int loop=0; loop<8; loop++){  
  17.             if(current.getRow()+x[loop]>=0 && current.getRow()+x[loop] < sizeBoard && current.getColumn()+y[loop]>=0 && current.getColumn()+y[loop] < sizeBoard){  
  18.                 if(node[(current.getRow()+x[loop])][(current.getColumn()+y[loop])]==0){   
  19.                     workList.add(new Coordinate(current.getRow()+x[loop], current.getColumn()+y[loop], current));  
  20.                     statusChild = true;  
  21.                 }  
  22.             }      
  23.         }  
  24.           
  25.         if(statusChild == true){  
  26.             workList.remove(workList.indexOf(current));  
  27.         }else{  
  28.             after = (Coordinate) workList.get(workList.size()-2);  
  29.             if(!current.getParent().equals(after.getParent())){  
  30.                 for(i=0; i<sizeBoard; i++){  
  31.                     for(j=0;j<sizeBoard;j++){  
  32.                         if(node[i][j]>node[after.getParent().getRow()][after.getParent().getColumn()]){  
  33.                             node[i][j]=0;  
  34.                         }  
  35.                     }  
  36.                 }  
  37.             }  
  38.             node[current.getRow()][current.getColumn()] = 0;                  
  39.             workList.remove(workList.size()-1);                  
  40.         }  
  41.         current = (Coordinate) workList.get(workList.size()-1);  
  42.         node[current.getRow()][current.getColumn()] = (node[current.getParent().getRow()][current.getParent().getColumn()])+1;              
  43.         countStep++;  
  44.     }          
  45. }  
penjelasannya gini..



  1. int[] x={2,2,-2,-2,1,1,-1,-1};    
  2. int[] y={1,-1,1,-1,2,-2,2,-2};    
nah ini untuk menentukan langkah bidak kuda. kan bidak kuda dari satu kotak bisa ada kemungkinan dia bisah jalan ke 8 kotak lainnya yah nentuinnya aku gunakan 2 array ini.


  1. workList = new ArrayList();  
  2. node[indexX][indexY] = 1;  
  3. workList.add(new Coordinate(indexX, indexY));  
  4. current =(Coordinate) workList.get(workList.size()-1);  
aku buat ArrayList dengan nama workList biar bisa ditaruh semua parcabangan yang bisa terjadi di dalam proses entar. trus aku inisialisai nilai yang ada pada node. Menambahkan node tadi kedalam workList. aku gunakan class dengan nama Coordinate untuk nampung tiap kordinat dari langkah bidak kuda tapi gak nimpan nilai dari langkah hanya nah untuk melacaknya aku gunakan array biasa untuk nampung nilai-nilai itu.


  1. while(node[current.getRow()][current.getColumn()] != sizeBoard*sizeBoard){ 
ini untuk perulangannya sampai semua kotak dapat dilewati.


  1. for(int loop=0; loop<8; loop++){  
  2.      if(current.getRow()+x[loop]>=0 && current.getRow()+x[loop] < sizeBoard && current.getColumn()+y[loop]>=0 && current.getColumn()+y[loop] < sizeBoard){  
  3.          if(node[(current.getRow()+x[loop])][(current.getColumn()+y[loop])]==0){   
  4.              workList.add(new Coordinate(current.getRow()+x[loop], current.getColumn()+y[loop], current));  
  5.              statusChild = true;  
  6.          }  
  7.      }      
  8. }  
perulangan ini untuk mencari tahu apa kah langkah berikutnya dari bidak kuda itu tidak keluar dari papan carut dan apakah kotak itu sudah dilewati. lalu lakukan penambahan kedalam workList


  1. if(statusChild == true){  
  2.                 workList.remove(workList.indexOf(current));  
  3.             }else{  
kalau ada childnya maka hapus node yang sekarang.


  1. }else{  
  2.     after = (Coordinate) workList.get(workList.size()-2);  
  3.     if(!current.getParent().equals(after.getParent())){  
  4.         for(i=0; i<sizeBoard; i++){  
  5.             for(j=0;j<sizeBoard;j++){  
  6.                 if(node[i][j]>node[after.getParent().getRow()][after.getParent().getColumn()]){  
  7.                     node[i][j]=0;  
  8.                 }  
  9.             }  
  10.         }  
  11.     }  
  12.     node[current.getRow()][current.getColumn()] = 0;                  
  13.     workList.remove(workList.size()-1);                  
  14. }  
kalau child tidah ada. saya cek apakah node yang sekarang(node yang paling akhir dari workList) dan node yang selanjutnya mempunyai parent yang sama. jika sama maka tidak perlu dilakukan perulangan untuk membuat 0(nol. oh iya 0 itu tandanya bidak kuda belum melewati kotak tersebut). nilai yang lebih tinggi dari nilai parent dari node berikutnya. kemudian menghapus node sekarang dari workList.


  1. current = (Coordinate) workList.get(workList.size()-1);  
  2. node[current.getRow()][current.getColumn()] = (node[current.getParent().getRow()][current.getParent().getColumn()])+1;  
ini untuk memberikan nilai dan menjadikan node selanjutnya sebagai node sekarang..

jadi gimana teman-teman pada ngerti ngak program saya? Pasti agak bingung yah.. gimana kalau langsung dicoba aja. programnya bisa di download disini.
programnya aku buat pakai NetBeans..

semoga ini bisa bermanfaat yah.. untuk kita semua.. :D oh yah buat para master yang baca ini tolong dikasih koreksinya yah biar program ini tambah bagus gitu..
jangan lupa tinggalin komentar teman-teman yah mengenai postingan ini.. apa pun itu saya terima kok..hehee

0 komentar:

Posting Komentar