Sunday, December 04, 2011

[jnijkgng] Generate difficult map colorings

What is an algorithm to generate maps that are difficult for humans to 3-color or 4-color?  Let this be the basis of a puzzle generator.

We wish for planar maps that are not too weird, not having weird shapes like gerrymandering.

3-coloring is NP-complete.

No comments :