Toy project to solve a cat puzzle my daughter had. The puzzle consists of a 5x5 tile Board in which cats are placed in certain locations. Moveable pieces of various Shapes are then placed onto the board. Each Shape covers multiple Points on the Board and includes one or more box Points. The goal is to move the Shapes, one at a time, to put all the cats into boxes. The starting locations of the cats and boxes determine the complexity (number of steps) to solve the puzzle.
Input is configured in index.js. The Board (dimensions and cats) is configured via text input. Shapes are plotted via Points with (0, 0) representing the upper left corner of the Board. I started on a shape_parser branch to pull all the data from the text input but never completed it.
The output is a series of Board configurations moving from the initial configuration to the final state. It should represent the shortest path (least moves) to the solution.
My solution is a depth-first search of the board space in order to find the shortest path to a solution. The algorithm is essentially:
- Push the initial board state onto a queue
- As long as the queue has entries...
- Pop the first board off the queue
- If it's in a solution state, we're done. Trace back the history to get the path from start to solution
- Otherwise, enumerate all possible child boards and push any that are not states we've seen before onto the queue
- Repeat until we find a solution state
- If the queue is empty and we didn't get to a solution state then the puzzle isn't solveable
Execution uses nodemon to re-execute if code changes
npm install
npm run watch