Let's try to follow the thoughts I might have had, had I tried to solve this problem myself.
    What would strike me first, is the elegance of the position. It is far from gamelike but still, other than in most problems, it has patterns that are meaningful to the ordinary chessplayer.
    Well, mate in 4. Let's threaten something. 1.Re1 threatens 2.Re4 mate. Now 1...Qxa8 2.Rxf4+ would be mate next move, but with 1...Qxd8+ Black forces stalemate. Then maybe something like 1.Rg1, to threaten 2.Qe1 or Qf1? In that case again, after 1...Qxa8 2.Rxf4+ Qe4 3.R1g4 White mates in time, but once more, 1...Qxd8+ is enough to stave off the mate long enough.
    Another obvious approach is to see what happens if we give a check. At first sight, that might seem to work: 1.Na4+ Kd3 2.Qc3+ Ke2 3.Qf3+ Kxd2 4.Qd1 mate, or 1.Nd1+ Kd3 2.Qc3+ Ke2 3.Bf3+ Kf1 3.Rh1 mate. But after both checks, Black can also capture on c4, winning a new flight square on b5, and then mate takes one move too many: 1...Kxc4 2.Qc3+ Kb5 3.Qxb3+ Kxa6 4.Bb7+ and mate next move.
    Apart from that, both after 1.Na4+ and Nd1+, Black also has 1...b2. If then 2.Rxb2 Qxd8+ is clearly enough to stave off the mate long enough. 2.Qxb2+ is a better try, but after Qxb2 3.Nxb2 axb1=Q 4.Rxf4+ Qe4 5.Rxe4 it has again taken one move too many to deliver mate.

Of course, if any of these crude attempts had worked, Yarosh' problem wouldn't be the diagram of the century. But as always with problems, finding the right refutations will lead to finding the solution, and this last attempt teaches us something important. Why, in that variation 1.Na4(d1)+ b2 2.Qxb2+ Qxb2 3.Nxb2 axb1=Q 4.Rxf4+ Qe4 5.Rxe4 mate, was it mate at all, if too late? Because the black Queen no longer defended the Bf4. Indeed, without that Queen, it would be mate in 1 by 1.Rxf4. Then what if we tried to disturb the queen in controlling that square?
    There is one obvious move to do that: 1.a7
    Having a hunch that the thematic defence will be axb1=Q, we'll try to cross off Black's other possibilities first. He has two Queen moves that defend the mate without defending the Bf4, but after both White is in time: 1...Qxa8 2.Rxf4+ Qe4 3.a8=Q Qxf4 4.Qd5 mate. Or: 1...Qxd8+ 2.Kg7 and now 2...Qg8+ 3.Kxg8 and 4.d8=Q mate or 2...Qxa8 3.Rxf4+ Qe4 4.d8=Q mate or 2...Qc7 3.d8=Q+ Qxd8 4.Rxf4 mate.
    So we turn to Queen moves that do defend Bf4. There are three, and against all three White is in time: 1...Qc7 2.Bxc7 axb1=Q 3.d8=Q mate, or 1...Qd6 2.Re1 Qe5 3.Nxe5 fxe5 4.Re4 mate or 1...Qe5 2.Bxe7 Qd6 3.Nxd6 Ke5 (otherwise Bxf6 mate) 4.Nd3 mate. This last variation, necessary for the soundness of the problem, demonstrates that luck is with geniuses.
    Queen moves not working, Black turns to his most obvious defence: 1...axb1=Q White must then pursue his attack on the Bf4 by 2.axb8=Q Against the threat 3.R(Q)xf4 and mate, Black has two defences: 2...Qe4 and 2...Qxb2. After 2...Qe4, 3.R(Q)xf4 Qxf4 4.Q(R)xf4 is mate. 2...Qxb2 robs White of the control of two flight squares for the black king; c4 and d3. After 3.Qxf4+ Kd3 there is now no mate next move, but with 3.Qxb3 White regains control over c4 and d3, and as the Qb2 is pinned, it is mate next move by 4.Rxf4.

