Maze Construction by Using Characteristics of Eulerian Graphs
Tomio Kurokawa *
Department of Information Science, Aichi Institute of Technology, 1247 Yachigusa, Yagusa-cho, Toyota 470-0392, Japan.
*Author to whom correspondence should be addressed.
Abstract
This paper describes the method to construct a maze for which the solution path goes along with the line of a closed one stroke drawn curve. If the crossing of the curve is considered a vertex and the curve between the two crossings (vertices) an edge, the closed curve becomes an Eulerian graph. Since maze does not allow the solution path to intersect itself, the proposed method constructs the path with no crossing; but it goes through every part of the original curve only once. In the process of the path construction, it makes use of the characteristics of Eulerian Graph. The theory was developed and a number of experiments were successfully conducted in some different situations.
Keywords: Maze, closed one stroke curve, contour cycle, Eulerian graph, bipartite graph.