Pada kajian skripsi ini pokpk permasalahan adalah bagaimana cara mendeskripsikan algoritma benteng pada papan catur berukuran sehingga tidak ada dua benteng yang saling menangkap atau memakan dalam 1 baris dan 1 kolom. Adapun yang menjdi tujuan dalam penulisan skripsi ini adalah untuk mendeskripsikan dan menganalisis cara langkah benteng pada papan catur sedemikian hingga tidak ada dua benteng yang dapat saling menangkap atau memakan satu dengan yang lain dalam I baris dan 1 kolom. Penulisan skripsi ini dibatasi hanya pada papan berukuran genap dan ganjil dengan dengan n > 2 dan benteng yang di tempatkan pada papan adalah jumlah maksimal benteng yang dapat ditempatkan. Algoritma runut balik ( backtracking) adalah algorima yang berbasis pada DFS untuk mencari solusi persoalan secara lebih ringkas daripada algoritma .Algoritma ini akan mencari solusi berdasarkan ruang solusi yang ada sacara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang akan diproses. Algoritma runut balik diterapkan dalam permainan catur . Dalam permainan catur di kenal bidak yang memiliki nama dan pergerakan yang berbedabeda. Bidak- bidak tersebut yaitu: pion, knight, king dan queen. Semuanya memiliki pergerakan sendiri- sendiri. Adapun benteng dapat bergerak dalam sejumlah petak secara horizontal, dan vertikal. Menurut teori algoritma runut balik dalam mencari koefisien dari rook polynomial yang berarti banyaknya cara menempatkan k buah benteng pada sebuah papan catur berukuran hingga . Berdasarkan pembahasan di atas dapat di peroleh rumusan umum sebagai berikut :
) . Ini berlaku untuk baik genap maupun ganjil.
No comments:
Post a Comment