Bergen KARABULUT, Atilla ERGÜZEN, Halil Murat ÜNVER

N-Vezir Problemi için Lineer Zamanlı Örüntü Temelli Algoritma

N-vezir problemi, nxn boyutundaki bir satranç tahtasına n adet vezirin herhangi iki vezir birbirine saldırmayacak şekilde yerleştirilmesidir. Bu problem literatürde değinilen VLSI testi, trafik kontrol işi planlama, veri yönlendirme, ölümcül kilitlenme ya da tıkanıklık önleme, dijital görüntü işleme ve paralel bellek depolama şemaları gibi çeşitli kullanım alanlarından dolayı önemlidir. Ayrıca bu problem, yeni yapay zekâ arama tekniklerinin geliştirilmesi için bir referans noktası olarak kullanılmaktadır. Fakat bilindiği üzere bu problemin çözümde sıklıkla kullanılan geri-izleme algoritmaları, katlanarak büyüyen zaman karmaşıklığından dolayı büyük n değerleri için tüm çözümleri üretememektedir. Bu nedenle, her bir n değeri için tüm çözümleri bulmak yerine bir veya daha fazla çözüm üretebilmek için çeşitli yöntemler önerilmiştir. Bu çalışmada, tüm n değerleri (n>3) için en az bir tane eşsiz çözüm üreten bir örüntü tespit edilmiştir. Bu örüntü kullanılarak, çok büyük n değerlerinde bile lineer zamanda en az bir tane eşsiz çözüm üreten yeni bir algoritma geliştirilmiştir. O(n) zaman karmaşıklığı ile geliştirilen algoritma, n-vezir problemine oldukça hızlı çözüm üretmektedir ve hatta bazı değerler için lineer zamanda (n-1)/2 adet eşsiz çözüm üretmektedir.

Anahtar Kelimeler:

N-vezir Problemi, NP-hard, NP-complete, kısıt sağlama problemi, optimizasyon problemi

A Linear Time Pattern Based Algorithm for N-Queens Problem

The n-queens problem is the placing of n number of queens on an nxn chessboard so that no two queens attack each other. This problem is important due to various usage fields such as VLSI testing, traffic control job scheduling, data routing, dead-lock or blockage prevention, digital image processing and parallel memory storage schemes mentioned in the literature. Besides, this problem has been used as a benchmark for developing new Artificial Intelligence search techniques. However, it is known that backtracking algorithms, one of the most frequently used algorithms to solve this problem, cannot produce all solutions in large n values due to the exponentially growing time complexity. Therefore, various methods have been proposed for producing one or more solutions, not all solutions for each n value. In this study, a pattern based approach that produces at least one unique solution for all n values (n>3) was detected. By using this pattern, a new algorithm that produces at least one unique solution for even very large n values in linear time was developed. The developed algorithm with О(n) time complexity produces quite faster solution to n-queens problem and even in some values, this algorithm produces (n-1)/2 unique solutions in linear time.

Keywords:

N-queens Problem, NP-hard, NP-Complete, constraint satisfaction problem, optimization problem,

PDF

___

