Authors: Diane Horton ( and David Liu (

Sample Blocky board with maximum depth 5


A visual game in which players apply operations such as rotations to a recursive structure in order to work towards a goal. The main data structure is a quad-tree, so this assignment provides lots of practise with recursion and trees. Students also implement some interesting and challenging algorithms.

Game assignments may be less appealing to female than male students [1], so we designed a game that is puzzle-like, with simple rules, but that is challenging to play. We think the game board is attractive, bearing a resemblance to a Mondrian painting, and the colour scheme can easily be configured by students - this is surprisingly satisfying!


Summary Students build a visual game that operates on a recursive structure.
Audience CS2.

Our implementation is in Python, with pygame for rendering, but the assignment could easily be adapted to another object-oriented language.

Difficulty The assignment is challenging but doable. The starter code is substantial and some of the algorithms are quite tricky, in particular:
  • Converting a quad-tree into a corresponding 2-D representation of uniformly-sized squares.
  • Finding the largest connected region of a given colour.
  • To help students approach the assignment, we provide an extensive handout that breaks the work into a series of tasks, and offers a way to check correctness at each step.

We ran this assignment very successfully in our CS2 with 450 students. Students had three weeks to complete the assignment and were allowed to work in pairs at their discretion. In addition to office hours and discussion board support, we devoted 30 minutes of class time to discussing the data structures and key algorithms when the assignment was released. Our students were very successful, on average earning 85% on the assignment.

Topics The primary topics covered are:
  • Recursion: The board itself is a recursive structure. Building the board, applying moves to it such as rotate-clockwise, and evaluating the score are all naturally recursive.
  • Trees: The board is represented using a quad-tree, and most of the recursive algorithms operate on it.
  • Inheritance: The code uses inheritance and polymorphism, both for different types of game goal and for types of player (a human player, a random computer player, and a smarter computer player).
Strengths The game is visually appealing and students many enjoy showing it off to friends and family. Thwarting your opponent's efforts to reach their goal can be as fun as working towards your own goal. It is fun also to watch two computer players of differing ability compete against each other.

The coverage of recursion is thorough, with methods ranging from straightforward to difficult. We like that students implement some algorithms that require deep thought beyond just getting the recursion.

Students experience a problem for which a dual representation (quad-tree and 2-D) is motivated.

There are many non-trivial and critically important invariants and preconditions in the code. Because these are lifelines when students write the code, the value of carefully documenting code properties like invariants and preconditions becomes clear.

All rendering code is provided, and all functionality can be autotested. A self-test is available for providing to students, and a full test suite is available for instructors.

Weaknesses When applying an operation to the board, the code updates the rendering but does not animate the change. It can be difficult to see what happened.
Dependencies The assignment assumes students are familiar with recursion, trees, and inheritance.
Variants Difficulty can be reduced, while still leaving plenty of recursion, by removing the goal to create the largest connected blob of a certain colour. This eliminates the two most challenging algorithms: converting to a 2-D representation, and finding the largest connected blob. The size of the assignment can be reduced by simplifying to a one-player game without scoring. Playing the game would be somewhat analogous to playing with a Rubik's cube.

Students could be asked to invent and/or implement new types of move. Possibilities include:

  • splitting each undivided block into four undivided sub-blocks of random colours.
  • merging each block that has four undivided sub-blocks into a single block of the majority colour. (Ties can be broken randomly.)
  • randomly changing all the colours while maintaining the same structure.

Students could be asked to invent and/or implement new types of goal. Possibilities include:

  • placing as much of one colour as possible on a diagonal.
  • distributing one colour as much as possible. (Even defining the measure for this goal is interesting.)

If an open-ended, exploratory task is appropriate, students can investigate the playability and difficulty of the game, perhaps even playtesting it. This could spark ideas for new move types and goal types.

Students can invent and implement new algorithms for a smart computer player, or implement a known algorithm such as minimax.

An undo operation could be added. If multiple undos are allowed, which would make sense in a solo game, this opens up a discussion about whether to store previous board states or previous operations, and the associated time-space tradeoffs.

Students could turn Blocky into a game for the web or their phone by plugging in a different renderer class.

The Game

Blocky is played on a randomly-generated game board made of squares of four different colours. We call the game board a "block." A block is either:

Each player is randomly assigned their own goal to work towards: either to create the largest connected "blob" of a given colour or to put as much of a given colour on the outer perimeter as possible.

There are three kinds of player moves:

What makes moves interesting is that they can be applied to any block at any level. For example, on the board on the left below, the user has chosen a block (highlighted) that is two levels below the top level. Rotating it clockwise would result in the board on the right.

Blocky board before a move Blocky board after the move

Data Structures

Blocks are represented using quad-trees. For example, suppose we set the maximum depth to just 2, and had this simple game board:

Blocky board with maximum depth 2

Its quad-tree would have this structure, where the children represent the upper-right, upper-left, lower-left, and lower-right sub-blocks, in that order:

Quad-tree representation of a Blocky board

Our implementation stores additional information in each node, including the size and position of the square, and includes a rich set of invariants that express, for instance, that:

When scoring a player who has a "blob goal", we need to find the largest connected blob of the target colour. This is much easier to do on a 2-D representation than on a quad-tree, so students derive a 2-D representation from the quad-tree. The algorithm is tricky, because a block of uniform colour may need to be treated as 1 square, or 4 squares, or 16 squares, etc. depending on how finely divided the game board is. The board above, for example, is 4-by-4 in the 2-D representation, since a maximum depth of 2 allows the board to be divided into up to 16 squares. We implement the 2-D representation as a list of lists of colours.

Assignment Materials

For the benefit of the community, we ask that adopters of the assignment do not post solutions or more of the starter code than we are providing here.

Contact Us

We'd love to hear your feedback! Reach us at and


[1] See for example "Gender Differences in Types of Assignments Preferred: Implications for Computer Science Instruction," Brenda Cantwell Wilson, Journal of Educational Computing Research Vol 34, Issue 3, 2006, pp. 245 - 255.