Scarne’s Challenge
At the Hacker’s picnic the other day, Bill Ragsdale was trying to drum up interest in participating in writing computer players for Scarne’s Challenge, a solitaire boardgame first created in 1950. The board has 24 numbered spaces plus an empty center space, and 24 numbered tokens placed randomly. The idea is to slide pieces along lines into the open space, and restore all the numbered pieces to the appropriate spaces.
It is similar in concept to the popular 15-puzzle: a sliding block puzzle, but with a larger search space. The number of possible board starting positions is 24!=620,448,401,733,239,439,360,000, or about 620 sextillion possible configurations. Clearly exhaustive search is not a good way to proceed with this problem.
Nevertheless, it appears to be on the border of doability using clever versions of iterated deepening A*. Korf and Taylor found optimal solutions for the simpler 24-puzzle.
I’ve begun working on implementing a computer player using ideas from their papers.