N-Queens Problem Solving using Apiary Organizational-Based Optimization Algorithm

الملخص

Researchers have utilised nature-inspired metaheuristic algorithms to find solutions for complex combinatorial optimisation problems and Non-deterministic polynomial (NP) problems. The N-queens problem is categorised as an NP-Hard problem as it becomes insurmountable for large N. This paper proposed a solution for the N-queens problem based on the Apiary Organisational-Based Optimisation Algorithm (AOOA). AOOA is a nature-inspired metaheuristic optimisation algorithm for NP-Hard problems comprised of multiple beehives inside the apiary, each with its population. In contrast to the backtracking method, AOOA employs a fitness function and randomisation techniques through seven stages to approach the optimal distributions of queens so they don’t attack each other. Experiments were carried out for different values of N ranging from 4 to 10. All solutions were found for Ns (4–8), which comprised 100% of the total solutions. At the same time, 97.7272% of total solutions were found for N = 9 and 98.6187% for N = 10. Moreover, several metaheuristic algorithms have been implemented to solve the N-queens problem, and the average number of 100 iterations has been compared. The results reflect the superiority of AOOA over the competing algorithms in finding the possible number of solutions in earlier iterations and consequently reducing the computational cost of further iterations.

الكلمات المفتاحية