Artificial Intelligence and Creativity - Two Requirements to Solve an Extremely Complex Coloring Problem

Bernd Steinbach, Christian Posthoff

2013

Abstract

The topic of this paper is the rectangle-free coloring of grids using four colors which is equivalent to the edge coloring of complete bipartite graphs without complete monochromatic subgraphs K2,2. So far unsolved are the grids of the sizes 17×17, 17×18, 18×17, and 18×18. The number of different 4-color patterns of the grid 18×18 is equal to 4324 ≈ 1.16798∗10195. We summarize in this paper some basic approaches in order to gain the required knowledge. Three creative approaches are steps so solve the most complex grid of the size 18×18. Two advanced creative approaches reduce the required runtime to less than 12 percent.

Paper Citation

in Harvard Style

Steinbach B. and Posthoff C. (2013). Artificial Intelligence and Creativity - Two Requirements to Solve an Extremely Complex Coloring Problem . In Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8565-39-6, pages 411-418. DOI: 10.5220/0004183004110418

in Bibtex Style

@conference{icaart13,
author={Bernd Steinbach and Christian Posthoff},
title={Artificial Intelligence and Creativity - Two Requirements to Solve an Extremely Complex Coloring Problem},
booktitle={Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2013},
pages={411-418},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004183004110418},
isbn={978-989-8565-39-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 5th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Artificial Intelligence and Creativity - Two Requirements to Solve an Extremely Complex Coloring Problem
SN - 978-989-8565-39-6
AU - Steinbach B.
AU - Posthoff C.
PY - 2013
SP - 411
EP - 418
DO - 10.5220/0004183004110418