I've only played the first few hundred levels of the free version but as far as I can tell the optimal number of moves is always the absolute minimum. I've never played a level that required more moves than there were "flows"
oh well.. i downloaded it too and played a couple of levels, and indeed, it's always the same numbers as there are different colors, so making a generator wouldn't be that hard i guess, but then you'll need to make a solver too, to see if it's possible to solve the generated one..i don't think this will be easy
Right, the minimum number of moves is always the same as the number of colors because the lines never cross.
As for generated maps, there's actually a slightly different way to do it than proving a particular random map is valid. My thought isn't fully developed because topology is somewhat of a weak area for me, but here it is:
Imagine you're specified to have K colors in a plane for your puzzle. Within this space, there exist k lines stacked on top of each other in any particular order in a way similar to this:
At the endpoints of each of those lines is, well, an endpoint. These will become the points between which the flow is drawn. Now, we can use these lines to generate any possible puzzle by a certain series of stretching, bending, and compressing operations from at least one possible color order. The only real rule is that the lines cannot cross (i.e.: the boundary conditions can't change). This generates what can be called a homotopic configuration: A set that can be continuously deformed by those operations back into the original lines. All possible valid configurations MUST meet this criterion, so we know the set of homotopic configurations contains all of the solutions we're looking for. But wait, there are two other criteria valid solutions must meet: That the configuration fit into an NxN grid and that the flows completely fill the grid. The former criterion is really the problematic one because it's discrete. In a continuous space, we could just wrap the flows around very tightly and "fill" the loose parts, thus making the second criterion trivial except given the first. To be honest, I'm not entirely sure how to guarantee that the generated solution will fit in the discrete grid nor that it can be "expanded" to fill the grid, although the latter shouldn't be too difficult.
Other related questions:
Is the set of homeomorphic flows identical to the homotopic set?
Can all homotopic flows be "expanded" to fill a grid?
Is there a way to generate the set of all valid flows without specifying color ordering?
Clearly I've put a bit too much thought into this since I downloaded the game
