Another problem-Find color of the pieces Please help me to find solution of this next problem by the legendary composer Andrej Kornilow. It appeared in Shakhmatnaya Kompozitsiya 41 issue in 2001 and it was dedicated to A. Lobusow on his 50th birthday.
The colours of the pieces on the diagram is unknown. The diagram can be obtained in a legal game. One needs to find colou of each piece: Black or White.
[FEN &quot;8/8/2NBQPN1/2QQKQQ1/2PPPPN1/2QPKPP1/2NPPPP1/8 w - - 0 1&quot;]

It is easy to find colors of the most pieces:

 1. The kings should not be checkmated by pawns (otherwise what was the previous move?), so the upper ones are White.
 2. The knight on g4 makes a check to either king, so it made the last move.
 3. All other pieces should not give a check to any king, so we must find the colors of them.
 4. There are 12 pawns and 6 queens, so 4 queens were created, and all other pieces are original.
 5. There are 2 White knights on the top, so knight on g4 is Black.
 

But then one needs to consider different possibilities of the pawn placements, taking into account possible movements. It is hard for me to find a solid approach to it.
I'm going to start from scratch even though the OP posted a partial answer in the question, so I will be covering some familiar ground.

I began to break the problem down by assigning black to the upper king, then making every piece which attacked him black. Since the g4 knight attacks a king, no other piece can be giving check to either king.

[title "White to move"]
[fen "8/8/2nbqPn1/2QqkqQ1/2PpPpn1/2QPKPP1/2NPPPP1/8 w - - 0 0"]


Immediately I see a problem. The d4 and f4 pawns both give check no matter which color they are, so I inverted the colors:

[title "Black to move"]
[fen "8/8/2NBQPN1/2qQKQq1/2ppppN1/2qpkpp1/2npppp1/8 w - - 0 0"]


This time I painted all chessmen white who would otherwise be checking the white king. Now there are two questions: is the g4 knight white or black, and which other pieces are white?

Let's analyze the promotion situation. There are 12 pawns and 6 queens. The game began with 16 pawns and 2 queens, so this establishes that a) 4 pawns became queens, b) no other pawns were captured or promoted, and c) the original queens are still present.

Let's look at captures. There are 25 pieces, and the game began with 32, so there were 7 captures total. What were the captures? Well, there are no rooks. Also Black has no bishops and White only has one. So in total, 2 black rooks and 2 black bishops were captured, and 2 white rooks and one white bishop was captured. This establishes that there was a maximum of 4 "lane-changes" for white pawns and 3 "lane-changes" for black.

Also, in tallying up the promotions, you have hopefully been able to deduce the color of the g4 knight. Since there are two other white knights targeting the white king, and no pawns were promoted to knights, the g4 knight must be black.

The other three pieces whose colors we can ascertain are the c2 knight and the d2 and f2 pawns, which must be black:

[title "White to move"]
[fen "8/8/2NBQPN1/3QKQ2/6n1/4k3/2np1p2/8 w - - 0 0"]


Now back to the pawn capture analysis. Let's see the pawn skeleton:

[title "Pawn skeleton"]
[fen "8/8/5P2/8/2pppp2/3p1pp1/3pppp1/8 w - - 0 0"]


We know the color of only three, though we also know that at least 6 are black (since at least 2 white pawns promoted to queen), and that they got into their current position using 3 captures or fewer. First, look at the a column. Either that black pawn promoted, or it captured twice, leaving one capture left for the other pawns. Since one capture isn't enough to explain the state of the other pawns, Black's a pawn must have promoted. In that case, either White's a pawn must have changed lanes at least once to let Black's pawn by, or Black's a pawn changed lanes. Now, look at b. Either that pawn promoted, or it captured once. If it captured once, then either a black c-pawn promoted or again captured once (since there is at most one c-pawn left). And again, in order for Black's b pawn to promote, either it or White's b pawn must have captured so they could get past each other. So at least two captures are necessary for columns a and b. We have five captures left.

Let's try to eliminate the possibility that Black has 7 pawns and White has 5. Black promoted the a-pawn, so we're working with b through h. Again, since this analysis mandates that b didn't promote, it captured. After this, there are two c pawns, and in the diagram, there's only one c pawn, so one of those pawns must have captured, too. Remember Black only gets three captures, so he has one left. There are no h pawns in the diagram, so the h pawn must have captured. Out of the diagram, then, if Black has 7 pawns, then he has the c pawn, two d pawns, one e pawn, one f pawn, and two g pawns.

[title "Pawn skeleton"]
[fen "8/3pppp1/2pp2p1/8/8/8/PPPPPPPP/8 w - - 0 0"]


Now, White. If White has 5 pawns, then he promoted 3. Since Black cannot have captured with his a pawn, White must have. Now White has two b pawns. In the diagram, there are no b pawns, and Black has the only c pawn, and the 3 d pawns are accounted for, and the two e pawns are accounted for. So either both white b pawns promoted, or else they would have to capture at least 4 times each to find a spot that would make sense of the puzzle position. Even one such b pawn journey would use up more than the rest of White's 4 captures, so this is impossible. White's a and b pawns must have promoted, using up one capture.

[title "Pawn skeleton"]
[fen "8/3pppp1/2pp2p1/8/8/8/2PPPPPP/8 w - - 0 0"]


I am already beginning to seriously doubt this situation. In order not to use captures, either White's h pawn promoted, or the c pawn promoted (after Black's c pawn captured and before the b pawn captured). Either way, White still needs to end up with one d pawn, one e pawn, and three f pawns. Let's try promoting the c pawn. It would use up the rest of the captures (3) to get the g and h pawns to f. Now the pattern can be fulfilled, but there are no captures left for White's f pawn to get around Black's f pawn, which must be on f2.

