Ultradiscretization is a limiting procedure transforming a given difference equation into a cellular automaton. The cellular automaton constructed by this procedure preserves the essential properties of the original equation, such as the structure of exact solutions for integrable equations. In this article, a cellular automaton analog of the multidimensional Allen-Cahn equation which is not an integrable system is constructed by the ultradiscretization. Moreover, the traveling wave solutions for the resulting cellular automaton are given. The shape, behavior and stability of the solutions in ultradiscrete systems are similar to those in continuous systems.