a apr*offi2on

ffi*,a APr*offi2onW*c.

rttrift: '{Fr

A(:cq:'

Mergfl.t"rl

DAFTAR ISI

i*ffirnan Judul1*& FengantarSrnnbutan Ketua STIKI

Dffiar lsi

lmplementasi Struktur Tree Untuk Pemodelan Sistem

lnformasi Bebantenan On-Line Dalam Upacara Yadnya

Agama Hindu

Evaluasi Kesesuaian Lahan Buah Pisang Kepok

Didasarkan Agroklimat Dengan Pendekatan Sistem

lnformasi Geografis

Rancangan Aplikasi Sistem lnformasi Keuangan Pada

Universitas Sains Dan Teknologi Jayapura (Ustj)

Rancangan Aplikasi Sistem lnformasi Manajemen Aset

Pada Universitas Sains Dan TeknologiJayapura (Ustj)

Pengembangan Framewerk Sisfo Kampus Berbasis Web

Menggunakan Metodologi Fast (Studi Kasus Stmik lij)

Sistem tnformasi Studi Pelacakan Jejak Alumni (Tracer

Study) Program Studi Sistem lnformasi Fakultas Sains

Dan Teknologi (Studi Kasus : Uin Syarif Hidayatullah

Jakarta)

Sistem lnformasi Penunjang Keputusan Penerimaan

Nasabah Pembiayaan Murabahah Menggunakan

ModelAhp (Studi Kasus : Bnisyariah)

Klasifikasi Penilaian Kinerja Dosen Dengan

Menggunaka n Algoritma Backpropagation

Model Pengembangan Sistem lnformasi Pengelolaan

Pondok Pesantren Mahasiswa

Pem buatan Prototi pe Apli kasi Wi reless M enggu na ka n

TeknologiJava Pada Sistem lnformasi AkademikPoliteknik Caltex Riau

Aplikasi Pengunduh Dan Pembaca Data NilaiJual Objek

Pajak (NJOP) Pada DirektoratJenderal Pajak

rssN 2089-1083SNATIKA 20LL, Volume 01

Halaman

10-15

L7-21

29-33

34-39

39-44

45-51

52-57

ilt

ivv-ix

i!! Anak Agung KompiangOka Sudana, lda AyuGde Kurnia Jayanti

ZainulArham

Mochamad Wahyudi,Muanam

Mochamad Wahyudi,Miwan KurniawanHidayat

Yusuf Durachman,Arini, Ryan Sofyan

Nur Aeni Hidayah

7 Nur Aeni Hidayah

Marson James

Budiman, Jufri

HusniThamrin, SusiloVeriYulianto,Julpitriadi

Juni Nurma Sari,

Febriliyan Samopa

Puji Rahayu, BandiAshari

1-6

10

Ll 58-53

-,erra F. Palandi

-* T Evelina, Tias A.mcbruv'ati

tsarnbang Hariyanto,Hirin DuiiAgustin

loko Lianto Buliali,Ahmad Saikhu

Ketut Agustini

Sawalludin, OpimSalim Sitompul, Erna

Budhiarti Nababan

Eko Budi Cahyono,Mochamad Hariadi

1.9 Taufiq, Rahmadi

20 Endah Purwanti

Jufri Wahyudi, TaufikFuadiAbidin

Muhammad AinurRony

Galan Tri Suseno, lna

Agustina, FirmanAnindra

Gunawan Putrodjojo

lda Ayu MadeWidiadnyani Pertiwi,MadedWindu AntaraKesiman, I Made Agus

Wirawan

Desain Sistem Toefl Untuk Membantu Persiapan TesToefl

Adaptasi Search Engine Yahoo Dan Google: AnalisisDiskriminan Dengan Pendekatan TechnologyAcceptance Model (TAM) Dan Usability

Pengkajian Peraturan Bank lndonesia No 9lt5/PBl/20A7Tahun 2007 Sebagai Pedoman Tata Kelola Teknologilnformasi (lT Governance) Bank Umum Di lndon'esia

Uji Bilangan Acak Dari Fungsi Pembangkit Bilangan AcakPada Bahasa Pemrograman Java

Pengembangan Simulasi Binary Tree Berbasis CAI UntukPembelajaran Matematika Diskrit

lsomorphic Solutions Of The N-Queens Problem

lnteraksi Gerak Tangan Alami Dengan LingkunganAugmented Reality Berbasis Metoda ProjectiveReconstruction

Penerapan Fuzzy Multi Criteria Decision Making(Fmcdm) Untuk Pemilihan LokasiSpbu Pada Kota

Banjarbaru

Logika Fuzzy Untuk Uji Kelayakan Lahan Singkong

Sebagai Bahan Baku Bioetanol

Penentuan Secara Otomatis Akronim Dan Ekspansinya

Dari Data Teks Berbahasa lndonesia

Sistem Pakar Untuk Mengidentifikasi Kerusakan Kulkas

Lg Tlpe Gr-S512 Menggunakan Aplikasi Mobile

AplikasiSistem Pakar Untuk Diagnosa Penyakit MenularPada Kambing

Aplikasi Multimedia Untuk Pembelajaran BerbasisSimulasi Heuristik Dengan Konektifitas Scorm

Pengembangan Aplikasi E-Learning Berbasis ModelPembelajaran Kooperatif Tipe Tgt (Teams GameTournament)

64-70

71-78

79-83

84-87

88-91

92-97

98-101

102-108

109-114

115-119

120-124

125-130

131-138

L39-L44

27

22

23

24

VI

25

Isomorphic Solutions of the N-queens Problem


Sawaluddin1, Opim Salim Sitompul2, Erna Budhiarti Nababan3

1 University of Sumatera Utara, Dept. of Mathematics, Medan 20155, [email protected]

2 University of Sumatera Utara, Dept. of Mathematics, Medan 20155, [email protected]

3 University of Sumatera Utara, Dept. of Information Technology, Medan 20155, [email protected]

Abstract. The N-queens problem is a classicexample in mathematics as well as computerscience that receives many attentions fromresearches for nearly two centuries. Despite itsusefulness in teaching computationalintelligence algorithms, another interestingfeatures of the N-queens problem is the notionof isomorphism and transformation groups.Once a solution of the N-queens problem isfound, the isomorphic solutions can betransformed easily by performing two kinds ofpermutations, i.e. rotation and reflection. In thispaper, we proposed a two-stage approach tofind the isomorphic solutions to the N-queensproblem. In the first stage, a genetic algorithmis used to find a solution of the N-queensproblem. In the second stage, the solution istransformed into seven isomorphic solutions.Using this approach, a complete solution forthe N-queens problem can be obtained. Theresults obtained show how the completeisomorphic solutions of 5-, 6-, 7-, 8-, and 9-queens can be generated in a very shortexecution time.

Keyword: object-oriented approach, genetic algorithm,N-queens problem, isomorphism.

1. Introduction

The N-queens problem is a classic example inmathematics as well as computer science that receivesmany attentions from many researches for nearly twocenturies. For the last two decades and more recentyears, the N-queens problem has been solved usingsome heuristic algorithms, especially geneticalgorithm (see for examples [1-7]). Despite itsusefulness in teaching computational intelligencealgorithms, another interesting features of the N-queens problem is the notion of isomorphism andtransformation groups [8, 9]. The problem can bestated algebraically by the following definition (asadapted from [1]): Let A be the set of integers such

that A={1,2, …, N } . Define B as the Cartesianproduct of A, i.e., B=A × A . Then B = {(1,1),(1,2), …, (2,1), …, (N,1), …, (N,N)}. Select Nelements of B and call this set as C. The set Crepresents a solution to the problem if for theCartesian product of C = C ×C , each element

((ik , jk ) ,(il , jl)) , either satisfies all of thefollowing conditions or fails all of them (for all l, k =1, 2, …, N).

1. ik ≠ il {not on the same column}2. jk ≠ jl {not on the same row}3. ik + jk ≠ il + jl {not on the same diagonal}4. ik - jk ≠ il - jl {not on the same diagonal}

As an example, Fig. 1 illustrates a solution of an 8-queens problem. As can be seen from the figure, eachqueen is located in different column and no queens arelocated on the same rows or on the same diagonals.

Fig. 1. Example of solution for the 8-queens

One of the many interesting features of the N-queens problem is the notion of isomorphism of itssolutions. Among many of the solutions, we canidentify that several of them are isomorphic form ofthe others. The isomorphic solutions can be obtainedfrom a current solution by means of permutation.There are seven different permutations that can beperformed to obtain complete isomorphic solutions,three of them are clock-wise rotations of 90o, 180o,and 270o. The other four permutations are reflectionsof the horizontal middle axes, vertical middle axes,left diagonal axes, and right diagonal axes (see Fig. 2).

SNATIKA 2011, ISSN 2089-1083 | 92


Fig. 2 Permutations of the original position

In this paper, we proposed a two-stage approachto find the isomorphic solutions of the N-queensproblem. In the first stage, a genetic algorithm isused to find a solution and in the second stage theseven permutations are performed to the initialsolution in order to get the isomorphic solutions.

The structure of this paper is organized asfollows: in section 2 we briefly describe thecharacteristics of the group of permutation in whichthe N-queens problem is formulated. In section 3,we describe the class data structure used by thegenetic algorithm to solve the problem. In section 4we provides an overview of the genetic algorithmapproach used in this paper and discuss theproperties of the three main operations in thegenetic algorithm, i.e. selection, reproduction, andmutation. Section 5 presents some results anddiscusses the output obtained for several cases of N,and finally in section 6 we will summarize the workand present the conclusion.

2. The N-queens problem of Group of Permutations

In algebra, the solutions of the N-queens problemare one example of a group of permutations that canbe represented as a group of symmetries ofgeometric figures (symmetries of the squares) [10].The set of transformations for N-queens is adihedral group Δ4, i.e. the group of symmetries ofthe squares of 4 sides. Elements of the group can beobtained by the operations of rotation R through360o/4, and reflection M about some side [9, 10].

As a group of permutation, we can find amongthe solutions of the problem that the permutationoperations are closed, has an identity element, hasan inverse, and associative. The closed propertiescan be shown from the fact that a permutation of aset C of the solutions of the N-queens problem is abijective function from a cartesian product of

C=C ×C . Thus, for a solution C0 = {(3,1),

(6,2), (8,3), (1,4), (4,5), (7,6), (5,7), (2,8)} of the 8-queens, the permutation yields:

C1 = {(5,1),(1,2),(8,3),(4,4),(2,5),(7,6),(3,7),(6,8)}(rotation 90o clockwise)C2 = {(3,1),(6,2),(2,3),(5,4),(8,5),(1,6),(3,7),(6,8)}(rotation 180o clockwise)C3 = {(3,1),(6,2),(2,3),(7,4),(5,5),(1,6),(8,7),(4,8)}(rotation 270o clockwise)C4 = {(2,1),(5,2),(7,3),(4,4),(1,5),(8,6),(6,7),(3,8)}(reflection on vertical axis)C5 = {(6,1),(3,2),(1,3),(8,4),(5,5),(2,6),(4,7),(7,8)}(reflection on horizontal axis)C6 = {(4,1),(8,2),(1,3),(5,4),(7,5),(2,6),(6,7),(3,8)}(reflection on left diagonal)C7 = {(6,1),(3,2),(7,3),(2,4),(4,5),(8,6),(1,7),(5,8)}(reflection on right diagonal)

The identity element is a special transformation,namely a rotation of 0o that doesn’t do anything.The inverse element of the solutions is an act toundo the transformation. In this case, the inversecan be formed by taking the inverses of thetransformation in reverse order for any sequence ofrotation and mirror images. The associativity of thetransformation can be shown by compositionoperation, such that the following equation holds:(C1 ○ C2) ○ C3 = C1 ○ (C2 ○ C3) [11].

3. The N-queens Class Data Structure

The class structure for the N-queens problem isdepicted in Fig. 3. The class consists of twomembers, i.e. the variable and function members.

SNATIKA 2011, ISSN 2089-1083 | 93


Fig. 3. The N-queens class structure

The member variable maintain a privatepopulation list, which points to the head of anorthogonal list used to store the population and theindividual data. The member function consists ofthe operations necessary for the genetic algorithmprocessing, namely creating an initial population,calculating non attacking queen, calculating fitnessof each individual, and the three main operations ofgenetic algorithm: random selection, reproduction,and mutation.

The private variable member of the N-queensclass points to a structure consisting of two lists ofnodes representing a list of population which pointsto a list of individuals. The two lists form anorthogonal list as shown in Fig. 4, where thehorizontal lists are representing the individuals andthe vertical lists are representing the population.Each node of the individual lists maintains thecolumn and row position information of the queen,whereas each node of the population list maintains

the individual as well as the number of nonattacking queens and their fitness.

Fig. 4. Orthogonal list of the N-queens datastructure

Each queen is placed into a fixed columnranging from 1 to N. During the initial creation ofthe individuals, the row position for each individualnode is generated randomly. Each column isinitialized with a number between 1 and N, showingthe row position of the queens. Fig. 5 shows anexample of the 8-queens problem with an initialpopulation of four individuals, where the rows arepositions of each queen in each column position of1 to 8.

Fig. 5. An instance of an initial population with four individuals

4. Overview of the Genetic Algorithm Approach

The N-queens class has several public memberfunctions for the main operations of the geneticalgorithm. Function create initial population

performs the initialization of the population. Afterthe initial population has been populated withindividuals, then the non attacking queens arecalculated using the following simple rule:

Two queens are attacking each otherwhenever:

SNATIKA 2011, ISSN 2089-1083 | 94


Each queen located at the samerow

Each queen located at the samecolumn

Each queen located at the samediagonal

For example, let X = Column and Y = Row. Two ormore queens located on the same row whenever Yi

= Yi+1 =… = Yj, where Yi and Yj are row positions ofthe ith and jth queens. Furthermore, two or morequeens are located on the same diagonal if |Xi – Xj|= |Yi – Yj|, where i, j = 1, 2, …, N. Location ofqueens on the same column, however, can beomitted since each queen will be placed on adifferent column, labeled from 1 to N.

Function calculate fitness is then used tocalculate the fitness of each individual. The fitnessfunction is determined in the following steps:

Determine the maximum number of non-attacking pairs of queens

max ( AQi )=N ×(N−1)

2

where AQi denotes the number non-

attacking queens and N is the number ofqueens.

Calculate the number of attacking queens (AQi

), which located on the same rowsand/or the same diagonals. The queens areattacking each other either directly orindirectly. Fig. 6 illustrates the attackingqueens.

Fig. 6. Attacking queens

Calculate the number of non-attacking

queens: max AQi

¿) - AQi

