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

ABSTRAK

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.