Puzzle Solver for Flow Game

[xombyphish]

Hello, all.
I'm new to this site and forum, as well as, to a degree, C++, itself.

I've distinguished myself among my other class mates, and as a result the professor has me working on projects for him, personally, that he just doesn't have enough time for.

Currently I am working on a program that solves a puzzle game called Flow that is available for Iphone and Android (both for free). The goal of the program is to solve the puzzle, which is generally in the format as follows:

x y b g x
x x x r x
x x r x x
y x x o x
b x o g x

(x = Blank; y = Yellow; b = Blue; g = Green; r = Red; o = Orange)

That program would need to find a path from color to color, only traveling on blank spaces. Once the color is found, all the x's would be change to the character denoting that color, and those spaces would no longer be available for the other color paths.

This issue is; I can't seem to figure out an algorithm to accomplish this. I tried using Dijkstra's algorithm, as well as the A* algorithm, but to no avail.

If anyone has any tips that might be of some help, please respond and let me know. I'm more than willing to post code snippets of the program if anyone needs it, or provide more details.

[cire]

First thoughts:

Pick a color. Generate all possible paths to get from one end to the other. Iterate through the paths to see if there are any positions that are common to all paths for this color. If there are, those positions must be reserved for this color.

On to the next color. Generate all possible paths to get from one end to the other, excluding any path which contains positions reserved for the previous color. Iterate through the paths to see if there are any positions that are common to all paths for this color. If there are, those positions must be reserved for this color. Remove paths generated for previous color if they pass through those positions reserved for this color.

Rinse and repeat for the rest of the colors.

Iterate through combinations of the remaining paths for each color until you find a solution (a combination where no positions are shared between paths of different colors.)

[K0T4K0t4]

It could be solved kind of how most game ai is done using game boards. Basically you would calculate all of the possible ways that say the blue node could connect to the other blue node. then you calculate all of the ways yellow could connect to yellow so on and so forth. once all the ways have been calculated for every color you compare the resulting paths for each color untill you find a set of paths that dont interfere with eachother and that set of paths is the solution to the level
its the brute force method to solving that type of problem. Once you have that done and working you should be able to optimize it using some clever thinking. For example if you know all paths of color c pass through squares x y and z then color d cant use any of those squares since they must be used by color c.
You could also look at the algorithms used in Sudoku solvers. Even though its a very different game many of the algorithms used to solve it can be manipulated to work on other puzzle type problems.
If you post your code id be happy to help more.