MVLSC Home · Issue Contents · Forthcoming Papers
Known and New Insides to the Problem of Rectangle-free Four-colored Grids
Bernd Steinbach
This paper describes a sequence of approaches leading finally to the solution on an extremely complex multiple-valued problem of computing rectangle-free four-colored grids. This problem is easy to describe, extremely hard to solve, but the verification of a found solution is a simple task.
At the point in time we starting this research it was known that there are such rectangle-free four-colored grids of small sizes, no such grids of large sizes, but it was unknown whether rectangle-free four-colorings exist of grid with the dimension 17 × 17, 17 × 18, 18 × 17, 18 × 18, 12 × 21, and 21 × 12. The reason why many approaches of scientists around the world failed to solve this task is the extremely high complexity. The number of different colorings of the grid G18,18 is equal to 418·18 ≈ 1.16798 · 10195.
This paper summarizes the main steps of our research to compute rectangle-free four-colored grids of sizes 17 × 17, 17 × 18, 18 × 17, and 18 × 18. Some so far unpublished results complete the insides to this problem. We refer to [9] regarding our solutions of the remaining grids 12 × 21 and 21 × 12.
Keywords: Four-valued coloring, rectangle-free grid, extremely complex task, rotation symmetry, Boolean equation, SAT-solver, XBOOLE