MVLSC HomeIssue Contents

Highly Complex 4-Colored Rectangle-free Grids – Solution Unsolved Multiple-Valued Problems
Bernd Steinbach and Christian Posthoff

This paper aims at the rectangle-free coloring of grids using four colors. It has been established that there are bounds for the size of rectangle-free four-colorable grids — outside of these values the grids cannot be colored. For the grids of the sizes 17 × 17, 17 × 18, 18 × 17, and 18 × 18 it is not yet known whether rectangle-free colorings by four colors exist. We present in this paper an approach that solves these problems in a constructive way.

From another point of view this paper aims at the solution of a multiple-valued problem which has an extremely high complexity. Whether at least one of this hardly imaginable large number of patterns satisfies strong additional constraints must be detected. 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.

Keywords: Four-valued coloring, rectangle-free grid, Boolean equation, SATsolver, permutation class, XBOOLE, soft computing.

Full Text (IP)