We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

Genetic based Algorithm for N - Puzzle Problem

by Harsh Bhasin, Neha Singla
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 51 - Number 22
Year of Publication: 2012
Authors: Harsh Bhasin, Neha Singla
10.5120/8347-1894

Harsh Bhasin, Neha Singla . Genetic based Algorithm for N - Puzzle Problem. International Journal of Computer Applications. 51, 22 ( August 2012), 44-50. DOI=10.5120/8347-1894

@article{ 10.5120/8347-1894,
author = { Harsh Bhasin, Neha Singla },
title = { Genetic based Algorithm for N - Puzzle Problem },
journal = { International Journal of Computer Applications },
issue_date = { August 2012 },
volume = { 51 },
number = { 22 },
month = { August },
year = { 2012 },
issn = { 0975-8887 },
pages = { 44-50 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume51/number22/8347-1894/ },
doi = { 10.5120/8347-1894 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:51:04.389953+05:30
%A Harsh Bhasin
%A Neha Singla
%T Genetic based Algorithm for N - Puzzle Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 51
%N 22
%P 44-50
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

N – Puzzle problem is an important problem in mathematics and has implications in Artificial Intelligence especially in gaming. The work presented reviews the previous attempts to solve this problem. A formal definition of the problem has been presented. The reason why it is considered as NP hard problem and why Genetic Algorithms (GAs) is applied has been explained. The work here by presents a GAs based algorithm to solve N – Puzzle problem. The algorithm has been analyzed and it is a sturdy belief that the presented algorithm has complexity better than most of the works studied. The work is a part of larger endeavor to solve all NP Hard problems by GAs.

References
  1. Harsh Bhasin and Neha Singla, (2012), "Harnessing Cellular Automata and Genetic Algorithms To Solve Travelling Salesman Problem', International Conference on Information, Computing and Telecommunications, (ICICT -2012), pp. 72 – 77.
  2. Harsh Bhasin and Gitanjali, (2012), "Harnessing Genetic Algorithm for Vertex Cover Problem", International Journal on Computer Science and Engineering (IJCSE), Vol. 1, Issue 2, pp. 218 - 223.
  3. Harsh Bhasin and Nishant Gupta, (2012), Randomized algorithm approach for solving PCP, IJCSE 2012; 4(1):106-113. ICID: 976303
  4. Harsh Bhasin and Neha Singla, (2012), Modified Genetic Algorithms Based Solution to Subset Sum Problem, IJARAI Vol. 1 (1).
  5. Hayes, Richard. (2001), 'The Sam Loyd 15-Puzzle'. - Dublin, Trinity College Dublin, Department of Computer Science, TCD-CS-2001-24, pp28.
  6. Richard E. Korf and Larry A. Taylor, (1996), 'Finding optimal solutions to the twenty-four puzzle', in Proceedings AAAI 1996, pp. 1202–1207
  7. Bauer, Bernard, (1994), The Manhattan Pair Distance Heuristic for the 15 Puzzle, Paderborn, Germany.
  8. Chris Calabro, (2005), Solving the 15-Puzzle.
  9. Zygmunt Pizlo; Zheng Li, (2005), Solving combinatorial problems: The 15-puzzle. Memory & Cognition, Vol. 33 Issue 6, p1069.
  10. Ariel Felner and Amir Adler, (2005), "Solving the 24 Puzzle with Instance Dependent Pattern Databases". Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA-05), pages 248-260.
  11. Ariel Felner, Richard E. Korf and Sarit Hanan, (2004), "Additive Pattern Database Heuristics", Journal of Artificial Intelligence Research (JAIR), 22:279-318.
  12. Alexis Drogoul and Christophe Dubreuil, (1993), 'A Distributed Approach to. N-Puzzle Solving', Proceedings of the Distributed Artificial Intelligence, pp. 95 – 108.
  13. Graham Kendall, Andrew J. Parkes, Kristian Spoerer, (2008), A Survey of NP-Complete Puzzles. ICGA Journal 31(1), pp. 13-34.
  14. http://www. cs. bham. ac. uk/~mdr/teaching/modules04/java2/TilesSolvability. html
  15. Johnson, W. W. (1879). Notes on the "15" Puzzle. American Journal of Mathematics 2(4):397–404.
  16. Story, W. E. (1879) "Notes on the '15 Puzzle. II. ' " , American Journal of Mathematics 2, 399-404.
  17. Archer, Aaron F. (1999), "A modern treatment of the 15 puzzle", The American Mathematical Monthly 106 (9): 793–799.
  18. S. Thrun, (1995) "Learning to Play the Game of Chess", In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems(NIPS) 7, Cambridge, MA, MIT Press.
  19. H. Bhasin and S. Bhatia, (2011), "Application of Genetic Algorithms in Machine learning", IJCSIT, Vol. 2 (5).
Index Terms

Computer Science
Information Sciences

Keywords

N – Puzzle problem Genetic Algorithms NP Hard Solvability Iterative Deepening

Powered by PhDFocusTM