Penerapan Teori Permutasi Untuk Permasalahan N Bidak Kuda Tidak Saling Menyerang Pada Papan Catur N x N

Astudin, Junika Irdia Indi (2026) Penerapan Teori Permutasi Untuk Permasalahan N Bidak Kuda Tidak Saling Menyerang Pada Papan Catur N x N. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5002221011-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

Penempatan bidak pada papan catur merupakan salah satu permasalahan dalam kombinatorika enumeratif yang membahas banyaknya susunan objek pada suatu papan dengan aturan tertentu. Salah satu bentuk permasalahan tersebut adalah penempatan n bidak kuda pada papan catur berukuran n x n dengan syarat setiap baris dan kolom memuat tepat satu bidak. Konfigurasi tersebut dapat direpresentasikan sebagai suatu permutasi atau elemen grup simetri Sn. Penelitian ini bertujuan untuk menentukan banyaknya konfigurasi valid penempatan n bidak kuda tidak saling menyerang pada papan catur berukuran n x n serta menganalisis struktur simetrinya. Enumerasi konfigurasi valid dilakukan menggunakan partisi baris, prinsip inklusi-eksklusi, dan proses eliminasi. Analisis struktur simetri dilakukan melalui aksi grup dihedral D4 yang meliputi transformasi rotasi dan refleksi, sedangkan banyaknya kelas ekivalensi dihitung menggunakan Teorema Burnside. Hasil penelitian menunjukkan bahwa banyaknya konfigurasi valid penempatan n bidak kuda untuk n = 3, 4, 5, 6, 7, 8, 9, 10 dan 11 berturut-turut adalah 2, 8, 20, 94, 438, 2766, 19480, 163058 dan 1546726. Banyaknya kelas ekivalensi terhadap aksi grup dihedral D4 untuk n = 3, 4, 5, 6, 7, 8, 9, 10 dan 11 berturut-turut adalah 1, 3, 6, 21, 75, 415, 2621, 21066 dan 195485. Penelitian ini juga menunjukkan bahwa permutasi identitas selalu merupakan konfigurasi valid untuk setiap ukuran papan, serta diperoleh formula umum untuk banyaknya konfigurasi valid bertipe sikel (2, 1, 1, ..., 1) dan (3, 1, 1, ..., 1). Dengan demikian, penelitian ini tidak hanya menghasilkan enumerasi konfigurasi valid, tetapi juga memberikan karakterisasi struktur simetri melalui teori permutasi dan aksi grup dihedral.
=====================================================================================================================================
Chess piece placement is one of the problems in enumerative combinatorics, which studies the number of possible arrangements of objects on a board subject to certain constraints. One such problem is the placement of n knights on an n x n chessboard such that each row and each column contains exactly one knight. Such a configuration can be represented as a permutation, or equivalently, as an element of the symmetric group Sn. This study aims to determine the number of valid configurations for placing n non-attacking knights on an n x n chessboard and to analyze their symmetry structure. The enumeration of valid configurations is carried out using row partitions, the inclusion–exclusion principle, and an elimination process. The symmetry analysis is performed under the action of the dihedral group D4, consisting of rotations and reflections, while the number of equivalence classes is determined using Burnside’s Theorem. The results show that the numbers of valid configurations for n = 3, 4, 5, 6, 7, 8, 9, 10 and 11 are 2, 8, 20, 94, 438, 2766, 19480, 163058 and 1546726, respectively. Furthermore, the numbers of equivalence classes under the action of the dihedral group D4 for n = 3, 4, 5, 6, 7, 8, 9, 10 and 11 are 1, 3, 6, 21, 75, 415, 2621, 21066 and 195485, respectively. The study also shows that the identity permutation always forms a valid configuration for every board size, and derives general formulas for the numbers of valid configurations with cycle types (2, 1, 1, ..., 1) and (3, 1, 1, ..., 1). Therefore, this study not only provides an enumeration of valid configurations but also characterizes their symmetry structure through permutation theory and the action of the dihedral group.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Papan Catur, Bidak Kuda, Permutasi, Konfigurasi, Kelas Ekivalensi Chessboard, Knight, Permutation, Configuration, Equivalence Class
Subjects:	Q Science > QA Mathematics > QA159 Algebra
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	Junika Irdia Indi Astudin
Date Deposited:	23 Jul 2026 03:29
Last Modified:	23 Jul 2026 03:29
URI:	http://repository.its.ac.id/id/eprint/136497

Actions (login required)

View Item