The rules of the IOS app we created, PathPuzzles, are very easy.  There aren't many of them and they mostly have to do with counting small numbers.  Yet, right out of the box, the rules aren't quite simple enough for a computer - there are many corner cases that humans can reason about intuitively, but that a programming language can't.

I realized that the most important problem that I needed to solve was how to represent the board in a digital format.  Until Rod got us involved to build an app, all of the puzzles were drawn by hand and then rendered in a graphics application before being printed.  They are fundamentally just graphics that don't contain enough context to be able to perform useful operations on them.  We needed a model that we could manipulate in a meaningful way through code.

//

The structure of a puzzle is pretty simple to look at: a set of contiguous cells that form a room.  All of the cells are squares that are bounded by walls that are either solid or contain a door.  Furthermore, the room must contain at least two external doors (entrances) so that you can get in and get out of the room.  The intuitive first solution is easy enough to define the board as a two-dimensional array of cells, each of which has values specifying its 4 walls (top, left, bot, right) as either solid, door, or none.  However, this approach turns out to be naive because you have to consider how to represent two adjacent cells?  If they are joined by a door then you have, A.right = door and B.left = door.  But this means you are specifying this door twice, which violates the DRY principle.  More importantly, you now have to have additional logic to make sure that your boards are always consistent: it would not ever make any sense for A.right = door and B.left = solid.  This isn't a picture that would make any sense.

//

Instead, I decided that cell walls would only be specified once as the top and left sides of a cell.  In this way a cell unambiguously "owns" exactly two edges and  that can be specified as a door, wall, or blank in exactly one place.

//

Now, because cells can only ever have walls along the top and left, when you need walls along the right or bottom of your puzzle, you actually have to extend the domain of cells in order to represent those positions.

A similar problem occurs when determining how to represent a path through the puzzle.  The obvious first approach would be to store a list of coordinates that the path goes through.  But this data structure actually makes it really hard to edit efficiently.  If you want to remove one segment and change the route you end up having to splice the list in complicated ways.  Furthermore, if you edit the path in certain ways you could change the sense of the direction of the path.  The same line segment could be represented by {(1,0) (1,1)} or by {(1,1) (1,0)}.  This type of ambiguity is also difficult to code with.

//

A better solution is to enumerate all of the possible segments of paths on the board and then simply flag which ones are present.  It turns out we already have a data structure that is similar to this because every path segment is drawn perpendicular to a cell edge.  We can actually represent an arbitrary path through the puzzle in a canonical format by using the same type data structure used for the board with two boolean fields: one is set if the path starts in the cell and goes up (through the top edge), and another if the path starts in the cell and goes to the left (through the left edge).  The whole board data structure ends up in a JSON object.

‍
Once we developed a canonical way to represent a board and a solution path in memory it became really easy to serialize them and create a database of puzzles and solutions. Reasoning about the game becomes really easy to implement in terms of standard programming algorithms: finding a solution to a puzzle just requires implementing a breadth-first search.  We were also able to build validation routines that ensure that the boards in the database are legal and solvable but also unique up to rotation and reflection.

Having a really strong object model that we all agreed on meant that it was straight-forward for a few people to build the game logic in JavaScript, while others built validation and constraint checking logic on the server side in C#.  Because the model was well understood very little conceptual work was actually duplicated in the two different environments, yet they interact with each other nicely.

The challenge of Path Puzzles was defining an elegant data structure that is expressive enough cover all valid board arrangements, but that is concise enough to structurally prevent ambiguity. This is the test of a good abstraction: it solves exactly the problem it needs to and don't get in the way of anything else.  That is model programming.

‍