26
Apr
11

KNIGHT’S TOUR

Siapa yang tak mengenal permainan ini???????Ini adalah permainan catur, sebuah permainan yang ditemukan di masyarakat negara Persia dan Arab, yang kemudian menyebar ke seluruh dunia. Kata “catur” itu sendiri berasal dari kata “chaturanga,” yang dalam bahasa Sanskrit berarti “empat divisi ketentaraan.”

Setelah melalui beberapa perubahan, akhirnya pada abad ke 12, bidak-bidak catur mulai ditetapkan, menjadi raja (king), ratu (queen), gajah (bishop), kuda (knights), dan benteng (rocks) serta pion (pawn). Perkembangan pada catur pun mulai terjadi. Dahulu permainan ini berakhir hingga berhari-hari lamanya, tetapi pada tahun 1300, mulai diperkenalkan pembatasan waktu bermain serta pada saat itu juga diperkenalkan aturan melangkah bidak pion.

Pada tahun 1.475 terjadi evolusi permainan catur. Mulai diperkenalkan konsep langkah Ratu (buah yang paling kuat) serta mulai diperkenalkan konsep promosi pion yang bisa berubah menjadi ratu. Gajah juga berubah istilah menjadi bishop. Dengan demikian skak mat menjadi lebih mudah di permainan ini dan mengurangi secara drastis langkah-langkah yang diperlukan.

Seorang pemain Italia, Gioacchino Greco, tercatat sebagai pecatur profesional pertama dalam sejarah permainan ini. Ia menulis buku catur dan menampilkan beberapa komposisi permainan serta analisis catur. Karya ini membuat catur menjadi permainan populer serta mulai menunjukkan teori, taktik dan strategi permainan ini.

Karya pertama yang memuat berbagai variasi dan kombinasi kemenangan ditulis oleh François-André Danican Philidor dari Prancis. Ia menunjukan permainan catur terbaik selama 50 tahun terakhir dan buku itu dipublikasi pada abad 18. Bukunya berjudul L’Analyze des échecs (Analisa Catur), sebuah buku berpengaruh hingga dicetak ulang sampai 100 kali.


KNIGHTS TOUR

Telah dijelaskan latar belakang sejarah catur diatas, kini saya akan coba terapkan konsep permainan catur pada matematika. Disini akan di gunakan kuda (knights) untuk penerapannya atau yang lebih dikenal knights tour.

Knights Tour merupakan sebuah masalah dalam matematika yang melibatkan kuda (knights) pada papan catur. Tujuan dari knight’s tour ini adalah melewati setiap kotak pada papan catur. Sebelum kita membahas lebih lanjut, saya akan menjelaskan sedikit tentang teori graf. Graf adalah himpunan simpul yang dihubungkan dengan sisi-sisi.


Graf yang akan digunakan disini ialah graf Hamilton. Graf Hamilton ada 2 macam, lintasan Hamilton, yaitu lintasan yang melalui tiap simpul di dalam graf tepat satu kali (gambar 2), dan sirkuit Hamilton ialah lintasan Hamilton yang kembali ke titik asal dan membentuk lintasan tertutup (gambar 1).


Gambar 1                                                    Gambar 2

Sekarang kita akan melihat aplikasi knights tour dalam metematika.


Seperti yang kita ketahui, bidak yang paling menarik langkahnya pada permainan catur adalah kuda, karena langkah kuda membentuk huruf L pada setiap langkahnya, seperti gambar di samping.


Untuk menyelesaikan knight’s tour ini, diperoleh banyak cara untuk menyelesaikannya. Apabila kita menggunakan konsep matematika secara umum, yaitu antara lain, menggunakan konsep faktorial, maka kemungkinan yang terjadi adalah 64! = 1.27 × 1089, sehingga membutuhkan bejuta-juta tahun untuk meyelesaiaknnya. Menggunakan konsep eksponensial, kemungkinan yang terjadi pun tidaklah sedikit, yaitu sekitar 64 × 463, lebih sedikit jika dibandingkan dengan konsep faktorial, teteapi tetap musatahil juga untuk kita cari. Dan dengan konsep simetri, maka kemungkinannya paling sedikit adalah 8.5 × 1038. WOW, terlihat mustahil bagi kita untuk menyelesaikan knight’s tour ini dengan ketiga konsep diatas. Dari ketiga konsep matematika diatas, langkah-langkah yang dibutuhkan sangat-sangat lah panjang sekali dan untuk menggunakan konsep tersebut kita harus menggunakan sebuah alat seperti komputer, salah satunya dengan menggunakn metode algoritma backtracking.


Algoritma Backtracking bisa kita gunakan untuk mencari solusi dari kasus permainan. Kita akan membangun solusi parsial dari sebuah masalah lalu akan mencoba mengembangkan solusi tersebut. Jika solusi yang telah diperluas gagal, maka ia akan balik (dengan runut balik) dan akan mencoba solusi parsial lainnya, Knight’sTour yaitu dengan cara sebagai berikut :

  1. Dari kotak awal kuda ditempatkan dan membangkitkan 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). Pencarian berhenti jika telah ditemukan solusi atau tidak ada lagi langkah yang memungkinkan.