If this were all, it would still only be a mediocre and rather pointless problem, that wouldn't even have been accepted by a serious problems magazine or column.
    But it is not all.
    There is almost a moral lesson here: we get access to beauty through the simple virtue of scrutiny. Have we really checked all of Black's defences? After 1.a7, we checked all the Queen's moves, and the promotion: axb1=Q What else could there be to check? Well, the promotion is the wrong wording: Black has four different promotions. But what good could a promotion to rook do him? Let's just have a look: 1.a7 axb1=R 2.axb8=Q Now, there is no 2...Qe4, but Black still has his other defence: 1...Rxb2, making d3 and c4 available to his King. And if White now continues as before, with 3.Qxb3, it is stalemate. Aha.
    Then what? We have to go back one move, to the position after 1.a7 axb1=R. White obviously must capture the black Queen. But if 2.axb8=Q does not work, what does work? It is at this point that the grandiosity of the whole thing might begin to dawn upon us. Suppose 2.axb8=R That still threatens Rxf4 mate, and after 2...Re1 White is in time with 3.Rxf4+ But after 2...Rxb2? Well, now, 3.Rxb3 is not stalemate, and after the only move, 3...Kxc4, 4.Qa4 is mate.
    By now we can hardly believe or own thoughts. Could it really be that if Black defends by 1...axb1=B, White has to promote to a bishop too? Indeed, if now 2.axb8=Q, then Be4 3.Rxf4 or Qxf4 is stalemate. But after 2.axb8=B Be4, 3.Bxf4 is not stalemate. The black bishop can move, and must move, and after it does, 4.Be3 or Be5 is mate.
    Finally: would 1...axb1=N make sense? It does, because after 2.axb8=Q Nxd2, Black again has access to a vital flight square, now c3, staving off mate long enough; after 3.Rxf4+ Ne4 there is no mate next move.
    As stalemate is not an issue now, 2.axb8=R or axb8=B are pointless. The solution must be 2.axb8=N. But is it? Against the old threat of 3.Rxf4+, Black again defends with 2...Nxd2. And now, 3.Qc1 is still mate next move: after any knight move, 4.Rxf4 mate follows, except for 3...Ne4. That blocks e4, and now 4.Nc6 is mate. It was precisely for this move that White needed a knight.

So:
If Black promotes to Queen, White must promote to Queen.
If Black promotes to Rook, White must promote to Rook.
If Black promotes to Bishop, White must promote to Bishop.
If Black promotes to Knight, White must promote to Knight.

This Holy Grail of chess had been searched for in vain for over a century. The greatest composers thought it would never be created.
    Leonid Yarosh, when he composed this problem in 1983, was a 26-year old soccer trainer from Kazan, and a complete unknown in the composing world.

Here are the main variations of the solution recapitulated:

1.a7!
1...axb1=Q 2.axb8=Q Qxb2(!) 3.Qxb3 Qc3 4.Qxc3 mate
                                     Qe4(!) 3.Qxf4 Qxf4 4.Rxf4 mate
1...axb1=R(!) 2.axb8=R! Rxb2(!)3.Rxb3 Kxc4 4.Qa4 mate
                       2.axb8=Q? Rxb2! 3.Qxb3 stalemate
1...axb1=B(!) 2.axb8=B! Be4(!) 3.Bxf4 B- 4.Be3(5) mate
                       2.axb8=Q? Be4! 3.Qxf4 stalemate
1...axb1=N(!) 2.axb8=N! Nxd2(!) 3.Qc1! Ne4 4.Nc6 mate
                       2.axb8=Q? Nxd2! 3.Qxf4+ Kc3 4.??
                                                     3.Rxf4+ Ne4 4.??
                                                     3.Qc1 Ne4 4.??

(c) Tim Krabbé, 1998