CLIQUE MAKSIMAL SEBAGAI KONSEP DASAR PEMBUATAN ALGORITMA CLIQUE-BACK UNTUK MENYELESAIKAN MASALAH N-RATU


Diny Zulkarnaen(1*)

(1) Jurusan Matematika Fakultas Sains dan Teknologi UIN Sunan Gunung Djati, Indonesia
(*) Corresponding Author

Abstract


Masalah N-ratu adalah suatu masalah penempatan ratu sebanyak N pada papan catur berukuran NxN dengan syarat tidak ada dua ratu yang saling menyerang. Banyak pendekatan yang dapat dilakukan untuk memecahkan masalah ini. Pada makalah ini digunakan pendekatan teori graf berdasarkan konsep clique maksimal sebagai metode penyelesaian masalah. Metode ini selanjutnya dijadikan dasar untuk membuat algoritma. Agar solusi lebih cepat diperoleh, maka digunakanlah algoritma backtracking. Penggabungan antara algoritma yang menggunakan konsep clique maksimal dan algoritma backtracking tersebut dinamakan algortima clique-back. Tidak seperti algoritma pada umumnya yang meletakkan satu-per-satu ratu pada kotak papan catur dan memeriksanya agar memenuhi syarat, algoritma ini justru seolah-oleh menempatkan ratu pada setiap kotak, kemudian mengeliminasinya (sesuai syarat) hingga akhirnya diperoleh solusi (jika ada). Proses eliminasi tersebut menyebabkan solusi yang diperoleh lebih cepat.

Full Text:

PDF

References


Erbas, Cengiz, and Seyed Sarkeshikt and Murat M. Tanik. 1992. Different Perpective of the N-Queens Problem, ACM, 99-108

Foulds, L. R. and D. G. Johnson. 1984. An Application on Graph theory and integer programming. Mathematics Magazine : vol 52 No 2, 95-104

Mumtaz, Fahmi. 2008. Algoritma Runut-Balik (Backtracking Algorithm) Pada Masalah Knight’s Tour. Makalah IF2251 Strategi Algoritmik Tahun 2008.