[Retros] An algorithm to verify cages in retro problems
hwatheod at cs.stanford.edu
Sun Jan 1 14:26:28 EST 2023
Happy new year!
Summary: I have a prototype implementation in Python for the next
improvement to Retractor 2, which is an algorithm for verifying many, but
not all, cages. See https://github.com/hwatheod/retractor-python for the
code, and a detailed write-up in the doc/cages.pdf subdirectory.
More details: If we see a position with a White pawn on b2 and a White
bishop on a1, then we know the position is illegal regardless of what is
on the rest of the board. In general, a "cage" is defined as an illegal
position which can't be made legal no matter what else I add to the board.
It is a concept used all the time when solving retro problems to quickly
rule out illegal positions.
Retractor 2 has simple cages like the one above built-in, but there are
endless cages of increasing complexity that are difficult to detect
automatically on a board full of pieces. For many problems that Retractor
2 can't solve right now, it's because there is a cage that it couldn't
Here I propose a different approach, which is an algorithm that when
*given* a position believed to be a cage, it tries to verify that it is a
cage. If verification is successful, then it can be used by Retractor 2
for future solution of problems. In this way, we can have a form of
human+computer verfication without the concern expressed by Elkies that
"human reasoning sometimes contain[s] holes big enough for a cook to slip
The algorithm is described in detail at:
and a prototype implementation in Python is in the same repository
The eventual goal is to integrate this algorithm into Retractor 2. In any
position, the user would click on a subset of squares on the board and ask
the computer to verify that the configuration is a cage. If the
verification is successful, Retractor 2 will remember it and use it for
future solutions. Verified cages could be exported, shared with others,
and imported by others (but must be verified on import again, to prevent
any unverified cages from getting into any solution).
Any comments are appreciated!
More information about the Retros