We consider the problem of asking whether a given d-dimensional rectangle Ro is covered with the union of other d-dimensional rectangles Ri or not. This problem, called the multi-dimensional rectangle cover problem, is a modification of the well-known satisfiability problem. The Davis–Putnum method and the local search method, which are representative methods for the satisfiability problem, can be generalized to this problem. In this paper, we propose a new algorithm called the MDP method. Our experiments show that, in both the multi-dimensional rectangle cover problem and the satisfiability problem, the MDP method is more efficient than the Davis–Putnum method and the local search method for those problem instances in which the whole or most of the area of Ro is covered and the rectangles Ri slightly overlap one another.
