Solution of n-Queen problem using ACO

Author

Khan, Salabat ; Bilal, Mohsin ; Sharif, M. ; Sajid, Malik ; Baig, Rauf

Author_Institution

Nat. Univ. of Comput. & Emerging Sci., Islamabad, Pakistan

fYear

2009

fDate

14-15 Dec. 2009

Firstpage

1

Lastpage

5

Abstract

In this paper, a solution is proposed for n-Queen problem based on ACO (ant colony optimization). The n-Queen problem become intractable for large values of `n´ and thus placed in NP (non-deterministic polynomial) class problem. The n-Queen problem is basically a generalized form of 8-Queen problem. In 8-Queen problem, the goal is to place 8 queens such that no queen can kill the other using standard chess queen moves. So, in this paper, the proposed solution will be applied to 8-Queen problem. The solution can very easily be extended to the generalized form of the problem for large values of `n´. The paper contains the detail discussion of problem background, problem complexity, ant colony optimization (swarm intelligence) and a fair amount of experimental graphs.

Keywords

computational complexity; graph theory; optimisation; ACO; NP-hard problem; ant colony optimization; experimental graphs; n-Queen problem; nondeterministic polynomial class problem; swarm intelligence; Ant colony optimization; Chemicals; Costs; Genetic algorithms; Joining processes; Multiagent systems; Particle swarm optimization; Polynomials; Simulated annealing; Telephony; 8-Queen Problem; Ant Colony optimization (ACO); Heuristic Techniques; Swarm Intelligence (SI); n-Queen Problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Multitopic Conference, 2009. INMIC 2009. IEEE 13th International

Conference_Location

Islamabad

Print_ISBN

978-1-4244-4872-2

Electronic_ISBN

978-1-4244-4873-9

Type

conf

DOI

10.1109/INMIC.2009.5383157

Filename

5383157