Several years ago I was playing a puzzle game with my dad and my sister called Solitaire Chess. We eventually got stuck on a puzzle for hours, and unlike the other similar puzzle games we have, the back of each card describing the puzzle wasn’t the solution but another puzzle. To find the answer I decided to write a program to solve it. I spent the rest of the evening and some of the next morning working on it until I found the solution.
Solitaire Chess is based on how chess pieces capture each other. Instead of pieces only being able to capture a piece of the opposing color, all the pieces are the same color and can take any other. The starting arrangement is defined by the puzzle’s card, and your goal is to eliminate all but one piece only through capturing. ThinkFun’s product page demonstrates this well:
ThinkFun’s how to play Solitaire Chess image (altered)
Or at least it would have if they didn’t put moves two and three the wrong way around:
ThinkFun’s how to play Solitaire Chess image
Making a program that solves any puzzle isn’t too complicated. To code how each piece captures other pieces I created helper methods to define their movement by either relative positions or a “look direction.” Kings, knights, and pawns can only capture pieces at a few positions relative to them, and rooks, bishops, and queens “look” in different directions and can only capture in their line of sight. If I was doing this project now I would probably use an enum for the piece types, but at the time I decided to use static instances of an abstract class.
I used recursion to do what I later learned is called a depth first search. The program iterates over all possible next boards states and makes a recursive call using each of them to solve the puzzle from there. If there are no more possible moves, the attempt either failed because there are still multiple pieces left, or the program has found the solution. I never bothered to have any kind of input or output for the program, so the puzzle setup is hardcoded in a 2d array, and I just used IntelliJ’s debug mode to view the resulting list of moves.
Much later I found out that the solutions to the puzzles were in the instruction manual all along. But at least I enjoyed the project.
You can find the code on my GitHub here.