I'm making a puzzle game where you flood fill intersected polygons, but the same colors can't be touching (diagonal is okay)

This is where I got the idea
Flood Fill (Game)

I want to be able to easily make puzzles (MSPaint would be ideal, then I could read it into the game).
Any other suggestions would work, also!

This is what the game will look like.



I want the alogrithm to tell me the least number of colors possible. Maybe, if there's a way, a solving alogrithm?

Any ideas? Thanks in advance!

If you only have 4 total colors, like the game in the link, then you can use a brute force method to determine the minimum number of colors required.  You run a few all possible combination tests.  First, you test with 2 colors (assuming no puzzle is solvable with 1 color) and see if the puzzle is solvable with 2 colors.  Then you test with 3 colors.  If isn't solvable with 2 or 3 colors, then you can assume that it is only solvable with 4 colors.  Of course, that last assumption is based on another assumption that you create solvable puzzles with your color limit.

If each puzzle is 20 pieces or less, it should run in a reasonable amount of time.  However, you would still want to compute these beforehand and not at runtime.

I'm still trying to figure out a way to test this :( There's so many possibilities. If I used a brute force method, and tried for 2, 3, etc. (not that bad). BUT I would have to try all the combinations of colors, which would be hundreds or thousands of possibilities to check. This could take quite a while.

hundreds, thousands and millions usually aren't that big of a deal.  It is when you hit billions that things really start to slow down.  That was why I said 20 or less pieces with 4 colors (or max testing of 3 colors) is 3^20 or about 348 million combinations.  You can certainly run that check in a reasonable amount of time.

You also have to remember that this kind of work would be done on your time and not the users.  You would want to calculate these during development and store them later for use during actual gameplay.

EDIT: I miscounted...  3^20 is 3.5 billion...  still doable, though =)

cable729:

I want the alogrithm to tell me the least number of colors possible. Maybe, if there's a way, a solving alogrithm?

This is actually a remarkably complex problem.

Jumping to the answer: any possible map can be colored using just four unique colors.  Some simple maps can be colored using just three.

The proof of this is sufficiently complex that it took mathematicians many years to work out, though: this was an unsolved research problem for a significant amount of time!

http://en.wikipedia.org/wiki/Four_color_theorem

I think I've figured it out, unless I overlooked something (quite possible, I didn't take years to prove it, just found a pattern in a couple minutes).

Look like it's solved with the least colors (i hope it is haha)

They require 2, 3, and 4 colors.



Now, if I place a single point in each region, and connect the points if the regions touch eachother...



Notice anything?

The number of colors needed is equal to the vertex with the most rays (segments, its been a while since geometry) coming off of it PLUS ONE.

Comments? Please disprove me if I'm wrong!

EDIT: THANK YOU SO MUCH FOR THE LINK, SHAWN! It helped me out so much!

In your last picture, you can put a green box next to the purple box and increase the link count, but not the color count.

You can easily have a graph where nodes have three and eight edges, and still only need three colors for a coloring.

I also discovered this shortly after posting. I'm looking into some patterns...

What I can think of to check:

-Take a list of the nodes with the top number of vertices
-Go through them until they "work" (The yellow node doesn't work on yours Jwatte)

To check if they "work" or are "true"

See for each of the nodes they connect to:
-How many connecting nodes they share with the original node we're checking
-(Trying to find a pattern here somewhere that can tell us if it works)

I'm pretty sure there is no simple solution to this problem. Or rather, if there is, it must be far from obvious, since it took a lot of smart mathematicians many years to prove the four color theorem! (ok, that's a slight stretch: a proof for this theorem basically requires an algorithm to compute how many colors are needed for any given map, plus an analysis of the halting problem for that algorithm. But the algorithm is a big part of it).

My advice would be to try brute-forcing this, and if that turns out to be too slow, just enter the number of colors by hand at the same time as you create each puzzle bitmap.

Shawn Hargreaves:

My advice would be to try brute-forcing this

Which is basically how the solution to the four-color problem was reached :)