On traversing labyrinths by automata that leave nonerasable marks

The problem of traversal of plane labyrinths by automata was set by C. Shannon at the beginning of sixties. It is known that there exists no finite automaton which can traverse an arbitrary preassigned labyrinth. It is natural to carry on the search of the positive solution of the problem of the traversal of labyrinths by automata in two directions. The first direction is concerned with consideration of more restricted classes of labyrinths and the second one is concerned with extension of capabilities of automata traversing labyrinths. In this paper it is shown that there exists an automaton leaving one unremovable label (colour) in nodes of a labyrinth which can traverse an arbitrary rectangular labyrinth.