In this paper, we propose a new arcconsistency algorithm, AC-8, whichrequires less computation time andspace than AC-6 and AC-7. The main idea oftheoptimization is the divide-and-conquer strategy, thereby decomposing anarcconsistency problem into a series of smaller ones and trying tosolve them insequence. In this way, not only the space complexity butalso the time complexity canbe reduced. The reason for this is that dueto the ahead of time performedinconsistency propagation (in the sensethat some of them are executed before theentire inconsistency checkinghas been finished), each constraint subnetwork will besearched with agradually shrunk domain. In addition, the technique of AC-6 canbeintegrated into our algorithm, leading to a further decrease incomputationalcomplexity.