[1] Abramson B., and Yung M.M., “Construction through decomposition: A linear time algorithm for the n-queens problem”, Colombia University Computer Science Technical Reports, CUCS-129-84, (1984).
[2] Sosic R., and Gu J., “A polynomial time algorithm for the n-queens problem”, ACM SIGART Bulletin, 1(3): 7-11, (1990).
[3] Waqas M., and Bhatti A.A., “Optimization of N+ 1 Queens Problem Using Discrete Neural Network”, Neural Network World, 27(3): 295, (2017).
[4] Wang C.N., Yang S.W., Liu C.M., and Chiang, T., “A hierarchical decimation lattice based on N-queen with an application for motion estimation”, IEEE signal processing letters, 10(8): 228-231, (2003).
[5] Bell J., and Stevens B., “A survey of known results and research areas for n-queens”, Discrete Mathematics, 309(1): 1-31, (2009).
[6] Murali G., Naureen S., Reddy Y.A., Reddy M.S., JNTUA-Pulivendula J.P., and JNTUA-Pulivendula J.P. “Graphical Simulation of N Queens Problem”, International Journal of Computer Technology and Applications, 2(6), (2011).
[7] Güldal S., Baugh V., and Allehaibi S., “N-Queens solving algorithm by sets and backtracking”, In SoutheastCon, IEEE, 1-8 (2016).
[8] Lijo V.P. and Jose J.T., “Solving N-Queen Problem by Prediction”, IJCSIT International Journal of Computer Science and Information Technologies, 6(4): 3844-3848, (2015).
[9] Sosic R. and Gu J., “3,000,000 queens in less than one minute”, ACM SIGART Bulletin, 2(2): 22-24, (1991).
[10] Matsuda S., “Theoretical characterizations of possibilities and impossibilities of Hopfield neural networks in solving combinatorial optimization problems”, In Neural Networks, 1994. IEEE World Congress on Computational Intelligence, 1994 IEEE International Conference, (7): 4563-4566, (1994).
[11] Sosic R. and Gu, J., “Fast search algorithms for the n-queens problem”, IEEE Transactions on Systems, Man, and Cybernetics, 21(6): 1572-1576, (1991).
[12] Hu X., Eberhart R.C. and Shi Y., “Swarm intelligence for permutation optimization: a case study of n-queens problem”, In Swarm intelligence symposium, 2003, SIS'03, Proceedings of the 2003 IEEE, 243-246, (2003).
[13] Meng F. and Wu S., “Research of hybrid genetic algorithm in n-queen problem based on HCI”, In Intelligent Information Technology Application, 2008. IITA'08. Second International Symposium on, IEEE, (2): 3-7, (2008).
[14] Khan S., Bilal M., Sharif M., Sajid M. and Baig R., “Solution of n-queen problem using aco”, In Multitopic Conference, 2009. INMIC 2009. IEEE 13th International, 1-5, (2009).
[15] Turky A. and Ahmad A., “Using Genetic Algorithm for Solving N -Queens Problem”, In 2010 International Symposium on Information Technology, IEEE, Kuala Lumpur, 745-747, (2010).
[16] Motameni H., Bozorgi S.H., Nezhad M.A.S., Berenjian G. and Barzegar B., “Solving N-Queen problem using Gravitational Search Algorithm”, Life Science Journal-Acta Zhengzhou University Overseas Edition, 10(1): 37-44, (2013).
[17] Maazallahi R., Niknafs A. and Arabkhedri P.A., “Polynomial-time DNA computing solution for the n-queens problem”, Procedia-Social and Behavioral Sciences, 83, 622-628, (2013).
[18] Habiboghli A. and Jalali T., “A Solution to the N-Queens Problem Using Biogeography-Based Optimization”, IJIMAI, 4(4): 20-26, (2017).
[19] Amooshahi A., Joudaki M., Imani M. and Mazhari N., “Presenting a new method based on cooperative PSO to solve permutation problems: A case study of n-queen problem”, In Electronics Computer Technology (ICECT), 2011 3rd International Conference on, IEEE, (4): 218-222, (2011).
[20] Sosic R. and Gu J., “A polynomial time algorithm for the n-queens problem”, ACM SIGART Bulletin, 1(3): 7-11, (1990).
[21] Sosic R. and Gu J., “Efficient local search with conflict minimization: A case study of the n-queens problem”, IEEE Transactions on Knowledge and Data Engineering, 6(5): 661-668, (1994).
[22] Lijo V. and Jose J.T., “Solving N-Queen Problem by Prediction” Int. J. Comput. Sci. Inf. Technol, (6), 3844-3848, (2015).
[23] El-Qawasmeh E. and Al-Noubani K., “Reducing the Time Complexity of the N-Queens Problem”, International Journal on Artificial Intelligence Tools, 14(03):545-557, (2005).
[24] Rohith S., Gupta A. and Pramodh S., “A Novel Method for Solving N-Queens Problem”, Int. J. Adv. Res. Comput. Sci. Softw. Eng., 3(10), (2013).