[Retros] An algorithm to verify cages in retro problems

[Theodore Hwa]

Hi all,

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 
detect.

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 
through" [1].

The algorithm is described in detail at:

https://github.com/hwatheod/retractor-python/blob/main/doc/cages.pdf

and a prototype implementation in Python is in the same repository 
https://github.com/hwatheod/retractor-python

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!

[1] https://pairlist1.pair.net/pipermail/retros/2021-April/004918.html

Ted