Recursive Path-finding in a Dynamic Maze with Modified Tremaux's Algorithm

Authors: Nien-Zheng Yew, Kung-Ming Tiong, Su-Ting Yong

Abstract:

Number Link is a Japanese logic puzzle where pairs of same numbers are connected using lines. Number Link can be regarded as a dynamic multiple travelers, multiple entries and exits maze, where the walls and passages are dynamically changing as the travelers move. In this paper, we apply the Tremaux’s algorithm to solve Number Link puzzles of size 8x8, 10x10 and 15x20. The algorithm works well and produces a solution for puzzles of size 8x8 and 10x10. However, solving a puzzle of size 15x20 requires high computer processing power and is time consuming.

Keywords: Number Link, maze, puzzle, Tremaux’s algorithm

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077030

References:

[1] D. Schulz, C. Kouri, and J.P. Huston, "Behavior on the water maze platform: relationship to learning and open field exploration in aged and adult rats," Brain Research Bulletin, vol. 74, no. 4, pp. 206-215, Sept. 2007.
[2] A. Ennceur, S. Michalikova, R.V. Rensburg and P.L. Chazot, "Detailed analysis of the behavior and memory performance of middle-aged male and female CD-1 mice in a 3D maze," Behavioural Brain Research, vol. 187, no. 2, pp. 312-326, Mar. 2008.
[3] J.L. Bizon, C.L. LaSarge, K.S. Montgomery, A.N. McDermott, B. Setlow and W.H. Griffith, "Spatial reference and working memory across the lifespan of male Fischer 344 rats," Neurobiology of Aging, vol. 30, no. 4, pp. 646-655, 2009.
[4] M. Babula, "Simulated maze solving algorithms through unknown mazes," in 2009 Proc. Of XVIllth Concurrency, Specification and Programming Workshop, pp. 13-22.
[5] Nikoli Co., Ltd. (2001-2011). "Nikoli Web," Retrieved October 18. 2011 from http://www.nikoli.cobien/.
[6] Nikoli Co. Ltd., Number Link, Taiwan: Grimm Press, 2006.