Berikut adalah contoh algoritma backtracking untuk kasus Knight’s Tour:

  • boardnya adalah 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;


Metode yang lain yang bisa digunakan adalah metode De Moivre. Langkah-langkah metode ini adalah sesuai gambar disamping:

  1. Solusi ini untuk papan berukuran 8 × 8 dengan 64 kotak.
  2. Bagi papan menjadi ukuran 4 × 4 pada bagian tengah kotak dengan sisi luar berjarak 2 kotak dari pinggir papan catur.
  3. Lintasan kuda dapat dimulai dari dalam kotak (berukuran 4 × 4) atau bagian luar kotak 4 × 4 tersebut.
  4. Jika dimulai pada bagian luar kotak, kuda bergerak memutari bagian luar kotak 4 × 4 terlebih dahulu hingga seluruh bagian luar kotak 4 × 4 terlewati semua.
  5. Bidak kuda akan masuk ke dalam kotak, hanya jika sudah tidak bisa melewati bagian luar kotak tersebut.
  6. Jika semua kotak bagian luar telah dilalui, maka dapat melalui bagian dalam kotak dengan mudah.
  7. Untuk memulai dari dalam kotak, dapat diulang langkah-langkah diatas.

Dalam matematika lintsan yang dibuat sebagai penyelesaian langkah kuda tersebut dapat kita terjemahakan ke dalam ilmu matematika yaitu teori graf, khususnya garf Hamilton. Seperti yang telah dijelaskan sebelumnya mengenai definisi lintasan dan sirkuit Hamilton, dapat kita terjemahkan ke dalam knight’s tour ini sendiri.

Berikut adalah contoh lintasan knight’s tour:

Gambar 5


        

Gambar 6

Perhatikan gambar 5 dengan menggunakan nomor, terlihat nomor 64 (merupakan simpul akhir) tidak bisa menuju ke nomor 1 (merupakan simpul awal) sehingga termasuk lintasan Hamilton, sedangkan untuk gambar 6, perhatikan gambar yang menggunakan nomor, disini terlihat bahwa simpul 64 bisa menuju ke simpul satu, tentunya dengan memeperhatikan langkah kuda, sehingga gambar 6 merupakan sirkuit Hamilton. Jadi berdasarkan definisi lintasan dan sirkuit Hamilton, maka gambar 5 termasuk lintasan Hamilton dan gambar 6 termasuk sirkuit Hamilton.


KESIMPULAN

Jadi kesimpulan yang dapat ditarik dari permasalahan diatas adalah permaianan catur tidak hanya dapat digunakan sebagai permainan mengasah otak, tetapi dengan menggunakan salah satu bidaknya yaitu kuda dapat membuat permasalahn yang cukup menarik untuk diselesaikan yaitu sebuah knight’s tour. Dan dari knight’s tour ini dapat diaplikasikan ke dalam bentuk matematika yaitu teori graf bahkan pemrograman komputer dengan algoritma backtracking.

Terima Kasih

                                                                                        M. RIJAL ALFIAN

                                                                                        G1D 008 008


27 Responses to “KNIGHT’S TOUR”


  1. 3 123nyren
    April 26, 2011 at 11:21 am

    karna papan caturnya warna ungu,,
    i like it dah ayokk….:)

  2. 5 hidayat07
    April 26, 2011 at 11:50 am

    wah…. Panjang bner postingan mu jang…

    Kok ada tulisan yg berantakan tu jang…

  3. 7 ucie
    April 26, 2011 at 1:05 pm

    coll…
    matematika mank kueren abiezzz…
    tapi tulisan yang tinta itemx jadi g keliatan jang,sama2 item se,,,,
    go ahade adk2…biar lbh kreatif.. ^^

  4. April 27, 2011 at 2:01 am

    baguuuuuuuuuuuuuuuussssssssss punya mu jang…..

  5. April 27, 2011 at 4:12 pm

    Bruuuuu..
    ud mb like tu…..

  6. 15 tinz08
    April 28, 2011 at 5:45 am

    jank, papan catur tuh,, bukannya warnanya hitam putih ya…??? heheee…
    like dsini jga dunkzz…
    https://gamatika.wordpress.com/2011/04/08/pita-satu-permukaan-2/

  7. 17 taufiqmtk08
    April 28, 2011 at 9:31 am

    bagus

  8. April 28, 2011 at 12:39 pm

    sukses bozzzz, aku tetap tak mengerti tapi hehehehe
    bukan bidang ane

  9. 21 itha89
    April 30, 2011 at 2:15 pm

    krennnnnn………..

  10. 25 ernagalery2008
    May 5, 2011 at 1:14 am

    latar item kok pke tulisan warna item,,,g bs baca ndut…..

  11. 27 Nunik Herawati
    April 1, 2013 at 4:11 am

    gan,, tu aplikasi kalo kita mau bikin pake program apa??


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


1_502554913l

Current CO2 Level in the Atmosphere

yang sudah mampir

  • 200,745 gamatika-ers

Kategori Tulisan

No Smoking

Lagi Online

Arsip

April 2011
M T W T F S S
« Mar   May »
 123
45678910
11121314151617
18192021222324
252627282930  

%d bloggers like this: