In this paper, we propose a new arc consistency algorithm, AC-8, which requires less computation time and space than AC-6 and AC-7 proposed by Bessiere et al. (1994, 1995). The main idea of the optimization is the divide-and-conquer strategy, thereby decomposing an arc consistency problem into a series of smaller ones and trying to solve them in sequence. In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistency propagation (in the sense that some of them are executed before the entire inconsistency checking has been finished), each constraint subnetwork will be searched with a gradually shrunk domain. In addition, the technique of AC-6 (Bessiere, 1994) can be integrated into our algorithm, leading to a further decrease in computational complexity.