[title "Pawn skeleton formation"]
[fen "8/pppppppp/8/8/8/8/PPPPPPPP/8 w - - 0 0"]

1. axb3 a5 2. d3 c5 3. b4 c4 4. b5 c3 5. b6 cxd2 6. c4 d5 7. c5 d4 8. c6 a4 9. c7 a3 10. c8=Q a2 11. b4 a1=Q 12. b5 bxc6 13. b7 c5 14. b8=Q c4 15. b6 e5 16. Qa8 f5 17. b7 e4 18. b8=Q f4 19. g3 f3 20. gxf4 g5 21. h3 h5 22. h4 g4 23. hxg5 g3 24. gxf6 hxg4 25. Qd8 g2 26. Qdc8 g3


But promoting the h pawn means we must cross with the c pawn all the way to the f file, using the remaining 3 captures, and leaving none for the f pawn to get around Black's f pawn, or for the g pawn to move over to f. And promoting any other pawns means moving both the c and h pawns, as well as getting around black pawns with the promoting pawn, as well as moving the g pawn over, as well as letting black's f pawn through. In short, White can't make it with 5 pawns in a setup with Black's only viable 7-pawn structure.

Therefore, since Black can't have 8 pawns, and Black can't have 7 pawns, and Black can't have fewer than 6 pawns (since White has at most 6), each side must have 6 pawns.

Now that I've established the number of pawns of each color, I can better analyze the distribution in the final skeleton:

[title "Pawn skeleton"]
[fen "8/8/5p2/8/2pppp2/3p1pp1/3pppp1/8 w - - 0 0"]


There are no a pawns, no b pawns, one c pawn, three d pawns, two e pawns, four f pawns, two g pawns, and no h pawns. Let's simplify this by counting the minimum lane-changes necessary if pawns are all the same color. We can eliminate the a and b pawns, assuming they promote (because otherwise another pawn promotes, and the a or b pawn uses unnecessary captures to move to that other pawn's file). The h pawns must move to f, making four captures, and a c pawn moves to d, for a total of five. Now from experience we also know that the a and b promotions don't come without a price. At least two additional captures are necessary to get them past each other, making 7. You may argue that another pawn could promote, but that would only increase the number of captures, since then the a or b pawn that didn't promote would need to make additional captures to get into the 5x5 square.

So far so good. We're getting in by the skin of our teeth. We have this:

[title "Pawn skeleton"]
[fen "8/2pppppp/8/8/8/8/2PPPPPP/8 w - - 0 0"]


We've used two captures to get the a and b pawns past each other to promote. They could possibly have been both black or both white, so I will leave that ambiguous. Basically we have 5 remaining captures, up to 4 for White and up to 3 for Black. Firstly we know the h pawns have moved to f (or h to g and g to f, but that comes to the same thing), and that a c pawn moves to d. We know the d2 pawn is black, the f2 pawn is black, and the f6 pawn is white. Sounds like the black c pawn moves to d2, so the c4 pawn would be white. So Black's c pawn comes to c3, White's d moves to d3, Black's c captures d2, White's c moves to c4, Black's d moves to d4. That footwork involves only one capture (black).

[title "Pawn skeleton"]
[fen "QQ6/2pppppp/8/8/8/8/2PPPPPP/qqB5 w - - 0 0"]

1. Qc8 c5 2. d3 c4 3. Bd2 c3 4. Qcb8 cxd2 5. c4 d5 6. Qc8 d4


The e2 pawn is presumably white, since otherwise, White's e pawn makes a capture to get out of the way, and we don't have room in our budget for such extravagance. So the e4 pawn should be black. For f, we know that Black has wormed into f2, and White got to f6. This can be attained by Black moving f to f4, White moving f to f3, Black moving g to g3, Black capturing gxf2 (two), White moving h to h4 then capturing twice (over to g5 then to f6), and Black moving h to h4 then making the final capture to g3 (three). It is also possible for White to move g to g3 and then Black capture h3xg2. But maybe this ambiguity can be ironed out later. In any case, the puzzle position has been attained.

[title "Pawn skeleton formation"]
[fen "8/pppppppp/8/8/8/8/PPPPPPPP/8 w - - 0 0"]

1. a4 c5 2. b4 c4 3. bxc5 b5 4. d3 b4 5. axb5 a5 6. b6 a4 7. b7 a3 8. b8=Q a2 9. c6 a1=Q 10. c7 b3 11. c8=Q b2 12. Qa8 b1=Q 13. Qab8 c3 14. Qa8 cxd2 15. c4 d5 16. Qab8 e5 17. Qa8 e4 18. Qab8 d4 19. Qa8 f5 20. Qab8 g5 21. f3 f4 22. Qa8 g4 23. Qab8 g3 24. Qa8 gxf2 25. h4 h5 26. hxg5 h4 27. gxf6 h3 28. g3 hxg2


Playing around with these pawns inspired me to the final breakthrough. The remaining white bishop is the dark-squared one, which means that Black captured the light-squared bishop, and since the capture didn't occur on the bishop's home square, then the bishop must have gotten out somehow. The e pawn can't move, so the g pawn must have.

We now know all the colors.

[title "White to move"]
[fen "8/8/2NBQPN1/2qQKQq1/2Ppppn1/2qPkPP1/2npPpp1/8 w - - 0 0"]