n-Queen problem dengan algoritma backtrackig (runut-balik)

Utomo, Eko Satrio Budi (2010) n-Queen problem dengan algoritma backtrackig (runut-balik). Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

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

Download (801kB)

Abstract

Algoritma runut-balik adalah sebuah algoritma yang digunakan untuk menemukan semua atau beberapa solusi dari beberapa masalah komputasi, dengan membangun kandidat-kandidat baru untuk solusi yang diberikan, dan meninggalkan masing masing bagian kandidat (runut-balik) segera setelah diketahui bahwa kandidat tersebut tidak mungkin diselesaikan menjadi solusi yang valid. Dalam kajian ini penulis menentukan banyaknya cara menempatkan n queen pada papan berukuran n x n sedemikian hingga tidak ada dua queen dapat saling memakan.

n-Queen problem adalah permasalahan di mana harus mencari cara bagaimana meletakkan Queen sebanyak n pada papan berukuran n x n sedemikian rupa sehingga tidak ada satu queen yang saling memakan dengan 1 langkah. Metode penelitian yang pertama merumuskan masalah, mengumpulkan data yang bersumber dari buku, jurnal, artikel, diktat kuliah, internet, dan lainnya yang berhubungan dengan permasalahan yang akan dibahas dalam penelitian, kemudian menganalisa dan membuat kesimpulan.

Berdasarkan hasil pembahasan dapat diperoleh bahwa rumus umum untuk n x n dengan n=6t-2 dan n=6t untuk t bilangan asli adalah Ai,1\2i untuk i genap dengan 1\2i...j...1\2n dan Ai,1\2n+k untuk i ganjil, dengan 1\2n+1...j...n-1, dan k bilangan asli dengan 1...k...1\2n solusi queen pada kotak di atas untuk n x n dengan n=12t-4 untuk t bilangan asli dapat diperoleh rumus umum Ai,1\2i untuk i gelap dengan 1\2i...j...1\2n dan solusi untuk i ganjil untuk i=4k-3 maka j=1\2n+2k dan untuk i=4k-1 maka j=1\2n-1+2k dimana k bilangan asli dengan 1...k...1\4n.

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Barizi, Ahmad
Keywords: Graf Pohon; Backtracking; Matriks; Langkah Queen
Subjects: 01 MATHEMATICAL SCIENCES > 0101 Pure Mathematics > 010105 Group Theory and Generalisations
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Masyitoh Firdaus Fahmi
Date Deposited: 16 May 2017 07:04
Last Modified: 16 May 2017 07:04
URI: http://etheses.uin-malang.ac.id/id/eprint/6507

Actions (login required)

View Item View Item