Progress in Systems and Telecommunication Engineering

DLINE Journals portal

Home

New Journals

Browse Journals

Journal Prices

For Authors

Print ISSN:
Online ISSN:

About JIO
	DLINE Portal Home Home Aims & Scope Editorial Board Current Issue Next Issue Previous Issue Sample Issue Upcoming Conferences Self-archiving policy Alert Services Be a Reviewer Publisher Paper Submission Subscription Contact us

How To Order
	Order Online Price Information Request for Complimentary Print Copy

For Authors
	Guidelines for Contributors Online Submission Call for Papers Author Rights

RELATED JOURNALS

Journal of Digital Information Management (JDIM)

Journal of Multimedia Processing and Technologies (JMPT)

International Journal of Web Application (IJWA)

Progress in Systems and Telecommunication Engineering

A Non-asymptotic Space Complexity of a Backtracking Algorithm for the N-queens Problem

Adrijan Bozinovski, Stevo Bozinovski
School of Computer Science and Information Technology, University American College Skopje Macedonia & South Carolina State University, Orangeburg, SC USA

Abstract: In this research we have studied the space complexity function to offset the shortcoming in the application memory. This is applied particularly when solving the N-queens issue. We found that it is essential to design the required memory space and to monitor the space complexity function in some input domain. We have described the detailed space complexity which is given for when the condition the value of N is less than forty.

Keywords: Space Complexity, Back-tracking Algorithm, Nqueens Problem A Non-asymptotic Space Complexity of a Backtracking Algorithm for the N-queens Problem

DOI:

Full_Text PDF 271 KB Download: 358 times

References:

[1] van Beek, P. (2006). Backtracking Search Algorithms. In Rossi, F. F., van Beck, P., Walsh, T. (eds.) Handbook of Constraint Programming, Elsevier, pp. 85-134, 2006
[2] Brassard, G., Bratley, P. (1996). Fundamentals of Algorithmics. Prentice Hall, 1996.
[3] Rich, E. (1983). Artificial Intelligence, McGraw-Hi11, 1983.
[4] Golomb, S., Baumert, L. (1965). Backtrack programming. Journal of the ACM, 12, p516-524.
[5] Fillmore, J., Williamson, S. (1974). On backtracking: A combinatorial description of the algorithm. SIAM Journal of Computing, 3, p 41-55.
[6] Bitner, J., Reingold, E. (1975). Backtrack programming techniques. Communications of the ACM, 18, p 651-656.
[7] Nicol, D. (1986). Expected performance of m-solution backtracking. SIAM Journal on Computation, 17(1), p 114-127, 1988.
[8] Stone, H., Sipala, P. (1986). The average complexity of depth-first search with backtracking and cutoff. IBM Journal of Research and Development, 30(3), pp. 242-258, 1986.
[9] Nauck, F. (1850). Schach. Illustrierter Zeitung 361:352, 1850.
[10] Pauls, E. (1874). Das Maximalproblem der Damen auf dem Schachbrete. Deutsche Schachzeitung, Bd. 29, p 129-134, 257-267.
[11] Foulds, L., Johnson, D. (1984). An application of graph theory and integer programming: Chessboard nonattacking puzzles. Mathematics Magazine, 57(3), p 95-104.
[12] Clapp, R., Mudge, T., Vol, R. (1986). Solutions to the N-queens problem using tasking in Ada. SIGPLAN Notices, 21, p 99-110.
[13] Erbas, C., Tanik, M., Aliyaziciogly, Z. (1992). Linear congruence equations for the solution of the N-queens problem. Information Processing Letters, 41, p 301-306.
[14] Rivin, L., Zabih, R. (1992). A dynamic programming solution to the n-queens problem, Information Processing Letters, 41, p 253-256.
[15] Crawford, K. (1992). Solving the n-queens problem using genetic algorithms. In: Proceedings ACM/SIGAPP Symposium on Applied Computing, Kanzas City, p 1039-1047.
[16] Shagrir, O., A neural net with self-inhibiting units for the N-queens problem. International Journal of Neural Systems, 3, p 249-252.
[17] Han, J., Liu, L., Lu, T. (1998). Evaluation of declarative n-queens recursion: A deductive database approach. Information Sciences, 105, p 69-100.
[18] Sosic, R., Gu, R. (1991). Fast search algorithms for the N-queens problem. IEEE Transactions on Systems, Man, and Cybernetics, 21(6), p 1572-1576.
[19] Sosic, R. (1994). A parallel search algorithm for the N-queens problem. In: Proceedings Parallel Computing and Transputer Conference, Wollongong, p 162-172.
[20] Knuth, D. (1997). The art of Computer Programming. Addison Wesley, 1997.
[21] Bo2inovski, A., Ackovska, N. (2012). The Binary Tree Roll Operation: Definition Explanation and Algorithm, International Journal of Computer Applications, 46 (8), p 40-47.
[22] BoNnovslci, A., Taney, G., Stojdevska, B., Patovski, V., Ackovska, N. (2016). Time complexity analysis of the binary tree roll algorithm, Journal of Information Technology and Applications, 6 (2), p 53-62.
[23] Bo2inovski, A., Taney, G., Stojtevska, B., Palovski, V., Ackovska, N. (2017). Space complexity analysis of the binary tree roll algorithm, Journal of Information Technology and Applications, 7 (1), p 9-19.
[24] Taney, G., Bcdinovski, A. (2017). A linear time algorithm for rolling binary trees, In: Proceedings of the 17th IEEE International Conference on Smart Technologies IEEE EUROCON 2017, Ohrid, Macedonia, p 255-260.
[25] Bozinovski, A., Bozinovski, S. (2004). N-queens pattern generation: An insight into space complexity of a backtracking algorithm, In: Proceedings of the 3rd International Symposium on Information and Communication Technologies. LasVegas, Nevada, USA, p 281-286.
[26] The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2010, Sequence A000170.
[27] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms. Third Edition. The MIT Press.

DLINE Journals portal