Assuming there were only Blue and Red (B&R) colors and 3 persons 1,2,3 ... it could work. As far as I understand the puzzle.

Ignore the all colors are used for one sec and / or assume that only one of 1&2 is allowed to move.

And also assume that all of them face the door to see the newcomers (otherwise knowledge is potentially lost)

1 enters the hall, takes a position.

2 enters the hall, looks at 1's color and takes a position behind 1. 1 also sees 2's color. Each still does not know own color.

3 enters the hall, looks at 1 and 2, he sees their color and they see his.

1 and 2 are either the same color (RR, BB) or different (BR).

* If same, 3 takes a position besides them forming another row.

* If different he stands behind them.

Now, since 1 and 2 know each other's colors, 3 basically transmits one bit (1/0) of info to both of them. Depending on his positioning, this tells them if their color is opposite or same.

If he gets beside them:

* (assume the all-colors-are-used rule) no one moves game over-win (forming either BR or RB rows depending where the door is).

* (not assuming the all-colors-are-used rule) if their color matches 3 they both move behind him, else both stay where they are (no force moves assumed) - game-over win

If he gets behind them, exactly one of them (1&2) needs to move away from 3 to form a new row and exactly one of them will know he has to move since they know their color and 3's - game-over win

**G(2,3,2)** and

**GAC(2,3,2)** are thus winnable where

**G[AC] (x,y,z) **instance of the (deadly) game where

**x **prisoners are painted

**y** colors, at most

**z** people can change their initial place, and

**AC** = All Colors used).

Also

**GAC(2,3,1)** is winnable since if all colors are used, in the case where 1&2 have the same color, the rows are formed without any of them needing to move.

The OP asks for GAC(N,4,2) where N>=14.

Above strategy seems to be sub-optimal as the placement of the first 2 is static therefore not transmitting any bit of info. Granted, there may be a way to improve this a bigger version of the game.

Setting aside the requirement of getting into a final position for a second, an easier problem would be if at the end of all this moving, each would know everyone else's color. The arrangement guarantees that this knowledge is gained if rows are correct in the end if both color-given order and reverse color-given order rows allow this and x>=2. Each prisoner would be able to see his own relative position and deduce his own color based on the row he is in and the other rows.

Also knowing everyone's color is equivalent to be able to color ID self (color IDing is shorter than color guessing

even if the arrangement is wrong - since they see those before upon entering and all who enter after.

So, instance

**G[AC](x,y,z) **winnable implies instance

**C[AC](x,y,z)** winnable (not sure if movement plays a definite role but it may transmit information regarding colors so we can't discard it). And I kinda think even C[AC](N,4,2) for N>5 is not winnable no matter what strategy they adopt (unless there's a trick /outside of the box thinking that I missed when trying to formalize the game instance / problem).

Notice that each move after the 2nd prisoner chooses his initial position transmits a bit of info to each player increasing the knowledge gain.

For the color ID problem (for just 2 colors) - just knowing each other's color - the knowledge can be thought of as a binary NxN matrix where 1 stands for "I know your role" and 0 stands for "no knowledge". And it's not symmetrical.

* Matrix starts empty.

* The n-th person entering adds +(n-1) bits of info for those before him (impossible to know before he entered since all before him we're blindfolded/did not see him)

* upon seeing the others adds +(n-1) bits of info to his own knowledge (impossible to know before he entered as he was blindfolded as well).

* Each positioning / movement of this n-th person may directly transmit one or more bits of info to the others YET no bit of info for this n-th person since no one is allowed to signal him anything.

* Indirectly, he may get some info (e.g. in the AC game) if either the placement of the n-1 persons before or the colors of those before him allow him to restrict his color-choice to a single one.

So, to fill the matrix from 0 to N*N in N+2 moves, the strategy needs to increase the knowledge gain at some point. Sum(i-1+i-1) only guarantees filling one half (minus the diagonal) of the matrix for the first n players entering (dumb/no strategy).

I don't see extra moves adding that much.

To double the knowledge gain, one needs a speed-up factor x2 for the placement strategy + extra moves.

Granted, near the end of the game, as placement choices (or color-choices in case of AC game) become restricted, a given strategy may speed up the knowledge gain (again, not specifically caring about ending placement here, so we're even allowing for a different end-arrangement plan), but not by much IMHO. (I might get fooled by the numbers here).

Adding more colors makes for an even weirder matrix. Assume 4-colors. Each player needs three bits of information (not color X, not color Y, not color Z) before he can finally color ID self. Since 4=2^2, granted two bits of info might narrow it down and speed it up (binary-search pattern). But again, extra dimensions (extra colors) make the knowledge deficit several times bigger.

And lastly it's hard to come up with a constant/better performing strategy when X is increased. Each new added player adds 1 unknown (as he chooses his spot) while the number of extra moves is limited - so each of these moves need to cover up for this unknown as well.

Sorry, long post.

I have no idea how this might be solvable (then again I did said so in the spoiler title ).

I'm also not an optimist, and when I actually manage to prove something I usually find myself proving something is not possible, but that's