15-Tile Puzzle

CSC8501-Advanced Programming for Games (C++) - Code Samples

Introduction

A combinatory problem for the final year of my degree. The C++ program can generate 15-tile style puzzles (writing them to a file), and calculate the number of rows and columns which can appear in order (increment by 1 as you go right/down) of all the reachable states of the puzzle. This is then written to a file.

What I Learnt

This was the first time I had properly tackled a combinatory puzzle, thinking about how best go through each possible combination of tiles, counting rows/columns which were continuous. Also, although I had used C++ earlier in my degree, this module was a useful refresher of the language.

Images

Implementation

C++ features involved

  • Object Orientation, inc. inheritance
  • C++11 features, inc. Lambda Functions
  • Common design patterns, inc. factor classes

Program Outline

  • The program is controlled by a main file which handles menus and instantiation of other classes.
  • A factory class is used to create/load from file Configuration classes which store the state of a particular puzzle.
  • The configuration class was extended to allow puzzles of any rectangular size and tiles between 1-1,000,000.
  • A solver class takes in a series of configuration objects to solve. The initial idea was to walk through each of the possible states, counting the number of continuous rows/columns, but is was felt this would be too slow for the larger puzzle sizes, so an equation was used instead.
  • The solver then stores the solutions in a struct to be printed to screen or written to a file.

Possible Improvements

  • The problem simply concerned 2d puzzles. As such, further work could be done to storing and solving puzzles of arbitrary dimensions.