Let's start with some definitions. We call the arrangements from the problem statement Latin rectangles. A Latin rectangle with the same number of rows and columns is called a Latin square.
The task was to add as many rows as possible to a Latin rectangle. We will prove that in fact each Latin rectangle can be extended to a Latin square. (This result is one of the "true classics" in combinatorics.)
Here is the argument: Clearly you can't add more than N-M rows. If M=N, the Latin rectangle is already a Latin square. Now assume that M<N. We will show how to add one row to the rectangle; repeating this process N-M times leads to the resulting Latin square.
For the arrangement let's construct following bipartite graph G with N+N vertices (N vertices in each partition): Vertices of the left partition will correspond to the columns of the grid. Vertices of the right partition will correspond to various kinds of flowers. The column X and a kind of flowers Y will be connected by an edge iff the column X doesn't contain the kind Y yet. Clearly each perfect bipartite matching of this graph induces a row of flowers that can be added to the arrangement and vice versa.
It remains to show that we can always find a prefect matching in the graph G. This follows immediately from Hall's theorem (sometimes called "Marriage theorem"). You may find the proof in almost any introductory book on combinatorics and/or graph theory.
Theorem (Hall). Let G be a bipartite graph with partitions A, B. For a set of vertices U we will denote the set of all their neighbors by N(U). (E.g. N(U) contains all vertices connected by an edge to some vertex in U.) A perfect matching in the graph G exists iff for all subsets S of the partition A (in our case the columns of the rectangle) |N(S)|>=|S|. (Here N(S) is the set of colors that may be used at least in one of the selected columns.)
Back to adding a row of flowers. Take an arbitrary set S of columns, let |S|=r (1<=r<=n). Each corresponding vertex in our graph has a degree (N-M)>0. Also there are exactly Q=(N-M)*r edges leaving the subset S. Similarly each vertex representing a kind of flowers has a degree (N-M). Therefore there are at least Q/(N-M) vertices (i.e. kinds of flowers) connected to S. It follows that |N(S)| >= Q/(N-M) = r = |S| and Hall's theorem guarantees us the existence of a perfect matching.
There are several known algorithms to find a maximum (not necessarily perfect) matching in a bipartite graph. We will briefly state the most simple of them (as it is already fast enough to solve the hard input). We will call an edge matched if it is a part of the current matching and free otherwise. A vertex can also be matched (incident with some edge in the matching) or free. An augmenting path is a path with alternating matched and free edges, starting and ending in free vertices. It can be easily shown that a matching is maximum iff no augmenting path exists.
The algorithm will work in rounds. In each round we run a breadth-first search to find an augmenting path. If no such path exists, we are done and found a perfect matching. Otherwise we have found a new matching having more edges. This matching can be obtained from the old one by "inverting" all edges on the augmenting path (e.g. matched edges become free and vice versa).
Each time we find a perfect matching, we output the corresponding row of flowers, remove the matched edges from the graph and start from the beginning. The total running time (using the algorithm described above to find a matching) is O(N4).
The easy input data set could be solved quickly using a simple backtracking algorithm — an easy way how to get one point.