In that case I know the solution, because you showed it to us. But just knowing the solution will not make me comfortable giving the problem as a challenge to my friends at the chess club. One thing I'm pretty sure of is that there is more to the explanation than Frankwho's comment.
Yes, but my interface timed-out after I had written a long reply. Will redo that later.
Very interesting problem and it certainly gives food for thought.
The conventional way to approach the position ("PRA"-style) is as such. Look at the position as a regular #7 (directmate in 7), and realise if black can't castle it's cooked, if black can castle it's unsolvable. Thus we find ourselves looking for a retro justification "PRA-style" to explain how black loses castling rights. Without other castling or en passant moves to potentially clash with, we reexamine the FIDE rulebook and find DR, 50M and 3R clauses to work with; the last one is what works here.
From the diagram position, we find the moves 1. Bg8 Ne6 (1 repetition) 2. Bh7+ Nf8 3. Bg8 Ne6 (2 repetitions). We now ask ourselves: after 3...Ne6, does black have castling rights?
Consider the unit position after 3...Ne6. Proof by contradiction: assume black can castle. Then black still had castling rights in the diagram (only the wB and bN moved in our sequence). What were the moves before the diagram? The only possibility is retracting -1...Ne6 -2. Bg8. (If you don't read retro notation, that means the 2 single moves just prior to the diagram were white discovering a check Bg8-h7+ no capture, and black interposing ...Ne6-f8 no capture. I'm not explaining this here, it's simple enough to deduce by counting pawn captures and missing units.) Thus that position with the knight on e6, bishop on g8 and black having castling rights occurred once before the diagram and twice in our sequence - threefold repetition, thus 3...Ne6 draws and we have no solution.
A way out of this, in the vein of current conventions, is to assert that: In order to have a solution, the act of repeating the position two times in the solution precludes a game history with the third repetition. (Parallel with RS: If there is no solution under simple PRA and mutually exclusive move rights, the act of castling (for example) by white precludes a game history with black castling rights.)
Therefore after 3...Ne6 which by our assertion doesn't automatically draw, we conclude that black can't castle. Which means black couldn't castle in the diagram position, and the move prior to the diagram was by the bK or bR - all is good, we don't have threefold repetition. And since after 3...Ne6 black can't castle, white mates in four more moves with 4. Qf1.
Now, I would like to respond with what I think of the above reasoning (I can't quite agree with how the logic goes if we try to shoehorn our conventions to fit this intention), but this post is getting plenty long enough and I'll just make another post after this one.
I'm quite curious as to what you think of this situation with conventions, Arisktotle, and how you propose resolving the conflicts. I'll also give my two cents here (by no means worth even two cents, just the opinion of someone quite outside the active retro-community.)
The current set of Codex clauses is not "complete", in the sense of handling unambiguously every possible interaction of special move rights and rules, particularly in the generalised cases. There does seem to be an underlying idea, though. Very roughly speaking, for a given position, all game histories are permitted unless proven otherwise; if there are multiple histories, we consider them all (notable exception: e.p.) and eliminate as we go along the forward play, if any. "Proven otherwise" mean by pure deductive logic, or by playing a move that eliminates certain histories. In addition, we do not consider a position drawn until all histories leading to the position meet the 50M or 3R criteria (analogous to DR: all futures of the position are drawn.) (Random idea: combining 50M/3R and DR?!)
If we define the history to be a discrete sequence of positions (each including full FEN information: special move rights, repetition number, moves since capture/pawn move), then the #7 above fits right in. The solution sequence eliminates the histories that keep black castling rights, since after 3...Ne6 the position is not "dead" - there exist histories in which it's only twofold repetition, just that in all of those black can't castle.
Unfortunately this interpretation is not easily generalisable nor even quite sound as-is - byproducts of the choices to make castling and e.p. unconditionally allowed and forbidden respectively, already pruning certain histories arbitrarily. But those choices were aiming at enriching the potential for composers. So in the end we still find ourselves asking: how do we formalise the conventions?
P.S. I appreciate this exchange of ideas - I've never reflected quite this much on the foundations of chess logic before. Any recommended readings, articles or archives?
P.P.S. Also sorry for walls of text and thanks to Athanael for the original post sparking this whole thread: not sure if you expected this type of response, but there are those of us out there who appreciate this genre of problems very much.
I also want to thank the OP, whose position turned out to be straightforward enough (no, not a pun) for me to finally understand it and be ready to confuse people with it when I go to the chess club tonight.
There's one thing I'm still wondering about. In the rule quoted by Remellion, it said "whichever castling is executed first is deemed to be permissible" but didn't say explicitly that the second castling is ruled out. If the first castling gives a position for which there is a proof game that does the castling manually, is the second castling still prohibited? The question occurred to me when I read in Arisktotle's #63 that "2.0-0 prevents it by eliminating proof games where black had castling rights".
That bolded phrase occurs in the context of "mutual dependency of castling rights", so the second castling is ruled out in the #4 problem because the castlings are provably mutually exclusive. Even if the unit configuration after 2. 0-0 is reachable from a proof game without white having castled, the fact is the position ( = unit configuration + extra information like side to move, castling/ep rights, previous moves etc) includes the fact that white just castled - hence histories allowing ...0-0 are eliminated.
@Remellion: Yes, those are a lot of issues and I can't handle them in a few lines or even a few pages. I am writing a book on the subject which will contain the full Monty of my ideas. The only way to view them is in a bundle as a new paradigm. They are not step-by-step improvements of the current conventions but they constitute a different way of looking, feeling and thinking about retro-problems.
Example: you refer to castling 'rights'. Most of the time the qualification 'right' is misplaced. In a diagram exist no castling 'rights' only castling 'licenses' (in the Codex referred to as permissions but this is less accurate). 'Rights' belong to proof games, 'licenses' to diagrams. In the case of PRA, every license is turned into a 'right' or it is 'revoked' in each of the partial problems before the solution starts. In RS, the development of a solution may determine that a license becomes a right or not, and it may be different in each variation. Quite often a right only crystallizes in retrospect. After castling is executed, the license becomes a right in retrospect. This is extremely significant, since it is the core of AP-justifications. Therefore, in #73, the only thing you may assume from the diagram is that black initially possesses a licence to castle which may be revoked by the course of events! And that is precisely what happens. The correct terminology for the process is: black lost the license to castle during the solution by losing the proof games in which he had the right to castle.
Example: Is it RS or PRA? I can answer that question in my paradigm but not in the Codex paradigm since it is incomplete. You may think that RS and PRA refer to generic logics but in the Codex they are only defined by listed cases. In the PRA list the obvious candidates 50M and 3P (3R in your dictionary) are missing while RS is stripped naked to "mutually exclusive castling". This is a result of the way the current Codex articles have been compiled. Instead of analytically reviewing the retro-logics in combination with retro-active properties (e.p., castling, 50M and 3P), they harvested the existing set of RS/PRA problems and drew up conventions to handle all those. This is not the way to look into the future. If you support just the forms already there, you will never get a new form. By the way, #73 was already published at that time and they missed it completely - or didn't get it. My paradigm is completely designed from generic concepts and does not stop at orthodox chess. It can easily handle forms like reflexchess, Circe, Warp-chess and retractors for which I have produced (and published) example problems. All completely intuitive once you inhabit the generic logics. Oh, I should still answer the initial question of this paragraph for my paradigm. RS-logic should always be the default logic as it is the least problematic and is the natural extension of the basic conventions (article 16.1, 16.2, 17, 18). PRA can be defined for the repetition and 50M attributes but it takes quite some explaining especially since the articles 17 and 18 are both fuzzy and incomplete. So #73, like #1, is of the generic RS-type.
Example: What about this strange AP-type? AP-problems are considered amongst the weirdest constructions in retro-land but they are quite the opposite. During my research I discovered that AP-logic is the root-type for RS-logic and for the basic conventions (article 16.1 and 16.2). They form a group, while PRA and other forms of Retro-Variants are the other group. There are as many ways to combine retro-active attributes for the AP-type as there are for the RS and PRA type and it is unbelievable that the Codex says it is just between the e.p. move and the castling move. In the field of law there are two concepts that describe the difference between the Codex paradigm and my paradigm quite well. The latter corresponds to 'common law' (generic), the former to 'case law' (only cases). In the coming years the retro-logics will inevitably expand into the fairy territories and the bookkeepers of the Codex Committee will be guaranteed a job for life by handling all the new cases on their desks. You can find me on the sundeck of a caribbean cruiseship meanwhile. If somebody pays me for this ...
Remellion, you ask me for recommended readings and I have no good answer for you. I am a bad archivist and lose most of my references and sometimes even good compositions. This is no big problem for me since I am currently concentrating on my conceptual innovations; the critical sample problems have already been published (without the theory). Two years ago I published some chapters of my book for trial on Janko's retro-forum and I will resume that in the coming months. There is an interesting article by R. Turnbull on 'Abominable problems' which describes his struggle with the application of some kind of retro-logic to several fairy types. I have taken his creations as a test bench to verify the power of the new paradigm. Piece of cake.
FOUND MATE IN 4
MIND BLOWING SOLLUTION
PRETTY EASY ONCE YOU REALLY LOOK AT THE CORRECT PEICE
@Arisktotle: Thanks for the reply. I will be looking into the retro mail archives then. It's material that I've seen before about two years back but skipped as being too wordy (apologies) but now I'm in a better position to understand what's actually happening.
I'm also sure you've heard this before, but the analogy of possible histories with quantum mechanics is very alluring, in particular with mixed states. I can thus accept the basics of what you're putting forth (at least until I read further and find out where the analogy breaks down.)
I hope the analogy with quantum physics breaks down somewhere or I will be arrested for unauthorized experiments with subnuclear forces one of these days. 
By the way, quantum entanglement is not essential for the understanding of the paradigm - it merely demonstrates a mathematical equivalence. Metaphors are useful for the replacement of fixed mental patterns. There are several different ways to convey the same message amongst which a few common human logics.
And note that the material presented sofar - on Janko's site and in this thread - is only introductory. The core processes and justifications are still awaiting publication.
In the next days I will present a step-by-step breakdown of the solution and justification of #73 as promised to n95311. It will contain a detailed comment on the state of article 18 (and by implication article 17) in the Codex.
I'll solve it.
1. Qc4! preventing castling this move. 1...bxc4 2. 0-0! and black permanently cannot castle. 3. b7 and 4. b8=Q/R# unstoppable. Sidelines 1...anything else 2. b7 and 3. b8=Q/R# mates.
It's obvious why 1. Qc4 prevents castling, but why 2. 0-0? Simple.
White is missing P, 2B, R, black missing 7 units. Assume white can castle. The Bc1 died at home, the wRa1 couldn't have escaped, therefore black's 2 pawn captures axb and bxc captured wBf1 and another unit. This means that white must have promoted a pawn. White needs 5 captures for the pawn structure on the board, and which leaves 2 captures for the promotion; whatever we try, the pawn promoted either on h8 (bR has moved) or f8 (passing by f7, bK has moved) and black can't castle.
PRA convention: Castling is legal unless proven otherwise. White's 2. 0-0 is legal by "benefit of doubt" so to speak, whereupon black's ...0-0 is provably illegal, and white mates by promotion.
Honestly not a hard problem by retro standards, but I don't particularly like bashing my head against some of the more nightmarish ones, so this was quite enjoyable.
EDIT: I see caveatcanis already solved it in #10 and #13. As expected. :-)
Your solution is incorrect.
I don't dispute the fact that when one side can castle, other can't, and vice versa. It is a nice detail for retroanalysis, but nothing more.
The right to castle is a hard fact, unknown to observers, but already established beforehand, definitely not affected by the initial moves in the puzzle (except for king or rook moves).
From retroanalysis, we have 3 possibilities:
a) neither side can castle
b) white can, black can't
c) white can't, black can
In the case of a) and b) it is simple: 1. b7 and 2. b8=Q/R#.
1. Qc4+ and 2. 0-0 are redundant moves.
However in the case of c), there is no way to deliver checkmate in 4 or sooner. Your line 1. Qc4+? bc! (and 2. 0-0 taken back after black's rightful protest, replaced with penalty king's move) is not acceptable, and black castles himself in his move.
If black can castle, we can't change it by trying an illegal move!
Polar_Bear is big on following rules, but I don't think he likes the one from Article 16.3 of the Codex of Chess Compositions, as quoted earlier by Remellion:
"Partial Retrograde Analysis (PRA) convention. Where the rights to castle and/or to capture en-passant are mutually dependent, the solution consists of several mutually exclusive parts. All possible combinations of move rights, taking into account the castling convention and the en-passant convention, form these mutually dependent parts. If in the case of mutual dependency of castling rights a solution is not possible according to the PRA convention, then the Retro-Strategy (RS) convention should be applied: whichever castling is executed first is deemed to be permissible."
I suspect he also doesn't like Article 17, 50 Moves-Rule:
"Unless expressly stipulated, the 50 moves-rule does not apply to the solution of chess compositions except for retro-problems."
Chess puzzles are not a religion and you need not wait for a message from heaven. The very simple solution is clearly explained by Remellion.
The perceived mystery around this puzzle type has nothing to do with its difficulty but with the lack of knowledge and understanding of the retrograde logic supporting it. It cannot be solved with just standard deterministic chess rules but needs additional 'conventions' handling the 'missing information'. One of them is the 'castling right', the other one is about arbitrating between 'clashing castling rights'. With these conventions in place, the puzzle solution is correct.
Conventions must be accepted by all parties involved, othervise they are just ignored. I don't remember I had agreed to PRA before I started to solve this puzzle since the OP failed to notice.
I would like to see people posting puzzles properly: with complete stipulations, conditions, applied conventions and rules exceptions.
@Polar_Bear: I am sure there are many conventions in the world that you have not agreed to but are nevertheless in place. What matters is that they have been authorized by the proper bodies - in this case FIDE and the WFCC (federation of problemists) - and that the conventions are knowable, i.e. their content is publicly available - as here in the "Codex for Chess Compositions" http://www.saunalahti.fi/~stniekat/pccc/codex.htm
The conventions are set in motion by the context of the issue at hand. As soon as you are aware that you are not dealing with '10 flavors of icecream' but with 'a chess composition' then you will presumably be able to access the rules, conventions and other regulations pertaining to the 'chess composition' context.
Conventions are indeed weaker than rules and how they are is also explained in the Codex. It boils down to this meta-convention: "all the conventions are considered to be in place in chess compositions unless stipulated otherwise with the diagram". It reduces the stipulation-burden on author and publisher when they need not specify RS or PRA with every diagram.
By the way, the convention we are talking about for problem #1, article 16.3, is a very peculiar one and I can sympathize with anyone who disagrees with it. It tells you to choose between 2 subconventions depending on which one produces a (proper) solution. For problem #1 it is the RS-subconvention that wins. It is not PRA. For article 16.3 see: http://www.janko.at/Retros/Glossary/Codex2009.htm
First move has got to be Rxh6 to prevent castling :) then place knight on f6 and push pawn :)
White is missing R+B+B+P while Black has made two pawn captures.
If we assume that White can castle, then White's R and black-squared B never got out, so Blacks pawn(s) captured the white-square B and P.
The captures must have occured on b6/b5 and c6 (not d6 and c5, because it's a white-squared B). For this to happen, the White pawn must first have been promoted.
We can already see 5 pawn captures by White, and Black is missing only 7 men (6 pieces and 1 P), so there are only two spare captures available to promote the White pawn. This means that the promotion must have occurred either on f8 (from f7) or on h8.
Either of these possibilities means that Black can't castle.
That was impressive analysis :)
Why doesn't Black keep repeating till draw? I don't get it :-(
Black would love to keep on repeating but white changes course with his 4th move. See the excellent comment by Frankwho.