.

Calculate fitness:

Fitness (Qi )=AQi

∑j=1

N

AQ j

where Qi is a queen located on row i and

AQiis the number of non-attacking

queen for a queen located on row i.

The next three member functions of the classare for the main operation of the genetic algorithm,i.e. random selection, reproduction, and mutation.The random selection function chooses a pair ofdifferent individual from the population randomly.Each pair of individuals is then undergoes areproduction process in which some genes from oneindividual are exchanged with genes from anotherindividual. The crossover point is randomly chosenfrom the positions in the strings of genes [11]. Bythis means, two new individuals are reproducedwith combination of genes inherited from the twoparents. The reproduction step is illustrated in Fig.7.

Fig. 7. Reproduction step with crossover point (c)randomly chosen

The last process of the genetic algorithm ismutation, where one or more genes from the newcreated individual are altered into different genes.The mutation point denoting which gene willundergo the alteration is chosen randomly from thestring of genes of each new individual.

5. Result and Discussion

The genetic algorithm appoach is written usingGNU C/C++ and implemented on Intel CPU [email protected], 2.0 GHz of RAM with GNU C/C++running on Windows XP. In the first stage, a set ofdata consisting of several chess board size aretested by executing the program ten times for eachdata set of certain chess board sizes. A completeresults obtained from the test for several number ofqueens is shown in Table 1.

