4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters


  • Victoria María Sanz III LIDI, Facultad de Informática, Universidad Nacional de La Plata, La Plata, Buenos Aires, Argentina
  • Armando Eduardo De Giusti III LIDI, Facultad de Informática, Universidad Nacional de La Plata, La Plata, Buenos Aires, Argentina
  • Marcelo Naiouf III LIDI, Facultad de Informática, Universidad Nacional de La Plata, La Plata, Buenos Aires, Argentina


Multi -objective problems, Discrete optimization, Superlinearity, Parallel algorithms


In this paper, an analysis of the 4-(N2-1) Puzzle, which is a generalization of the (N2-1) Puzzle, is presented. This problem is of interest due to its algorithmic and computational complexity and its applications to robot movements with several objectives. Taking the formal definition as a starting point, 4 heuristics that can be used to predict the best achievable objective and to estimate the number of steps required to reach a solution state from a given configuration are analyzed. By selecting the objective, a sequential and parallel solution over a cluster is presented for the (N2-1) Puzzle, based on the heuristic search algorithm A*. Also, variations of the classic heuristic are analyzed. The experimental work focuses on analyzing the possible superlinearity and the scalability of the parallel solution on clusters, by varying the physical configuration and the dimension of the problem. Finally, the suitability of the heuristic used to assess the best achievable objective in the 4-(N2-1) Puzzle is analyzed.


Download data is not yet available.


[1] Sergienko I., Shylo V. Problems of discrete optimization: Challenges and main approaches to solve them. New York: Springer; 2006; 42(4):465-482.
[2] Lambur H, Shaw B. Parallel State Space Searching Algorithms. 2004. www.metablake.com/parallel_search_project
[3] Grama A., Kumar V. State of the art in parallel search techniques for discrete optimization problems. IEEE Trans. on Knowledge and Data Engineering, 1999.
[4] Parberry I. A Real Time Algorithm for the (n2-1) Puzzle. Information Processing Letters 1995;56(1): 23-28.
[5] Ferreira A., Pardalos P. Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques. New York: Springer; 1996.
[6] Reinefeld A. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. In: Proc. of the 13th International Joint Conference on Artificial Intelligence; Chambery Savoi, France; 1993. p. 248-253.
[7] Hanson O., Mayer A., Yung M. Criticizing Solutions to Relaxed Model Yields Powerful Admissible Heuristics. Information Sciences 1992; 63(3): 207-227.
[8] Korf R. E., Schultze P. Large-scale parallel breadth-first search. In: Proc. of the 20th National Conference on Artificial Intelligence; Pittsburgh, USA; 2005. p. 1380-1385.
[9] Anderson T., Culler D., Patterson D. A Case for NOW (Networks of Workstations). IEEE Micro 1995; 15(1): pp. 54-64.
[10] Bohn C., Lamont G. Load Balancing for Heterogeneous Clusters of PCs. Future Generation Computer Systems, 2002; 18(3): 389-400.
[11] Grama A., Gupta A., Karypis G., Kumar V. An Introduction to Parallel Computing. Design and Analysis of Algorithms. Pearson Addison Wesley; 2003.
[12] Leopold C. Parallel and distributed computing. A survey of models, paradigms, and approaches. New York: Wiley; 2001.
[13] Quiin M. J. Parallel Computing: Theory and Practice. McGraw-Hill Companies; 1993.
[14] Buyya R. High Performance Cluster Computing: Architectures and Systems. Prentice-Hall; 1999.
[15] Hwang K. Advanced Computer Architecture. Parallelism, Scalability, Programmability. McGraw Hill; 1993.
[16] Helmbold D., McDowell C. Modeling speedup(n) greater than n. IEEE Trans. on Parallel and Distributed Systems, 1990; 1(2): 250-256.
[17] Manquinho V., Marques-Silva J. Search Pruning Techniques in SAT-Branch-and-Bound Algorithms for Binate Covering Problem. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2002; 21(5): 505-516.
[18] Sanz V., Chichizola F., Naiouf M., De Giusti L.,De Giusti A. Superlinealidad sobre Clusters. Análisis experimental en el problema del Puzzle N2-1. In: Proc. of the XIII Congreso Argentino de Ciencias de la Computación; Chaco-Corrientes, Argentina; 2007. p. 1300-1309.
[19] Wilkinson B., Allien M. Parallel Programming: Techniques and Applications Using Network Workstation and Parallel Computers. Pearson Prentice Hall; 2005.
[20] Fitch R., Butler Z., Rus D. Reconfiguration Planning Among Obstacles for Heterogeneous Self-Reconfiguring Robots. In: Proc. of the IEEE International Conference on Robotics and Automation; 2005. p. 117-124.
[21] Sanz V., Chichizola F., De Giusti A, Naiouf M, De Giusti L. Análisis de Performance en el procesamiento paralelo sobre Clusters del problema del Puzzle N2-1. ENIEF 2008. XVII Congreso sobre Métodos Numéricos y sus Aplicaciones. ISSN: 1666-6070
[22] Ratner D. and Warmuth W. Finding a shortest solution for the NxN extension of the 15-Puzzle is intractable. AAAI-86, 168-172
[23] Sanz V. Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster. Análisis de Performance. Informe Final de Trabajo de Grado; 2009.
[24] Dijkstra E., Scholten C. Termination detection for diffusing computations. Information Processing Letters 1980; 11(1):1-4.




How to Cite

Sanz, V. M., De Giusti, A. E., & Naiouf, M. (2010). 4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters. Journal of Computer Science and Technology, 10(02), p. 86–90. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/732



Original Articles

Most read articles by the same author(s)

1 2 3 4 > >>