THE SOLUTION OF ULTRA LARGE GRID PROBLEMS
Bernd Steinbach · 2012
SAT solvers have grown in power over the last decades. However, both certain intentions of their application and the complexity of the problems are still obstacles to their successful utilization. Here we are facing a problem where an extremely small fraction of solutions must be found in the unimaginably large search space of more than 10 195. Up to now SAT solvers were able to find solutions for subproblems with the size of approximately 10 135. Hence, it was our challenge to bridge the gap of 10 60. In this paper we focus on a subproblem of the basic graph coloring problem. Due to the estimated complexity it seemed to be hopeless to find solutions. However, we enjoyed this extreme challenge and studied several approaches beyond the application of SAT solvers which allowed finally to solve the so far open graph coloring problem.