I heard that part of the proof of the four-color theorem produced a set of maps which are fairly difficult (but of course still possible) to color. These can form a nice set of puzzles for humans. I'm imagining a mouse-clicking Flash or Java game.
If those don't work, three coloring is NP-complete, so challenging three-color puzzles may be designed. One may go to the extreme to design three-color map-coloring versions of various NP monetary prize problems: RSA factoring, Certicom ECC Diffie-Hellman, EFF Megaprimes, Eternity 2.
No comments :
Post a Comment