Development of an Application for Interactive Research and Analysis of the N-Queens Problem

Velin Kralev, Radoslava Kraleva, Dimitar Chakalov

Abstract


This paper presents a study on the N-Queens Problem. Different approaches to its solution discussed in the scientific literature are analyzed. The implementation of an algorithm based on the backtracking method is also presented. The algorithm is optimized to find solutions in a specific subset of configurations among all possible ones. With this approach, the computational complexity of the algorithm is reduced from exponential to quadratic. In this way, the algorithm finds all possible solutions in a shorter time: fundamental and their symmetrical equivalents. The methodology for conducting the experiments is presented. The purpose of the study, the tasks to be performed, and the conditions for conducting the experiments are presented as well. In connection with the research, an application that implements the presented algorithm has been developed. This application generated all the results obtained in this study. The experimental results show that with a linear increase in the number of queens (equivalent to a quadratic increase in the number of fields on the board, the number of recursive calls made by the algorithm increases exponentially. Similarly, the number of possible solutions, as well as the execution time of the algorithm (in the different modes of the application - internal, interactive, and combined), also increases exponentially. However, the algorithm's execution time in the internal mode is significantly shorter than in the other two modes - interactive and combined. The future guidelines for the study are presented.

Keywords


N-queens problem; backtracking algorithm; decision problem; software development; application programs.

Full Text:

PDF

References


K. Pratt, "Closed-form expressions for the n-queens problem and related problems," International Mathematics Research Notices, vol. 2019, no. 4, pp. 1098-1107, Feb. 2019, 10.1093/imrn/rnx119.

K. C. Buño, F. G. C. Cabarle, M. D. Calabia, and H. N. Adorna, "Solving the N-Queens problem using dP systems with active membranes," Theoretical Computer Science, vol. 736, pp. 1-14, Aug. 2018, 10.1016/j.tcs.2017.12.013.

M. A. Ayub, K. A. Kalpoma, H. T. Proma, S. M. Kabir, and R. I. H. Chowdhury, "Exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem," in Proc. 20th International Conference of Computer and Information Technology, ICCIT 2017, Dhaka, Bangladesh, 2018, pp. 1–6.

M. Plauth, F. Feinbube, F. Schlegel, and A. Polze, "Using Dynamic Parallelism for Fine-Grained, Irregular Workloads: A Case Study of the N-Queens Problem," in Proc. 2015 3rd International Symposium on Computing and Networking, CANDAR 2015, Hokkaido, Japan, 2016, art. no. 7424747, pp. 404-407, 10.1109/CANDAR.2015.26.

A. F. J. Al-Gburi, S. Naim, A. N. Boraik, "Hybridization of bat and genetic algorithm to solve N-queens problem," Bulletin of Electrical Engineering and Informatics, vol. 7, no. 4, pp. 626-632, Dec. 2018, 10.11591/eei.v7i4.1351.

O. Kolossoski, L. C. Matioli, E. M. R. Torrealba, and J. G. Silva, "Modular knight distance in graphs and applications on the n-queens problem," Discrete Mathematics, vol. 343, no. 12, art. no. 112136, Dec. 2020, 10.1016/j.disc.2020.112136.

M. BaÄa, S. C. López, F. A. Muntaner-Batle, and A. SemaniÄová-FeňovÄíková, "New Constructions for the n-Queens Problem," Results in Mathematics, vol. 75, no. 1, art. no. 41, Mar. 2020, 10.1007/s00025-020-1166-9.

A. Alhassan, "Build and conquer: Solving N queens problem using iterative compression," in Proc. International Conference on Computer, Control, Electrical, and Electronics Engineering 2019, ICCCEEE 2019, Sudan, 2019, art. no. 9070976.

G. Zheng and Y. Xu, "A Hybrid Chemical Reaction Optimization Algorithm for N-Queens Problem," Advances in Intelligent Systems and Computing, vol. 1274 AISC, pp. 128-137, 2021, 10.1007/978-981-15-8462-6_15.

I. A. Humied, "Solving N-Queens problem using subproblems based on genetic algorithm," IAES International Journal of Artificial Intelligence, vol. 7, no. 3, pp. 130-137, Sep. 2018, 10.11591/ijai.v7.i3.pp130-137.

V. Jain and J. S. Prasad, "Solving N-queen problem using genetic algorithm by advance mutation operator," International Journal of Electrical and Computer Engineering, vol. 8, no. 6, pp. 4519-4523, Dec. 2018, 10.11591/ijece.v8i6.pp.4519-4523.

A. K. Dubey, V. Ellappan, R. Paul, and V. Chopra, "Comparative analysis of backtracking and genetic algorithm in n queen’s problem," International Journal of Pharmacy and Technology, vol. 8, no. 4, pp. 25618-25623, Dec. 2016.

P. N. Sharief and B. S. Saini, "Metaheuristic techniques on N-Queen problem: DE VS ABC," International Journal of Applied Engineering Research, vol. 10, no. 55, pp. 4240-4244, 2015.

E. Masehian, H. Akbaripour, and N. Mohabbati-Kalejahi, "Landscape analysis and efficient metaheuristics for solving the n-queens problem," Computational Optimization and Applications, vol. 56, no. 3, pp. 735-764, Dec. 2013, 10.1007/s10589-013-9578-z.

V. Kralev, R. Kraleva, and S. Kumar, "A modified event grouping based algorithm for the university course timetabling problem," International Journal on Advanced Science, Engineering and Information Technology, vol. 9, no. 1, pp. 229-235, 2019, 10.18517/ ijaseit.9.1.6488.

V. Kralev, "Different applications of the genetic mutation operator for symetric travelling salesman problem," International Journal on Advanced Science, Engineering and Information Technology, vol. 8, no. 3, pp. 762-770, 2018, 10.18517/ijaseit.8.3.4867.

F. Arroyo Montoro, S. Gómez-Canaval, K. Jiménez Vega, and A. Ortega De La Puente, "A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors," International Journal of Foundations of Computer Science, vol. 31, no. 1, pp. 7-21, Jan. 2020, 10.1142/S0129054120400018.

A. A. Lapushkin, "Application of Hopfield neural network to the N-queens problem," Advances in Intelligent Systems and Computing, vol. 449, pp. 115-120, 2016, 10.1007/978-3-319-32554-5_15.

V. M. Saffarzadeh, P. Jafarzadeh, and M. Mazloom, "A hybrid approach using particle swarm optimization and simulated annealing for N-queen problem," World Academy of Science, Engineering and Technology, vol. 43, pp. 974-978, 2010.

H. Motameni, S. Bozorgi Hossein, M. Ali Shaban Nezhad, G. Berenjian, and B. Barzegar, "Solving N-queen problem using gravitational search algorithm," Life Science Journal, vol. 10, no. 1, pp. 37-44, Mar. 2013.

D. Chatham, "The n queens problem with forbidden squares," Utilitas Mathematica, vol. 111, pp. 199-210, 2019.

P. Prudhvi Raj, P. Shah, and P. Suresh, "Faster Convergence to N-Queens Problem Using Reinforcement Learning," Communications in Computer and Information Science, vol. 1290, pp. 66-77, 2020, 10.1007/978-981-33-6463-9_6.

S. Saxena, N. Sharma, and S. Sharma, "Parallel computing in genetic algorithm (GA) with the parallel solution of n Queen’s Problem based on GA in multicore architecture," International Journal of Applied Engineering Research, vol. 10, no. 17, pp. 37707-37716, 2015.

C. Jianli, C. Zhikui, W. Yuxin, and G. He, "Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture," Computational Intelligence, vol. 36, no. 4, pp. 1621-1637, Nov. 2020, 10.1111/coin.12300.

J. Cao, Z. Chen, Y. Wang, and H. Guo, "Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem," complexity, vol. 2021, art. no. 6694944, 2021, 10.1155/2021/6694944.

Y. Azuma, H. Sakagami, and K. Kise, "An efficient parallel hardware scheme for solving the N-queens problem," in Proc. 2018 IEEE 12th International Symposium on Embedded Multicore/Many-Core Systems-on-Chip, MCSoC 2018, Hanoi, Viet Nam, 2018, art. no. 8540208, pp. 16-22.

F. J. De Souza and F. L. De Mello, "N-Queens Problem Resolution Using the Quantum Computing Model," IEEE Latin America Transactions, vol. 15, no. 3, art. no. 7867605, pp. 534-540, Mar. 2017, 10.1109/TLA.2017.7867605.

A. Maroosi and R. C. Muniyandi, "Accelerated execution of P systems with active membranes to solve the N-queens problem," Theoretical Computer Science, vol. 551, no. C, pp. 39-54, 2014, 10.1016/j.tcs. 2014.05.004.

Y. Sasaki, M. Fukui, and T. Hirashima, "Development of iOS software n-queens problem for education and its application for promotion of computational thinking," in Proc. 2019 IEEE 8th Global Conference on Consumer Electronics, GCCE 2019, Osaka, Japan, 2019, art. no. 9015331, pp. 563-565.

K. Vassallo, L. Garg, V. Prakash, and K. Ramesh, "Contemporary technologies and methods for cross-platform application development," Journal of Computational and Theoretical Nanoscience, vol. 16, pp. 3854-3859, 2019, 10.1166/jctn.2019.8261.

M. Cuadros, A. De la Fuente, R. Villalta, and A. Barrientos, "Cross-platform enterprise application development framework for large screen surfaces," Smart Innovation, Systems and Technologies, vol. 140, pp. 161-169, 2019, 10.1007/978-3-030-16053-1_15.

M. K. Yahya-Imam, S. Palaniappan, and S. M. Ghadiri, "Investigation of methodical framework for cross-platform mobile application development: Significance of Codename One," International Journal of Computer Aided Engineering and Technology, vol. 11, no. 4-5, pp. 439-448, 2019, 10.1504/IJCAET.2019.100443.

P. S. Mendez, J. C. Silva, and J. L. Silva, "Multi-screen and multi-device game development," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10272 LNCS, pp. 74-83, 2017, 10.1007/978-3-319-58077-7_7.

M. L. Hamzah, A. A. Purwati, E. Rusilawati, and Hamzah, "Rapid application development in design of library information system in higher education," International Journal of Scientific and Technology Research, vol. 8, no. 11, pp. 153-156, Nov. 2019.




DOI: http://dx.doi.org/10.18517/ijaseit.11.5.14523

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development