Skip to content


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Basic BFS/DFS Solver for 2d, rectangular puzzles in C++
branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.


Basic BFS/DFS Solver for 2d, rectangular puzzles in C++

Play around with this code--it is far from a perfect programming example. If you are new to C++, pick up "Effective C++" by Scott Meyers and review this code with a critical eye. While many best-practices are followed, there are stylistic choices that could be improved, inefficiencies to be addressed and enhancements begging to be implemented. I've included some challenge questions to help you get started--have fun playing games with games!

Matt Taylor, 2010

To compile, you will need to link against -lboost_regex -lboost_program_options

Challenge questions:

1. Tile sort uses distance from the "home square" to assign each piece, 
   position and move a score. Implement a scoring method for TrafficJam.  
   What components should be part of the score?  Which score algorithms 
   seems to work the best?  Why?  What edge cases are still missed?

2. Two search algorithms are provided: Breath First Search and Directed 
   Walk.  What are the differences between these two approaches?  What 
   are the pros and cons of each approach?  With this in mind, implement 
   depth first search.  How does DFS compare to the approaches already 
   provided?  How does it compare to the hybrid approach--and should DFS 
   be included?

3. List out all the examples of the boost library used in the source code.  
   What other tools from boost could be used to make the code more robust 
   or easier to read/maintain?  What are the pros and cons of BOOST_FOREACH,
   vs traditional for loop, vs while loop?

4. Why do you think the author added IBoardGameSolver and IPuzzleFile?  
   Would you add other interfaces, remove these, or change them in some way?

5. Most design decisions need to be made before the applicaton is complete.  
   What are the key design decisions for this program?  What would you have 
   done differently?  Would you change it, or live with it as-is?

6. A lot of shared pointers are used throughout the application, but 
   sometimes raw pointers are used instead.  Why is there a mix of raw and 
   shared pointers?  Should there be?  What would you use instead?  What is 
   the danger of mixed managed/unmanaged pointers?  If you would make a 
   change, implement it.

7. Pick another 2-d puzzle you like and implement the appropriate Board, 
   Space and GamePiece classes.  Make this new puzzle an option at the 
   command line.  For an extra challenge, implement a more complicated puzzle
   like Colorsok ( where
   the playable space is not rectangular and many moves don't change the
   state of the game.

8. "Avoid returning 'handles' to object internals" states Item #28 of 
   Effective C++, 3rd Edition (Scott Meyers). How does the BoardGameSolver 
   class disregard this suggestion?  Rework the class to follow Scott Meyer's 

9. What infrastructure would be needed for two player zero-sum games (such 
   as Chess "mate in N moves" puzzles).  Rework this code to handle such 
Something went wrong with that request. Please try again.