SNATIKA 2011, ISSN 2089-1083 | 95


Table 1. Results of ten times execution for severalnumber of queens

# of Queens

MaxGen #Pop

Ave # of Gen

Ave Exec Time (sec)

Ave #of Exec

4 100 20 1.1 0 10.45 20 7.3 0.015625 16 20 42.8 0.078125 35.87 20 48.5 0.140625 7.98 20 48.7 0.125 92.89 20 60.5 0.203125 151.1

10 200 20 103.9 0.421875 92.211 300 20 155.6 0.640625 142.512 20 180.7 0.734375 311.713 400 20 230.1 1.078125 413.4

Table 1 shows some parameters that are used inthe program, namely the number of queens (# ofqueens), maximum number of generations (MaxGen), the number of population (#Pop), the averagenumber of generations (Ave # of Gen), the averageexecution time (Ave Exec Time) in seconds, and theaverage number of execution in order to obtain thefirst solution (Ave # of Exec).

From the experiment performed, it was foundthat the complexity of the program is increasing as

the number of the queens is increased. This fact canbe illustrated by the number of executionsperformed in order to obtain the first solution, sincethe solution is not always obtained in everyexecution (see Fig. 8). The number of executionsare increasing exponentially as the number ofqueens increases.

Fig. 8. Complexity of the problem as the number ofqueens increases

As for the second stage, the program is executedin order to obtain the isomorphis solutions for eachnumber of queens setup in the first stage. Results ofthe execution for the number of Queens of 4, 5, 6,7, and 8 can be seen in Fig. 9.

Fig. 9. Isomorphic solutions for several N-queens

SNATIKA 2011, ISSN 2089-1083 | 96


6. Conclusion

Even though the N-queens problem is oftenconsidered as a toy problem, the solution to thisproblem is in fact a difficult one. The N-queens problem is an instance of the contraint satisfactionproblem (CSP) that can be setup for classroomdemonstration purposes as an NP-completeproblem. The nature of isomorphic solutions of theproblem can also be used as a tool to teach studentabout the concepts of isomorphism, transformationgroups, as well as equivalence classes.

References

[1] Erbas, C., Sarkhesik, S., Tanik, M. M.:Different perspectives of the N-queensproblem. CSC ’92: Proc. of the 1992 ACMAnnual Conference on Communications, 99-108 (1992)

[2] Crawford, K.D.: Solving the N-queensproblem using genetic algorithm, SAC ’92:Proc. Of the 1992 ACM/SIGAPPSymposium on Applied Computing, 1039-1047 (1992)

[3] Homaifar, A., Turner, J., Ali, S.: The N-queens problem and genetic algorithm,Proc. IEEE Southeastcon ’92, 262-267(1992)

[4] Bozikovic, A., Golub, M., Bodin, L.:Solving N-queens problem using globalparallel genetic algorithm, The IEEE Reg. 8EUROCON 2003, 104-107 (2003)

[5] Bozinovski, A., Bozinovski, S.: N-queenspattern generation: an insight into spacecomplexity of a backtracking algorithm,Proc. of the 2004 International Symposiumon Information and CommunicationTechnologies (ISICT ’04), 281-286 (2004)

[6] Martinjak, I.: Comparison of heuristicalgorithms for the N-Queen problem. Proc.Of the ITI 2007 29th Int. Conf. onInformation Technology Interfaces, Cavtat,Croatia, 759-764 (2007).

[7] Turkey, A.M., Ahmad, M.S.: Using geneticalgorithm for solving N-queens problem.Proc. of the 2010 International Symposiumin Information Technology (ITSim), KualaLumpur, 745-747 (2010)

[8] Eastridge, R., Schmidt, C.: Solving N-queens with a genetic algorithm and itsusefulness in a computational intelligencecourse. J. of Computing Sciences inColleges 23, 223-230 (2008)

[9] Cull, P., Pandey, R.: Isomorphism and the N-queens problem. SIGCSE Bulletin 26, 29-44(1994)

[10] Pinter, C.C.: A Book of Abstract Algebra.McGraw-Hill: New York (1982)

[11] Russel, S., Norvig, P.: Artificial IntelligenceA Modern Approach. 2nd Edition, PrenticeHall: New Jersey (2003)

SNATIKA 2011, ISSN 2089-1083 | 97

a apr*offi2on

Documents