Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open Multiple-Valued Problems

• Main Authors: Steinbach, B., Posthoff, C.
• Format: Conference Proceeding
• Language: English
• Subjects: Boolean equation; Color; Computational modeling; Data structures; Equations; four-valued coloring; Image color analysis; Mathematical model; rectangle-free grid; SAT-solver; Vectors; XBOOLE
• ISSN: 0195-623X; 2378-2226
• DOI: 10.1109/ISMVL.2012.12

This paper aims at the rectangle-free coloring of grids using four colors. It has been proven in a well developed theory that there is an upper bound of rectangle-free 4-colorable grids as well as a lower bound of grids for which no rectangle-free color pattern of four colors exist. Between these tight bounds the grids of the size 17×17, 17×18, 18 × 17, and 18 ×18 are located for which it is not known until now whether a rectangle-free coloring by four colors exists. We present in this paper an approach that solves all these open problems. From another point of view this paper aims at the solution of a multiple-valued problem having an extremely high complexity. There are 1.16798 * 10 195 different grids of four colors. It must be detected whether at least one of this hardly imaginable large number of patterns satisfies strong additional conditions. In order to solve this highly complex problem, several approaches were taken into account to find out properties of the problem which finally allowed us to calculate the solution.