Neil Bickford has exhaustively searched the space of 5 × 4 sliding-block puzzles* to determine the one with the longest minimal solution. The unique result, which requires a whopping 235 moves, happens to be Bob Henderson’s Gauntlet puzzle:
*subject to the constraint that the objective is to move the red monomino to the upper-left corner.
Despite having far fewer positions than a Rubik’s cube, the graph of this sliding-block puzzle has a much longer diameter. Tomas Rokicki proved that the Rubik’s cube has a diameter of 20 in the half-turn metric, and there’s an upper bound of 28 for its diameter in the more natural quarter-turn metric. It has also recently been proved that the Rubik’s cube Cayley graph (which is vertex- and edge-transitive) is also Hamiltonian; it is conjectured that every Cayley graph is Hamiltonian.
Now, chess problems are harder than sliding-block puzzles, since you have to account for all possible moves that your opponent could make. For instance, ‘mate in 3’ problems are quite difficult due to the plethora of possible combinations for which one must account. This is reflected in the fact that (generalised) chess is EXPTIME-complete, whereas sliding-block puzzles are merely PSPACE-complete.
If mate-in-3 problems can be difficult, then surely the following mate-in-549 problem must be completely intractable? Even the best grandmasters can see no logic behind the majority of the moves, since the depth of the problem is beyond human comprehension. Indeed, it would probably please even Doron Zeilberger, who considers Fermat’s Last Theorem to be trivial due to the existence of a human proof.
This configuration was discovered by programmers at Lomonosov University, Moscow, who exhaustively catalogued all reasonable seven-piece chess endgames. White can force a win, eventually, but Black can prolong defeat for as many as 549 moves. Interestingly, the optimal sequence of moves for White involves promoting the pawn to a knight, rather than to a queen.
If we’re allowed an infinite board, then it’s possible to have mate-in-ω games and beyond, where White eventually wins, but Black can delay White by an arbitrarily long time. It is also conceivable that there is an algorithm for converting a statement in Peano arithmetic to a chess configuration in which White can force a checkmate if and only if the statement is true. (Both of these rely on the fact that rooks, bishops and queens can move by any integer in a single move.)