Fill each of the piece of the puzzle with one of the four available colours. Don’t let pieces of the same colour touch (share a side). – [Author’s description]
Flood Fill (onefifth)
Posted by Stephen
on June 26, 2012
Fill each of the piece of the puzzle with one of the four available colours. Don’t let pieces of the same colour touch (share a side). – [Author’s description]
This is neat! I really dislike how it immediately pushes onto the next level after you complete a puzzle, though, without giving you a chance to minimise your placed colours.
(At one point in secondary school I was convinced that I’d discovered an obvious proof to the four colour problem. I suspect I was overlooking something, though.)
I feel like designing a map that requires more than 4 colors is possible, but I’m not about to vainly go down that road (I’d rather assume I’m wrong).
Man, I spent a lot more time on this game then I thought I would. “Oh this game seems kinda simple I don’t see why I’d keep playing it hey what the hell more levels please!” 😳
Sure enough, the only disproofs I can conjure exist in other kinds of geometries; I’m a do some homework I think.
It’s a proven thing: https://en.wikipedia.org/wiki/Four_color_theorem
You can draw one on a bagel that needs seven!
Yeah, I found the wiki page soon after my lame-ass math attempts.
That’s an interesting point about the torus. I’m currently toying with the minimum number of colors required for a lobachevskian rather than euclidian map. I’m pretty sure it’ll be 4 since you can model the one as a subset of the latter, but what else am I really doing this evening?
Yeah, it’ll be the same for any space with the same topology as a plane or sphere, so the Hyperbolic plane will also take four colors. And conversely as you keep adding holes to a torus, you can require more and more colors.
An interesting variant problem is where for each region you’re given a list of four colors you can use for that region, with the same restriction that the color you pick for each region (from its respective list) can’t match the color of any of its neighbors. It turns out that putting four colors on each list is not enough–that is, there are some maps and list assignments that have no solutions. But with five you can always do it.
The problem of finding such a map where this is impossible was posed several decades before it was solved by a seventeen-year-old. So maybe Terry’s secondary school efforts weren’t entirely in vain.
Also played with some ways of adding complexity like that. Linking pieces that weren’t physically attached and other restrictions. I ended up just keeping it simple, but there are a lot of options.
The way this was designed, adding levels is actually the least fun task.
I started work on a second version with a significantly nicer code-base and a bitmap based level editor. Meaning user-created levels would be fairly trivial. The hard part of that was automating the detection of adjacent pieces. I had an algorithm for doing it but there were a lot of “edge-cases” (hah, pun) that seemed like they needed human decision-making. I ended up just leaving the project in an unfinished state.
However, these kinds of threads popping up really make me reconsider making/releasing a “squeal” of sorts.
I totally agree. The immediately advancing levels was a poor design decision, it’s unfortunately not worth fixing after so long.