Deskripsi algoritma benteng pada papan catur nxn dengan menggunakan algoritma runut balik

Hidayat, Herman Firmansyah (2011) Deskripsi algoritma benteng pada papan catur nxn dengan menggunakan algoritma runut balik. Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img]
Preview
Text (Fulltext)
04510039.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (5MB) | Preview

Abstract

INDONESIA :

Pada kajian skripsi ini pokok permasalahan adalah bagaimana cara mendeskripsikan algoritma benteng pada papan catur berukuran nxn 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 nxn 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 nxn berukuran genap dan ganjil dengan nxn dengan n>2 dan ... benteng yang ditempatkan 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 berbeda-beda. 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 nxn baik genap maupun ganjil.

ENGLISH:

In this research, the study of the problem is how the method to describe the step of the rook on the chess board nxn, so that nothing 2 rooks that eat/catch in 1 row and 1 column. In the concerning that become the purpose of this research is to describe and analysis the method of the rook step on the chess board nxn, so that nothing 2 rooks that can eat/catch between on rook and another in 1 row and 1 coloumn. The limited of this research in on the chess board nxn that complete and uneven measure with n>2 and ...,the rook that placed on the board is the total of maximal the rook that place.

Backtracking Algorithm is algorithm that have the basis of DFS to find out the solution of the problem more concise than brute force algorithm. This algorithm will find out the solution appropriate the solution space with systematic but not all of the solution space will be processed. Backtracking algorithm can be applied in the chess game. Play chess needs calm emotional, because if not calm when play and hurried disposed then, will make the mistake to take the step that cause lose. In the chess game familiar with pawn that have the name and different movement. They are pion, knight, king, and queen. All of them have movement itself. The rook can move in the cabin with horizontal and vertical.

According with background of the study above, so the research doing with the purpose to determine of rook step on the chess board nxn with the result that there are not two rook that can eat with another on the 1 row and 1 column. According with backtracking algorithm theory to find out ... from rookpolynomial, it means that a lot of the method to put k on the chess board, that measurement nxn. According with the research above can find out the general formula:
... . This formula can be applied to nxn exactly and queer.

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Nashichuddin, Achmad
Keywords: Graf; Pohon; Algoritma Runut Balik( Backtracking); Graf; Tree; Backtracking Algorithm
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Nuzulul Imamah
Date Deposited: 27 Apr 2017 03:00
Last Modified: 27 Apr 2017 03:00
URI: http://etheses.uin-malang.ac.id/id/eprint/6399

Actions (login required)

View Item View Item