The Knight's Tour dengan Backtracking

Knight’s Tour adalah suatu permainan yang menggunakan papan catur menggunakan teori graf. Pada permainan ini, kita harus menjalankan kuda ke setiap kotak tepat satu kali hingga semua kotak terlewati. Seperti kita tahu bahwa langkah dari kuda adalah serupa dengan huruf L yaitu
• Dua langkah horisontal kemudian 1 langkah vertikal, atau
• Satu langkah horisontal kemudian 2 langkah vertikal, atau
• Dua langkah vertikal kemudian 1 langkah horisontal, atau
• Satu langkah vertikal kemudian 2 langkah horisontal.
Jika pada Knight’s Tour suatu solusi mampu melangkah tepat 1 disemua kotak dan bisa kembali ke kotak mulai, maka disebut Closed Knight’s Tour. Jika tidak mampu kembali ke kotak mulai walaupun semua kotak telah terlewati maka disebut Open Knight’s Tour.

Backtracking sendiri merupakan perbaikan dari  Algoritma Brute Force. Algoritma ini berbasis pada DFS (Depth First Search).  Algoritma ini diperkenalkan oleh D.H Lehmer pada 1950. Penggunaan Backtracking adalah untuk hanya mencari solusi yang mengarah pada solusi yang tepat. Sehinggan waktu pencarian suatu langkah bisa lebih hemat. Algoritma ini akan men
Algoritma Backtracking bisa kita gunakan untuk mencari solusi dari kasus permainan Knight’s Tour yaitu dengan cara sebagai berikut :
1. Dari kotak awal kuda ditempatkan dibangkitkan langkah-langkah yang mungkin dilalui oleh kuda.
2. Memilih salah satu langkah (kotak) yang kemudian diperluas langkah tersebut.
3. Menempatkan kuda pada kotak yang telah dipilih.
4. Mengulangi langkah satu untuk kotak yang sedang ditempati.
5. Kembali ke langkah sebelumnya jika belum ditemukan solusi(backtracking).
6. Pencarian berhenti jika telah ditemukan solusi atau tidak ada lagi langkah yang memungkinkan.

Berikut adalah algoritma backtracking untuk kasus Knight’s Tour
• board is n x n (ukuran dari papan)
• (x,y) adalah koordinat letak kotak
• move adalah nomor kotak yang telah dilewati
• ok adalah boolean apakah sukses atau gagal

type chess_board is array (1..n,1..n) of integer;

procedure knight (board : in out chess_board;

                         x,y,move : in out integer;

                         ok : in out boolean) is

w, z : integer;

begin

   if move = n^2+1 then

     ok := ( (x,y) = (1,1) );

   elsif board(x,y) /= 0 then

     ok := false;

   else

     board(x,y) := move;

     loop

       (w,z) := Next position from (x,y);

       knight(board, w, z, move+1, ok );

       exit when (ok or No moves remain);

     end loop;

     if not ok then

       board ( x,y ) :=0; -- Backtracking 

     end if;

    end if;

end knight;

Referensi
[1] http://www.csc.liv.ac.uk/~ped/teachadmin/algor/search.html
[2] http://www.informatika.org/~rinaldi/Stmik/2007-2008/Makalah2008/MakalahIF2251-2008-109.pdf
[3] http://www.usna.edu/Users/math/wdj/knight_tour.htm