I asked this on a computer chess forum (programmers hang out there, etc.) and got no substantive answers, which makes me think it's a research question. Whether it's sufficiently mathematical is iffier, so I hope it's ok for here (the site has a chess tag after all).
I'm looking for search strategies to find solutions to the Babson task using a computer. The Task is a chess-problem composition challenge proposed by Joseph Ney Babson in 1884, to create a mate-in-$n$ chess position such that:
- White moves;
- Black defends by promoting a pawn (possibly underpromotion);
- White wins by promoting her own pawn to the exact same piece that black promoted to. E.g. if Black promoted to a bishop, then White must also promote to a bishop in order to mate, since other promotions leave stalemate traps or other escapes.
The Task stayed unsolved for almost 100 years, before Leonid Yarosh published the first satisfactory solutions in the early 1980s. A dozen or so further solutions have been found since then, but it's still considered very difficult. I use the term "Babson Task" to refer to the challenge of composing such positions, as opposed to the individual positions (chess problems) that represent solutions to the Task.
The linked Wikipedia article discusses the Task's history and solutions and has some good further links. Before Yarosh's first solution, top composer Pierre Drumare worked on the problem for 20 years, publishing partial solutions along the way before finally giving up and saying the full task was probably impossible. Tim Krabbé (1986) published a book in Dutch called "De Man die de Babson Task wilde maken" (The man who wanted to make the Babson task), about Drumare's unsuccessful quest. Krabbé also has a good article about Yarosh's 1983 solution.
Anyway, I know how a conventional chessplaying engine works (search the move tree, with some obvious scoring heuristics plus a few branch-selection tricks like alpha-beta pruning) but have only the vaguest thoughts of how to search for a solution to this sort of constraint problem. I don't know even how a human goes about it (I play chess a little but don't know anything about problem composition other than this task).
Thanks for any advice.