Journal of New Music Research, 2017Vol. 46, No. 3, 213–228, https://doi.org/10.1080/09298215.2017.1303519

The CrossSong Puzzle: Developing a Logic Puzzle for MusicalThinking∗
Jordan B.L. Smithand Jun Kato

, Satoru Fukayama, Graham Percival and Masataka Goto

National Institute of Advanced Industrial Science and Technology (AIST), Japan(Received 27 July 2016; accepted 23 February 2017)

Abstract
There is considerable interest in music-based games and apps.
However, in existing games, music generally serves as anaccompaniment or as a reward for progress. We set out todesign a game where paying attention to the music would be
essential to making deductions and solving the puzzle. The
result is the CrossSong Puzzle, a novel type of music-based
logic puzzle that integrates musical and logical reasoning. The
game presents a player with a grid of tiles, each representing
a mash-up of excerpts from two different songs. The goal is torearrange the tiles so that each row and column plays a continuous musical excerpt. To create puzzles, we implemented analgorithm to automatically identify a set of song fragments tofill a grid such that each tile contains an acceptable mash-up.
We present several optimisations to speed up the search for
high-quality grids. We also discuss the iterative design of thegame’s interface and present the results of a user evaluation of
the final design. Finally, we present some insights learned fromthe experience which we believe are important to developing
music-based puzzle games that are entertaining, feasible andthat challenge one’s ability to think about music.
Keywords: games, puzzles, mash-ups, interfaces, software

1. Introduction
Why is listening to music enjoyable? One hypothesis is that alistener’s pleasure derives (at least in part) from one’s ability
to detect patterns in the music, thereby ‘compressing’ it in
one’s mind (Schmidhuber, 2009). There is some evidence
that, compared to other works, compositions widely regarded
as musical masterpieces may be more compressible, despite

having a more complex surface representation (Hudson, 2011).
If this hypothesis is correct, then pattern identification is central to the enjoyment of both music and puzzles. In logic
puzzles, such as sudoku, solvers are tasked with identifying
patterns and discovering strategies to take advantage of themin order to complete the puzzle. To solve a puzzle can be seen
as an act of entropy reduction: to assemble a scattered pile ofjigsaw pieces into an image; to fill a series of blanks, whose
values are uncertain, with fixed values.
If music and puzzles are enjoyable for similar reasons,is it possible to devise an activity that combines the two?
Despite some historical precedents (discussed in Section 2),
few activities target those with an interest in both. This may
be due to an inherent difference that puts the pastimes at odds
with each other: puzzles have no tempo or schedule—they aresolved at the solver’s own pace—while music is defined byits happening in time, and interruptions or sudden changes inrhythm or playback will detract from the experience. Devisinga satisfying combination of active listening and puzzle-solving
is therefore a difficult challenge.
In this work, we have embraced this challenge. The result is
the CrossSong Puzzle (see Figure 1), a real-time puzzle gamein which the solver listens to the audio ‘clues’without interruptions. In the 4×4 grid of tiles, each row and column represents
a four-part excerpt of a song. Each tile thus represents a mashup of two songs. The solver is presented with a scrambled grid,and the object of the puzzle is to reconstruct the excerpts bylistening to the tiles and rearranging them. The excerpts are
metrically aligned and time-stretched to the same duration
so that all beats coincide. Gameplay is continuous: the tiles
play one after the other, smoothing the discontinuities between
the different mashups. The result is akin to an indefinite,reconfigurable remix of the source songs.

Correspondence: Jordan B.L. Smith, National Institute of Advanced Industrial Science and Technology (AIST), Central 2, 1-1-1 Umezono;
Tsukuba, Ibaraki; 305-8568; Japan. Email: jordan.smith@aist.go.jp∗An early version of this article won the Best Paper Award at the Sound and Music Computing conference in Maynooth, Ireland, in 2015.
© 2017 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group.
This is an Open Access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives License(http://creativecommons.org/licenses/by-nc-nd/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium,provided the original work is properly cited, and is not altered, transformed, or built upon in any way.

214

Jordan B.L. Smith et al.

Fig. 1. CrossSong puzzle overview. Green tiles indicate correct placement. The solver cannot see the labels and must deduce the correct orderby listening to the tiles. Demo application and gameplay video available at: https://staff.aist.go.jp/jun.kato/CrossSong/.

The CrossSong puzzle may call to mind the classic 4×4
sliding-tile puzzle, in which the goal is to reconstruct an image
given similar constraints. However, its highly constrained construction more closely resembles that of a crossword puzzle. A
cruciverbalist (a constructor of crosswords) must find suitablewords to fill a grid such that wherever two words cross, theletters match. Likewise, to make a pleasing CrossSong puzzle, we must find suitable song excerpts such that wherever
two songs cross, a pleasing mash-up is made. Discovering
a set of excerpts where this is possible is challenging but,
we anticipate, essential for the enjoyment of the puzzle. The
algorithm we developed for doing this, based on the work ofDavies, Hamel, Yoshii, and Goto (2014), is one of our main
contributions.
What is the purpose of our game? Besides being fun on
its own, a music-based puzzle game may prove useful formusic education. Common sense, partly backed up by a bodyof literature, argues that games and puzzles are useful for exercising basic cognitive skills (Griffiths, 2002). Even advanced
subject knowledge, like molecular chemistry, can be reinforced with the appropriate use of games (Crute, 2010). Uniqueamong music-related games (discussed in detail in the next
section), CrossSong has been designed to encourage ‘musical thinking.’ The puzzle requires solvers to isolate rhythms,
timbres and melodies in their mind in order to identify connections between the tiles. Such careful listening may flex theirmusicianship.
Section 2 reviews existing combinations of music and puzzles, as well as previous work in mashability estimation. The
rest of the article is structured around the main contributions of
this work: Section 3 gives a formal overview of the proposed
CrossSong Puzzle design, including gameplay and implementation; Section 4 describes the grid construction algorithm anda test of several grid search heuristics; Section 5 discusses
the iterative development and testing of the interface, andthe design principles which guided it; Section 6 presents theresults of an evaluation of the finalised design; and we discuss
the project and give concluding remarks in Sections 7 and 8.

2. Related work
In this section, we first review prior examples of games basedon music. Second, we review existing software for creatingand estimating the quality of mash-ups.
2.1 Musical puzzles and games
The earliest type of musical puzzle may be the puzzle canon,
which has existed since at least the fourteenth century(Ciconia, 1993, p. 411). In a canon, a melody is set against adelayed, possibly transposed repetition of itself. In a puzzle
canon, a single melody is given, and the solver must determine
the delay and transposition required so that the result obeys
the rules of counterpoint. After several dissonant attempts, thesolver is rewarded with the harmonious result once they findthe correct solution. It is possible to propose any melody as a
puzzle canon, without a solution in mind—such is the origin of
Bach’s famous ‘Musical Offering’—but in this case a solution
is not guaranteed to exist.
Puzzle canons may be treated as a curiosity, but in truth,
most exercises in counterpoint training can also be seen as puzzles. Species counterpoint, a practice that is a fundamental partof many undergraduate music theory curricula, is a practice ofwriting music with strict melodic and harmonic constraints.
Typical counterpoint exercises, like writing a melody above abassline or harmonising a melody as a chorale, can be regarded
as logic puzzles. Although there are usually many solutions,finding any solution without breaking a rule is challenging
enough.
An example of turning music-making into a game, rather
than a puzzle, is the musical dice game, a form popular inWestern Europe in the 1700s (Hedges, 1978), in which randomrolls of the dice were used to choose a selection of score fragments which could then be performed for one’s amusement.
The dice game is an important ancestor to modern algorithmic
composition (Nierhaus, 2009, p. 36). A recent system forgenerating medleys of existing recordings is also inspired by
the dice game (Lin, Liu, Jang, & Wu, 2015).

The CrossSong Puzzle

215

the pieces are in incorrect order, the result can sound not
only incorrect but also unmusical. It would be preferable todivide the fragments only at beat or downbeat positions. In
fact, some music psychology experiments suggest that musicthat is divided and reassembled at a sensible timescale can be
as enjoyable to listeners as the original (Upham & Farbood,2013).

Today, there are many web- and smartphone-based games
which are based on music; however, a partial survey (Dubus,
Hansen, & Bresin, 2012) suggested that the market is dominated by sound banks, multimedia players, instrument emulators and music-creation apps like synthesisers and sequencers.
In those apps and games we are aware of that do combine
music and puzzles, the link between the music and the puzzle
mechanics is rarely strong. In most cases, the logical reasoning
is separate from the music, which instead serves as a progress
indicator or as a kind of reward, generated by the game stateor triggered by the correct solution to the puzzle.
For example, in the puzzle game Auditorium,1 players mustarrange attractors, repellers and other items in order to guidea stream of light particles to a set of sinks. Each sink activatespart of the soundtrack, so the music reflects one’s progress in
the level. The gradual superposition of musical parts makes apleasing soundtrack, but the game could be played just as easily with no audio: all of the musical cues that indicate progress
are redundantly matched with visual cues about which sinks
are active. The same observation—that the music does notconvey any crucial information—could be made for othermusic puzzle games such as Chime,2 Lumines,3 and FRACT
OSC.4
A related category of music-based video games, known asrhythm games, includes DrumMania and the hugely popular
Guitar Hero5 series. In these games, the challenge is to executea sequence of physical actions indicated by a stream of visualcues. In contrast to the aforementioned music puzzle games,
hearing the music is essential for rhythm games in order toentrain to the beat.Also, since the cues often match the melodic
contour of the music, musical knowledge could help a player
entrain to the cues. However, these are better described asphysical challenges than as puzzles.
What is missing is a puzzle where the music is the sourceof information used by the solver, and which demands careful
listening. To our knowledge, the only predecessor with thisfeature is the prototype game developed by Hansen, Hiraga,
Li, and Wang (2013), who developed a musical analogue ofa jigsaw puzzle. A 15-second excerpt of music is divided into
pieces and the solver’s goal is to arrange the pieces from left toright in order to reconstruct the original excerpt. As an added
challenge, the audio of several pieces has been randomly transposed; the solver must detect and undo these transpositions inorder to complete the puzzle.
Their design has limitations that ours aims to overcome.
First, playback is not continuous: puzzle pieces must be individually triggered, which reduces the immersiveness of the
gameplay and of the music. Second, each musical excerpt isdivided into pieces at arbitrary timepoints, so the resulting
pieces do not sound like coherent fragments. Thus, when

We propose a new type of puzzle, the CrossSong puzzle (described in the next section), but in doing so we must also
propose a method of creating instances of this puzzle. Puzzles
could be created by hand, but this would be cumbersome,and would preclude the possibility of generating puzzles ondemand for users who want puzzles that feature music of
their choosing. Thus we would prefer a fully-automated gridcreation algorithm. Some modern mobile games use automated music analysis to generate level content, including AudioSurf 6 and Record Run.7 Levels in Guitar Hero are createdindividually by humans, but the research prototype Beat theBeat (Jordan et al., 2012) uses rhythmic information extracted
from the audio to generate levels for a Guitar Hero-like minigame.
For the CrossSong puzzle, we require an algorithm that can
do two things: first, automatically align the beat of two pieces
with beat-tracking; and second, estimate the quality of theresulting mash-up at multiple shifts in pitch. The problem ofbeat tracking constitutes a field of its own; see Hainsworth(2006), among others, for a review. Downbeat tracking is aneven harder problem that continues to inspire a large amountof research (see, e.g. Krebs, Böck, & Widmer, 2013). Many
tools are capable of estimating beat locations, and some ofthese directly facilitate the creation of mash-ups, such as the
Echo Nest Remix API8 (discontinued as of May 2016, andsuperceded by the open-source toolbox Amen9 ).
A growing number of systems can use this information tocreate mash-ups autonomously. Beat-Sync-Mash-Coder(Griffin, Kim, & Turnbull, 2010) computes beat information
and uses it to automatically synchronise and loop the playbackof two excerpts, but the excerpts must be extracted from fulllength audio files manually by the user, and the system does
not attempt to match the pitch of the excerpts. The commercial system Mixed In Key10 estimates the mutual harmoniccompatibility of all songs in a collection, and can recommend
source material for users to create mash-ups on their own.
However, the compatibility estimate is on a song-to-song basiswith no timing information; this is too coarse for our purpose,
since the compatibility of two excerpts can be greatly affectedby the phase of the excerpts. The dice-game-inspired system

1 http://www.cipherprime.com/games/auditorium/.

6 http://www.audio-surf.com/.

2 http://www.chimegame.com/.

7 http://www.harmonixmusic.com/games/record-run/.

3 http://lumines.jp/.

8 http://echonest.github.io/remix/.

4 http://fractgame.com/.

9 https://github.com/algorithmic-music-exploration/amen.

5 http://www.guitarhero.com/.

10 http://mashup.mixedinkey.com/HowTo.

2.2 Automatic remixing and level creation

216

Jordan B.L. Smith et al.

cited earlier (Lin et al., 2015) produces pleasing medleys, butthese are concatenations rather than overlapping mash-ups ofmusic.
Among existing systems, AutoMashUpper (Davies et al.,2014) fulfils our requirements best. First, it performs beat,downbeat and phrase-level boundary detection; this is important because mash-ups between phrases that are intact andaligned downbeat-to-downbeat sound better, at least in theopinion of the authors. Second, it estimates the harmonic,
rhythmic and spectral compatibility of two phrases at all possible shifts in pitch and time. The harmonic compatibility of twosegments is taken as the correlation between chromagrams
estimated from the audio. Rhythmic compatibility is estimatedin the same way, using a rhythmic feature derived from thepattern of estimated kick and snare onsets. Finally, the coarse
spectra from each segment are compared; the flatter theirsum, the more the two excerpts are deemed to have complementary spectra, and the greater their mashability. Detailsof this algorithm can be found in Davies et al. (2014). A
competing algorithm, proposed in Lee, Lin, Yao, Lee, and Wu(2015), uses a similar approach but also attempts to ensure
fluid transitions between successive sections of the remix,
which is not a concern for the present application. In Section 4,
we describe how AutoMashUpper was adapted for our needs.
It should be noted that AutoMashUpper makes many strong
assumptions about the rhythmic regularity of the piece: constant tempo, constant 4/4 metre, and for the most part, phrases
that are 2n bars long. These assumptions clearly do not apply
to all music, so they present a problem for our system. The
user should be aware of this constraint and avoid selecting
music in different time signatures. In the future, an automatic
metre-detection step could be developed to quickly warn users
of incompatible songs.

3. CrossSong puzzle
The CrossSong Puzzle was described briefly in the introduction. In this section, we explain the design and construction of
the puzzle in more detail. Later in Section 5, we explain how
our design evolved over a series of user tests.
In its solved state, the puzzle contains excerpts from 8
different songs, labelled A–H , one for each row and column ofthe grid. (See Figure 2.) Each song excerpt has the same length
in beats, which is some multiple of four, so that each may be
divided into four parts: X 1 –X 4 for song X . With each excerpt
time-stretched to the same duration and spread across fourtiles, each tile is assigned two parts that play simultaneously
as a mash-up: one from the ‘across’ song and one from the‘down’ song.
The solver begins the puzzle with the tiles arranged randomly, and their task is to determine the correct order bylistening to the tiles. Due to the symmetry of the puzzle, there
exist two solutions (i.e. the arrangement in Figure 2 and its
transpose); therefore, we must fix one off-diagonal tile in place
and reveal its correctness to the solver.

Fig. 2. Illustration of CrossSong Puzzle interface. In addition toindicated controls, clicking on two different tiles swaps their position.
Row, column and tile labels are added for clarity, but do not appear
in the interface. X i indicates the ith part of excerpt X .

During gameplay, audio playback is continuous: the tiles
play one after the other, first by row (from left to right, top
to bottom), then by column. The tile currently being played
is highlighted. Because all the tiles have the same durationand tempo, even in the initial random configuration there is arhythmic coherence to the music.
The player can perform two actions: first, they may click on
any two tiles to swap their position. Second, they may clickon arrows outside the grid to choose which row or column toplay next after the current tile has finished playing. It is also
possible to pause and resume the game. A link to a gameplay
video is given in Figure 1. For beginners, solving a single
puzzle takes roughly 10 min; an expert par time is closer to
3 min.
Normally, the two clips in each tile are played with equal
loudness. However, as a hint and a reward for partial progress,
the balance between the clips changes if the tile is positioned
correctly with respect to its neighbours. The more correctneighbours, the more the mixing is reduced. The concept of‘relative cell correctness’ is illustrated in Figure 3(a). In thisexample, the tile B3 -G 2 has one correct horizontal neighbour,
since the tile B2 -F2 belongs to its left in the solved puzzle. The
impact of this arrangement is seen in Figure 3(b). When B3 G 2 is played as part of the current row (horizontal playback),instead of the mix being 50/50, it will be 75% B3 and 25% G 2 .
When played as part of the current column (vertical playback),
since both vertical neighbours are correct, the mix will be
100% G 2 and 0% B3 . It does not matter if B3 -G 2 is in thecorrect position within the 4 × 4 grid; this audio mixing isbased only on relative correctness.
We implemented the game as a web-based application. Thishas the advantage of making it instantly cross-platform: wehave played it successfully on a desktop with a mouse, on asmartphone with a touch screen, and even on a large-format
touch screen with multiple users (as pictured in Figure 9).

The CrossSong Puzzle

217

each set, there are 8!/2 = 20160 ways of arranging them inthe 4 × 4 grid. (The factor of 2 reduction recognises that any
arrangement and its matrix transpose are equivalent.) Finally,each excerpt may be transposed (in pitch) up to 3 semitones
upwards or downwards, increasing the space by a factor of
107 . (Precisely, it is a factor of 78 − 68 , or 4,085,185.) In total,
this means 1028 different solutions—about 10,000 moles—
clearly too many to search exhaustively.
Before explaining how we reduced this search space, hereis the overall procedure for computing mashability, searchingfor an optimal mash-up, and processing the audio.
(1)
(2)
(3)
Fig. 3. Diagrams for how neighbour correctness is calculated for agiven tile, B3 -G 2 , and the resulting balance when played as part ofa row or column.

Once a puzzle has been generated (discussed in Section 4), it
is presented to the player in a JavaScript interface. We used
the Web Audio API, allowing us to leverage the increasing
capabilities of modern web browsers for interactive audio
applications (Wyse & Subramanian, 2013).

4. Puzzle creation algorithm
As described in Section 2, AutoMashUpper estimates the
mashability of two excerpts as a function of their harmonic,
rhythmic and spectral compatibility, considering a range ofpossible transpositions. AutoMashUpper finds, for a given
section of a song, the single best matching segment among
a list of other songs. Our goal is different: to find a set of eightsong excerpts, each of which can be divided into four equalsized clips, such that, when arranged into a 4×4 grid, eachcombination of clips forms a good mash-up.
The problem is similar to generating a crossword puzzle
grid: for that task, letters must be found which create acceptable words in each direction. However, a strict similarity
function applies for letters—they are either the same or not—but no binary measure of acceptableness is available to us formusic. The crossword generation problem, though seemingly
straightforward relative to our task, has been researched for
decades (e.g. see Ginsberg, Frank, Halpin, & Torrance, 1990).
It is a complex search problem that is NP-complete (Engel,
Holzer, Ruepp, & Sehnke, 2012).
Our primary obstacle is the vast space of combinations tosearch. Each excerpt can begin on any downbeat, meaning
there are roughly 100 choices of excerpt in a typical song
(this is the case for a 120BPM song that lasts 3:20). For 8
songs, this gives 1008 = 1016 possible sets of excerpts. For(4)

Extract harmonic, rhythmic and spectral features fromthe 8 recordings (Davies et al., 2014)
Estimate the mashability of all pairs of points in two
different songs (Davies et al., 2014)
Search for the choice of excerpts and their arrangement
in a grid that maximises mashability
Process audio clips to generate the puzzle grid(a) Apply time-stretching and pitch shift tomatch all excerpts using Rubber Band library(Cannam, 2012)(b) Match loudness of all excerpts using FFmpeg11

Feature processing (step 1 in the list above) requires roughly
14 s to analyse each song (based on an average 3-minute song).
Step 2, computing the mashability, takes roughly 0.5 s per pairof songs, or 14 s overall for an 8-song puzzle. These steps
can also be executed in advance if the library of music waspreviously known to the system. The audio processing using
Rubber Band and FFmpeg takes about 10 s. The bottleneck is
the incredible number of random sets of excerpts.
There are several dimensions to the search in step 3. First,
we choose a set of 8 songs, labelled P through W ; we areassuming that this is fixed by the user. Second, we select anexcerpt from each song; let P p represent the choice of segmentp from song P. Third, we fit the songs into the grid; i.e.
we choose a mapping of {P, Q, . . . , W } → {A, B, . . . , H },where {A, B, C, D} are the rows and {E, F, G, H } are thecolumns, as before. For a choice of segment indices { p, q, . . . ,w}, it is computationally cheap to find the optimal mappingin the grid. Thus, in the search algorithm, we focus on finding
the best choice of song segments to use.
In step 3, we estimate the quality of a solution grid by taking
the sum of each tile’s mashability M(X, Y, d X Y ). Here, X ∈{A, B, C, D} is a row excerpts, and Y ∈ {E, F, G, H } thecolumn excerpts, and d X Y represents the delay required forthe given combination of row and column. For example, fortile (A, G), we are interested in the mashability when excerpt
G is delayed by half its length with respect to excerpt A; thisis because, as we saw in Figure 2, G 1 (the first bar of G)
coincides with A3 .
11 http://www.ffmpeg.org.

218

Jordan B.L. Smith et al.

4.1 Search optimisations
There are two ways to make the search space less daunting:to reduce the search space, and to improve how the searchalgorithm scans the space. Our search optimisations include
both techniques.
4.1.1 Eliminating segments
We have already limited our search space to passages thatbegin on downbeats. We can further reduce the search spaceby restricting ourselves to excerpts that begin at one of thesection boundaries estimated by AutoMashUpper, which uses
a variation of the classic Foote algorithm (Foote, 2000). This
restriction increases the odds that each excerpt will be an intact
phrase of a song, and reduces the 100 or so excerpts in eachsong to roughly 20 to 30.
We can reduce the space even more by ignoring repeatedsegments. If a structural analysis predicts that two segments
are the same (for example, that both are choruses), then it is
not necessary to consider both in our search. What savingsare possible with this technique? In the SALAMI data-set, themedian number of large-scale segments with unique labels
is 4 per annotation (Smith, Burgoyne, Fujinaga, De Roure,& Downie, 2011). (For small-scale segments, the median is7.) Methods of detecting repetition are countless and range incomplexity; for a recent review, see (Müller, 2015). For speed
and simplicity, we can use k-means to cluster the potential
excerpts based on the features we have already computed: theharmonic, rhythmic and spectral features used by the mashability algorithm. For each estimated cluster, we retain theexcerpt that is closest to the cluster centroid, and ignore theothers. After this step, the number of excerpts is reduced from15 or 30 to k, which we can set freely. If the 100 potential
excerpts are reduced to 8, the search space shrinks by morethan 108 .
4.1.2 Eliminating transpositions
Our next optimisation is to only consider, for each pair of excerpts, the transposition that gives the optimal mashability—
even though this may not be the transposition used in the final
puzzle. This reduces the search space by a factor of 107 , but it
can clearly lead to problems: the final grid will require that all
the clips be transposed to match each other, but these optimaltranspositions might be infeasible. For example, suppose wehave chosen clips for slots A, B, E and F on the basis of theiroptimal mashability, disregarding the required transpositions.
We then transpose E 1 to match to A1 , F1 to match A2 and B1
to match E 2 . However, this fixes the transpositions of B2 andF2 , and the result may be dissonant.
In order to mitigate this, we compute mashability not between individual fragments (such as A2 and F1 ), but between
full excerpts (i.e. between A and F, with F delayed by one
quarter—i.e. M(A, F, d AF )). This creates some mutual dependence in the mashability values. In the previous example,
we know that B2 and F2 will match as long as B1 and F1 match.

Assuming all the mashability values are high, we know that B1
matches E 2 , which matches A2 , which matches F1 . Hence, tothe extent that harmonic compatibility is transitive, we can use
a greedy approach without worrying too much about conflicts
in transpositions.
Note that the problem above applies only to harmonic mashability. Rhythmic and spectral mashability are not affected bythis simplification, since neither are expected to be affectedby small transpositions in pitch.
4.1.3 Stochastic search
Since an exhaustive search would take too long, our aim is
to find the highest quality solution in a fixed amount of time.
Stochastic search strategies, such as simulated annealing, aredesigned to accomplish this. Simulated annealing strikes a balance between random search—always checking random new
solutions, exploring the search space broadly— and greedy
search, in which we focus on a narrow part of the search
space that seems promising. Crucial, then, is that we have aconcept of neighbouring solutions: if a solution is a vector{ p, q, . . . , w} of segment indices, then we can generate aneighbour by changing a single one of these values.
At each step in our search, we can either choose a random
solution or choose the neighbour of a good existing solution.
Briefly put, the trick of simulated annealing is to make thischoice probabilistically, and to transition smoothly from atendency for random steps at the beginning, to a tendency
for greedy steps near the end of the allotted time. The effect is
illustrated in Figure 4. The figure depicts a typical set of 100
solutions, ranked in order of mashability (this is the black line).
In a random search, any unexamined solution could be tested
next; in a greedy search, we would use the current optimal
solution (the one at the far left) as our basis and choose some
unexamined neighbour of it to look at next. If no neighbours
remain, we ‘pop out’ of the local maximum and look along thenext-best path. But we can also use the mashability scores as
the relative probability of choosing each solution as a basis.
Simulated annealing does this by letting the relative probabilmax), with Mi theity of choosing a basis i be pi = exp( Mi −Mtmashability of the basis, Mmax the greatest mashability foundso far, and t be the ‘temperature’ which cools from 1 to 0. As
t → 0, the pi → 0 if Mi < Mmax . The plot shows us theprobability curves for evenly spaced values of t starting at 1(red) and ending at 0 (blue).
4.1.4 Local sampling
Earlier we noted that for every choice of excerpts, there are8!/2 = 20160 possible arrangements to consider. However, itturns out that these arrangements might vary little in terms ofmashability. Figure 5 plots the maximum mashability foundin an exhaustive search of grid arrangements compared to theaverage mashability found in a random set of 50 arrangements.
The close correlation suggests that sampling a few solutions
for each choice of excerpts may be more efficient than exhaustive local search.

Relative likelihood

The CrossSong Puzzle
1
0.8
0.6
0.4
0.2
0
0

20

40

60

80

100

Fig. 4. In black: relative mashability (y-axis) of typical set of 100
solutions, sorted by rank (x-axis). In colour: relative likelihood (yaxis) of continuing search from a given ranked solution, for various
time steps from beginning (red) to end (blue) of allotted time.

Maximum mashability

1
0.8
0.6
0.4
0.2
0.2

0.4

0.6

0.8

1

Mashability of sample
Fig. 5. Maximum mashability of all 20160 grid arrangements (yaxis) vs. best mashability in a random sub-sample of 50 arrangements(x-axis). Data obtained from 100 random choices of song excerpts
for each of 20 random sets of songs (mashability normalised tomaximum discovered in each set). The strong correlation indicatesthat exhaustive local search may not be necessary.

4.2 Runtime experimentHigh-dimensional search spaces can be complex, and there
is no certainty that any search heuristic will be successful.
We tested the effectiveness of our proposed search optimisations in a runtime experiment. We used a full-factorial design
with the following settings: (1) checklist size: i.e. how many
arrangements to test for each choice of excerpts (50, or thefull 20160); (2) search style: random, greedy or simulated
annealing; (3) whether to use the structural analysis (withk = 8) or none at all; and (4) runtime, which we set as eithera rush job (10 s) or potential background job (3 min).
For each setting, we ran trials on eight combinations ofsongs from the RWC Music Database (Music Genre, Goto,
Hashiguchi, Nishimura, & Oka, 2003). Because mashability(which has arbitrary units) strongly depended on the combination of songs—for one set, the maximum value was 29, foranother, 50—we have re-scaled the values by the maximum
and minimum discovered values for each set. The results ofthe experiment are shown in Figure 6.
Naturally, the longer the runtime, the better the results.
All of the other factors were also found to have a significant effect on the mashability of the best grid. Moreover, wefound a strong interaction between all factors and the available
runtime.

219

First, we found that structural analysis was not helpful tothe search process. The analysis shrinks the search space, but,
disappointingly, seems to do so at the cost of good solutions.
The difference was minor for short searches, but quite large
for long searches.
On the other hand, we found that the other two heuristics
both led to gains—but only during short searches. In a short
search, greedy was better than random, and simulated annealing better still. However, in a long search, greedy outperformed annealing (and both were much better than random).
Perhaps this is because the greedy approach, over a long time,is actually able to exhaustively search local maxima and begin
searching for others.
Lastly, the local search strategy was very important in short
searches. By sampling instead of using exhaustive local search,
the algorithm could test more excerpt combinations. However,in a long search where the algorithm had more time to findthe good combinations, the exhaustive local search could findthe best solutions of all. Also, a simple refinement of thealgorithm—to use the small checklist size, and at the end of
the allotted time perform an exhaustive grid search on the best
grid so far—would give the best of both strategies.
While the annealing and local sampling search heuristics
will be useful strategies for time-limited applications, likewhen making a puzzle out of a user’s music, more straightforward, exhaustive approaches would be best for generating
puzzles offline.
In future search systems, we may wish to consider different
combinations of songs, since, as stated earlier, this had a big
impact on mashability. Considering the choice of songs would
exponentially increase the size of the search space. However,based on our experiment, we would expect the local sampling
and greedy heuristic to speed this considerably.

5. Design development
A puzzle creator has two contradictory goals: first, to confront
the solver with a problem that is difficult to solve; and second,
to ensure that the solver is eventually successful (Gottlieb,
1998). Hence, our first goal was to iteratively develop our puzzle design until we felt it struck the correct balance between
posing no challenge and posing an insurmountable one. In
the process, we also kept in mind two design criteria that aresupported by the popular concept of ‘flow’ (Csikszentmihalyi,1990), which seeks to explain why certain activities are moreengaging than others. Namely, we felt that the player’s goals
should be clear and manageable, and that feedback should befrequent and useful.
In this section, we describe the sequence of puzzle designs
we developed, including the pros and cons of each. The assessments at this early stage of development are based on
the authors’ own experience in testing versions of the game,as well as those of colleagues we recruited to test it. Since
having fresh eyes is essential to effective playtesting, we had
new colleagues test each iteration. A more formal evaluationof the game is discussed in Section 6.

220

Jordan B.L. Smith et al.

(b) Annealing Type(c) Local search
1

0.8

0.8

0.8

0.6
0.4
0.2

Grid quality

1

Grid quality

Grid quality(a) Structural Analysis
1

0.6
0.4
0.2

0
Y

N

Y

0.4
0.2

0
N

0.6

0
R

G

A

R

G

A

All

50

All

50

Fig. 6. Boxplot of mashability of grids (scaled to global maximum found) in a 10-second search (left half of each plot) or 3-minute search (righthalf). The three plots compare: (a) structural analysis not applied (N) vs. applied with k = 8 (Y); (b) random, greedy or annealing search; (c)local search strategy: exhaustive local search of all 20160 solutions vs. a brief search of 50 solutions.

Our iterations primarily affected three aspects of the puzzle:
first, the balance of visual and auditory hints given; second, theway that the puzzle confirmed the progress of the solver; andthird, how the listener’s familiarity with the musical excerpts
was handled.
5.1 Version 1: Initial prototype
Our initial prototype worked as described in Section 3. All of
the basic gameplay elements of this version—the swapping oftiles, the control of row and column playback and the fadingaudio hint based on row correctness illustrated in Figure 3—
were retained in future versions. However, there was a slightdifference: only the top-left-most tile was fixed.
The puzzle was enjoyable to work on, but it was only
solvable by those who knew the music beforehand. None ofthose who tested this version without knowing any of themusic solved it; one user even spent 10 min without being
certain of the relative position of any tiles, and was very
discouraged.
We concluded that more fixed tiles would be needed togive players a decent starting point. Moreover, at least one ofthese tiles would need to be off the main diagonal: we had
not yet realised that the transpose arrangement of tiles was
logically sound but not recognised by the system as correct,
nor reinforced by the audio hints. This meant that if users reassembled the first ‘across’ song, but arranged the tiles in thecolumn instead, they would get no confirmation—auditory orotherwise—that they had done the right thing.
5.2 Version 2: Adding hints
Our second version added two more fixed tiles to get started
in the upper-left corner. This meant that solvers had an ‘in’
to start the puzzle: i.e. there was a place where solvers could
easily make progress, even if they were unfamiliar with themusic or how the puzzle worked. Feeling that this was not
sufficient to make the puzzle feasible, we also added strong
visual hints to support the audio: the relative correctness ofevery tile was shown by displaying icons at the boundary withthe correct neighbour (these are the hearts seen in Figure 7(a)).

Unfortunately, the visual hints made progress too rapid:
once a few tiles had been placed in the correct order, therest of the puzzle could easily be solved visually by checking
different configurations through trial and error. Although we
agreed that some visual confirmation of one’s progress wasneeded, this version took the focus of the logic away from theaudio, defeating the intent of the puzzle. The ideal visual hint
would reinforce the auditory hint without immediately adding
any new information.
5.3 Version 3: Refining visual hints
Our solution was to animate the background of the currently
playing tile: we added a textured background that flows in the
direction of the arrow in Figure 3(b). For example, if no neighbours are correct, the background flows in a south-easterly
direction; if both horizontal neighbours are correct duringhorizontal playback, the background flows eastward. Thus,
the solver gets a visual confirmation of the relative correctnessof the tile, but without extra clues about which neighbouring
tiles are correct. Also, the visual clue is only available while
the solver listens to the tile, so solving it visually is too slow
to be effective. Although it is still technically possible to solve
it using only visual hints, the necessary brute-force method isslow and tedious.
Those testing this version reported that the puzzle was still
too difficult, for two reasons. First, mentally keeping track of
the tiles was taxing, and it was easy to undo one’s progress:for example, one might sort several similar tiles into a single
row, but then forget which row it is, or accidentally swap atile away and lose track of it. Second, the puzzle was still
very difficult for first-time listeners; many of the mash-ups
blended well enough that it was hard to tell which parts of atile belonged to which song!
5.4 Version 4: Improving usability
We next added two features to make the game more userfriendly. First, following the example of Hansen et al. (2013),
we added a welcome screen (see 7(b)) where solvers were

The CrossSong Puzzle

221(a) Visual hints added to Version 2(b) Welcome screen, added to Version 4

Fig. 8. Depiction of a typical gameplay sequence. In the top part, theaudio cues help the user identify which tiles arranged incorrectly. In
the middle part, the user listens to the new arrangement. The bottom
part shows the visual feedback provided to the user.

(c) Row confirmation screen, added to Version 4
Fig. 7. Screenshots of development versions of CrossSong.

allowed to listen to each of the eight excerpts separately before
solving the puzzle—just like jigsaw puzzle solvers can lookat the picture on the box first.
Second, we added a row-confirmation feature (Figure 7(c)).
If all the tiles in a single row or column are placed in theircorrect position, a congratulatory message appears, and thetiles become fixed in place—but only after that full row (orcolumn) is played. This way, randomly shuffling tiles is still afruitless approach. Fixing the tiles in place prevents undoing
one’s work but also serves as an encouraging confirmation ofpartial progress, which is a feature of many engaging puzzles.
A typical sequence of gameplay steps leading up to this row
confirmation event is depicted in Figure 8.

This version of the puzzle, we felt, was fun to play and had
most of the qualities we sought: it combined a need for careful
listening with logical deduction, and although supported by visual hints, the visual hints did not dominate the puzzle-solving
experience. The puzzle also sets up a series of goals (the row
and column confirmations) that are achievable whether one
is playing with one’s favourite songs, or someone else’s. The
game is available to play online.12
5.5 Version 5: Controlling difficulty
Although most testing issues were evident after a few testruns, some only became apparent over multiple trials. Overall,
we had the impression that the game was too hard, and possibly
too fast-paced.
To reduce difficulty, we tried increasing the unit length of
the tiles. Previously, we had generated puzzles where each
12 https://staff.aist.go.jp/jun.kato/CrossSong/.

222

Jordan B.L. Smith et al.

tile was four beats long. Doubling this to 8, we found thatthe mash-ups in each tile could be understood more clearly.
Over eight beats, with more independent activity from the twosongs, it was easier to parse the components of the mash-up
and recognise the music. Moreover, we found the less chaotic
mash-ups more pleasing to listen to.
We also changed the audio mixing levels of the two mashups. In previous versions, the mixing level (which depends ona tile’s relative correctness—recall Figure 3) progressed from50/50 to 100/0, rendering one song inaudible. We changed
100/0 to 70/30 (and shifted the midpoint accordingly), sothat one song became very quiet but was still perceptible. Although we previously enjoyed the pay-off of hearing perfectlyisolated excerpts in a completed puzzle, the isolation could
make progress more difficult during solving. Being able tofaintly hear the ‘cross-songs’—e.g. hearing parts of the ‘down’songs when playing a row that is entirely correct—was a usefulsolving aid.
Finally, we created a number of different tile layouts. The
variety is enjoyable when playing several levels in succession,and fixing more tiles in place is a simple way to reduce thedifficulty of the game.
5.6 Future versions
Although the puzzle has been conceived as a single-player
game, as an interface it can accommodate alternative modes
of interaction. It is straightforward to use as a multiplayer
game: Figure 9 depicts two players playing cooperatively ona large touch screen device. In this setting, each solver canchoose four songs to include in the diagram. The search algorithm can add an extra constraint to ensure that one player’s
choices appear in the rows, and the other player’s songs in thecolumns; this actually simplifies the search by a few orders ofmagnitude.
The interface is also a rudimentary but engaging remix
device. It is fun to ignore the game goals and use the interface
instead to arrange sounds and control their playback. In thisway, the interface resembles automatic remix engines like
Adventure Machine13 and Girl Talk in a Box.14

Fig. 9. CrossSong Puzzle with two users working cooperatively.

to perform statistical tests, but with 10 participants we can atleast get an indication.
6.1 Procedure
Participants filled out a background questionnaire, completed
a sequence of puzzles, and then an evaluation questionnaire.
The study took about 1 h to complete. Participants completed
the study online (from the privacy of their home or workplace), and were asked to use headphones. The full experiment
sequence was as follows:(1)

Introductory sequence (10 min)(a)(b)

Introduction and overview of study
Preliminary questionnaire (musical sophistication,
genre preference, game preference)(c) Tutorial video(2)

CrossSong puzzles (35 min)(a) Tutorial sequence
(i)
(ii)
(iii)

(b)

6. Evaluation
Having arrived at a game design that satisfied us in playtesting,
we evaluated it in a controlled trial with 10 participants. One
goal of the evaluation is to assess the usability of the system,and to uncover any remaining issues with the design. For
usability studies, 5 participants is often regarded as sufficient(Greenberg & Buxton, 2008). However, another goal of theevaluation is to discern whether playing the game has any
impact on players, such as stoking an interest in the music
used by the puzzle, or in mash-ups generally. To answer thesequestions definitively, a larger sample size would be needed

2 × 2 puzzle
3 × 3 puzzle
4 × 4 puzzle with one row or column left tosolve

CrossSong puzzles
(i)

(ii)

Sequence A:
Puzzle X: 4 × 4 using music from the RWC
Music
Database(PopularMusic,
Goto, Hashiguchi, Nishimura, & Oka, 2002).
Puzzle Y: 4 × 4 using music from the RWCMusic Database (Jazz Music, Goto et al., 2002)
and Western pop music.
Sequence B:
Puzzle Z: 4 × 4 using Western pop, indie andelectronic music
Puzzle X: same as above.

13 http://www.madeon.fr/adventuremachine.
14 http://static.echonest.com/girltalkinabox/.

(3)

Evaluation survey (15 min)The CrossSong Puzzle
For each participant, the background survey assessed: theirmusical sophistication, using the standard Goldsmiths MSI
short test (Müllensiefen, Gingras, Musil, & Stewart, 2014);
their preference for different musical genres, with a set ofquestions modelled on the Short Test of Musical Preference(Rentfrow & Gosling, 2003), but adapted for a Japanese audience; and their preference for various types of games, including rhythm video games, puzzle video games, logic puzzles
and crossword puzzles. We used version 1.0 of the self-report
MSI questionnaire, abridged to only those 18 questions thatload onto the ‘General Sophistication’ factor.
From our experience introducing the puzzle to others (reported in the previous section), we knew that the game was
not self-explanatory: players needed at least some explanationof the game mechanics. During the development of the game,
this had been explained to playtesters in person, but for ourevaluation, we needed a succinct script that could be consistent
between participants and available online. We thus createda two-minute video that explained the goal and the main
mechanics of the puzzle, i.e. the controls, the way that correctrows lock in place, and the hints at partial progress provided
by the background. Believing that simpler versions of the
puzzle would allow new players to absorb the game mechanics
without feeling overwhelmed, we also crafted a short tutorial
sequence (see Figure 10). It begins with simple 2×2 and 3×3
versions of the puzzle; the 2 × 2 is usually solved with one
move, but introduces players to the sound of the game and thecontrols. For the 3×3, we explain the most basic sound-based
solving strategy, which is to pick a nearly completed row,
‘focus on its sound, and then search for the missing tile in therest of the grid.’Then, in a 4×4 puzzle which has all the tiles in
the correct place except for one row, we explain the usefulnessof the visual cues: by playing the columns, the correctness ofany tile can be immediately deduced from the background.
The final step was a follow-up questionnaire of 20 questions that addressed the goals of the evaluation. The questions
assessed: if they liked the game (2 questions); if the difficulty
was appropriate (2 questions); if the tutorial exercises were
useful (2 questions); if the music was enjoyable (3 questions);
which was more important among the audio and visual hints,
or whether pure luck dominated (3 questions); if the interface
was user-friendly (4 questions); and if the game had an impact
on the user (4 questions). Several questions were borrowed
from the widely-used System Usability Scale (Brooke, 1996),
and the other questions were written in a similar style. The
questions are listed in Table 1.
The study was conducted in Japan, so the questionnaires,
instructions, tutorial video, and so forth were all presented inJapanese. Only the basic messages within the game (e.g. the‘congratulations’ message, the ‘play’ button and the welcome
screen) were left in English. However, the participants wereskilled enough in English that this did not pose a problem.
The Japanese translations of the Goldsmiths MSI questions
will be made available for other researchers online. They weretranslated by the 2nd and 3rd authors, who are both fluent inJapanese and English.

223

6.2 Participants
Of the 10 participants, 2 were female and the median age was
30 years old, with a range from 19–34. On the 18-question
Goldsmiths MSI questionnaire, the median score was 72, whichcoincidentally is the exact midpoint of the scale—although itcorresponds to the 32nd percentile compared to the general
population (Müllensiefen, Gingras, Stewart, & Musil, 2013).
The scores fell in the range 43–100, or between the 4th and79th percentile.
The participants also rated on a seven-point Likert scale
how much they enjoyed various genres of music and types ofpuzzles and games. All but one of the 10 participants indicatedthat they at least ‘somewhat liked’ J-Pop music, Seven of
the 12 genres we asked about were popular genres; when
pooling all the popular genres, the average rating from every
participant was greater than 4. Preference for puzzles andgames was less unanimous: out of 10 participants, 7 gave
average Likert ratings above 4, but within this group of people
who enjoyed puzzles, average ratings fell between 5.75 and
6.75.
6.3 Results
The average user responses for the evaluation questionnaire
are shown in Figure 11. The responses for related questions
have been grouped together. The results indicate that the puzzles were enjoyed by most participants (liking), and that all
participants found the interface to be intuitive and easy to use(interface quality). Also, most players agreed that listening
closely was the most important skill, although the visual hints
were also needed (see Q10 and Q11 in Table 1). Thus our main
design goals seemed to be successfully achieved.
Responses were more mixed on the questions of feasibility
and tutorial usefulness. Four of the participants agreed thatthe puzzles were too hard, and only four participants reported
never feeling lost or discouraged. While players being lost is
not necessarily a bug for a puzzle game—we want to challenge
the players—we do not want to discourage them. On theother hand, six participants felt that the tutorial exercises wereboring or not necessary. This was interesting to hear, because
we were quite certain, based on our informal tests, that the
tutorials were essential to the puzzle’s feasibility: during theprototyping stage, before we introduced the video and tutorial,
new solvers were usually unable to make any progress in the
4 × 4 puzzles—much less solve them in 10 min or less—without some assistance. In fact, this evaluation was the firsttest in which all participants were able to complete all the
puzzles without supervision, and in the expected amount oftime.
Participants also seemed to find the music enjoyable. Beyond this, we hoped that listening carefully to the short excerpts might inspire in the participants a desire to hear the
rest of the songs (future engagement), but the results here are
mixed. However, nearly all participants agreed that they would
like to play the game again with music of their choosing (Q19
in Table 1),

224

Jordan B.L. Smith et al.
Tutorial puzzles:

Main puzzles:

Fig. 10. Screenshots of opening layouts for sequence of tutorial puzzles.

Fig. 11. Distribution of survey responses, grouped by factor. Likert scale answers (1–7) normalised to (−1, 1). Numbers in brackets indicate
the questions included in the factor; see Table 1 for questions and detailed responses. (Responses to negatively phrased questions were inverted
before being grouped in this summary figure.)

We anticipated that the experience of the participants might
depend on their musical sophistication, or their stated enjoyment of pop music or games and puzzles. There were too few
responses to apply statistical tests, but in any case we did notobserve any hint of a relationship between the participants’
background and any of the evaluation factors. The only exception was an apparently strong correlation between how
much participants reported enjoying games and how muchthey enjoyed this one (Figure 12). This may have been due

to the outlier on question #1—the person who did not enjoy
CrossSong—also happening to be the person who reported
the lowest enjoyment of games.
We also solicited written feedback from participants. They
made several suggestions for improvements to the game: somelonged for a more ‘complete’ interface to enhance the user
experience, such as indicating a player’s ‘score’, or otherwise
tracking their progress. The number of tile swaps made and thetime elapsed could be used to generate a player’s score (withThe CrossSong Puzzle

Fig. 12. Scatter plot of reported liking of games generally (onbackground survey) and reported liking of CrossSong.

smaller values of each giving higher scores). Others pointed
out shortcomings of the interface that would be simple to fix,
like the hard-to-find ‘pause’ button (users had to scroll down
to reach it), or the way users are instructed to listen to thefull excerpts first, which can be time-consuming. Although
this was optional, the experiment setting implied that it was
mandatory.
But overall, their comments indicated that users considered
the game to be a very interesting idea. One user praised the
pay-off of the un-mixing: he did not notice which songs wereused when mashed up, and felt it was very interesting when,
upon solving, the reconstructed song would get prominent
focus.
Encouragingly, novice users without extensive knowledgeof music wrote that they enjoyed the game and felt confident
playing it. Recall that musical sophistication was not found tocorrelate with any of a player’s survey answers. Some players
reported listening to the music more carefully than they had
before, and the phrases they used in their comments—focusing
on the ‘components of the songs’, or noticing the ‘typicalsound of musical instruments’—suggests that CrossSong may
be an interesting way to get musical novices to think aboutmusic more critically.

225

music. On the other hand, a puzzle needs some kindof visual component for the user to interact with, so a
display is necessary to let the solver confirm or track
their progress. However, if all information relevant to
the puzzle is displayed visually, this defeats the intent tomake a listening-based puzzle. Thus the main challenge
in designing a puzzle to engage musical thinking may
be to figure out how to introduce visual hints while
confining them to a supporting role. The key to this balance in CrossSong was to make the visual hint (i.e. thebackground animation direction) available only while
the music was being played. This kept the gameplay
focus on listening to the music, but allowed solvers tomake some progress even when they were otherwise
lost.
(2) Using multiple mechanics to modulate difficulty.
It must be possible to vary the difficulty of the puzzles:
simpler puzzles are needed to show a new player theropes, and more difficult puzzles are needed to maintaintheir interest. Many factors affect puzzle difficulty, but
not all of them can be controlled. Some factors are baked
into the design, and changing them would affect difficulty too drastically: these include the balance of visualand auditory hints, and the way that correct rows lock
into place. Some factors depend on the user, including
their familiarity with the music and their listening skills.
Thus, it is important that the puzzle design accommodate at least a few parameters that can be easily tweaked
to control difficulty: in the case of CrossSong, changing
the size of the grid and the arrangement of fixed tiles
are two ways to control difficulty predictably.
(3) Designing levels automatically.
If users are able to choose what music to use in a puzzle,
this gives them another way to control the difficulty of
puzzles. The potential to play CrossSong with musicof one’s choosing was part of the game’s appeal, andparticipants in the evaluation agreed. But user-selectedmusic demands procedurally generated puzzles. That
is: automatic level design is a requirement. In the caseof CrossSong, the ability to generate levels depended
on an efficient search algorithm that we applied to existing mashability estimation techniques. Without thisinfrastructure, we would not have been able to rapidly
develop the prototype, nor produce puzzles tailored tothe users.

7. Discussion
In Section 1, we noted a challenge to designing an effective
musical puzzle: the fact that music happens in time, whereas
puzzles can be solved at an arbitrary pace. Reflecting on theevolution of the design after multiple rounds of playtesting andredesign, we realise now that the success of a music puzzle
hinges on many more issues, including these three points:(1)

Balancing visual and auditory hints.
The goal of a music-based puzzle should be to challengea solver’s ability to listen carefully and to think about

Eran Egozy, co-founder of Harmonix (the company thatcreated the music games Guitar Hero, Rock Band, Fantasia:
Music Evolved, and others) has written that throughout his
career, he has often held the same goal in mind: to engage players while allowing them to be musically expressive (Egozy,2016). However, it took almost 20 years of developing games
for him to judge that he had come close to realising that.
Above, we offered the design lessons we learned in the courseof developing and testing CrossSong, which we believe areapplicable to any music-based puzzle. However, ours remains

5.2
5.5
4.3
4.4
6.3
1.9
5.7
1.8
4.1
3.7
5.0
4.3

(11) (–) I mainly solved the puzzles by focusing on the background animation hints.

(12) Completing a CrossSong puzzle depends mainly on skill, not on luck.

(13) The interface was easy to use.

(14) (–) I found the interface to be very complex.

(15) I felt confident using the interface.

(16) (–) I needed to learn a lot of things before I could get going with CrossSong.

(17) About the songs in the game I had never heard before: after playing the game, I would like to hear the rest of these songs.

(18) About the songs I had heard before: after playing the game, I would like to hear these songs again.

(19) I would like to play the game with music of my choosing.

(20) I would like to hear more mash-ups.

2.5(8) (–) I did not enjoy listening to the music while playing.

(10) I mainly solved the puzzles by listening closely to the music.

4.9(7) The combination of sounds in the mash-ups was often interesting.

(9) I liked the music that was used in the puzzles.

4.2

3.7

(4) (–) At some point while solving, I felt lost or discouraged.
3.7

4.6

(3) I would like to play the game again.

(6) (–) I would have been able to solve the puzzles without doing the exercises first.

4.0(5) (–) Solving the exercises was boring.

5.6(2) (–) The puzzles were too hard.

Average
response(1) Playing CrossSong was fun.

Question

1.73

1.95

1.90

2.07

0.75

1.10

0.83

0.78

1.43

1.73

1.75

1.60

1.63

1.45

1.90

1.66

1.42

1.43

1.61

1.36

Standard
deviation

30%

80%

30%

50%

100%

80%

90%

100%

50%

30%

70%

70%

80%

50%

50%

40%

40%

50%

40%

90%

% Favorable
responses

Table 1. Raw average and standard deviation of survey responses for each question. The neutral midpoint of the seven-point Likert scale was 4; percent favourable responses thus gives thefraction of responses strictly greater than 4, or, for questions phrased negatively and marked with a ‘–’, strictly less than 4.

226
Jordan B.L. Smith et al.

The CrossSong Puzzle
a first effort at creating a real-time music puzzle, and we anticipate new insights will come with developing more designs.

8. Conclusion and future work
We have proposed a novel type of puzzle, the CrossSong,
which aims to combine the pattern-learning and pattern-seeking
joys of music and puzzles. We have developed an algorithm
for generating puzzles from music provided by a user, and aninterface for solving them. The software allows (and solving
the puzzle requires) the user to explore and to analyze a set oforiginal mash-ups in real time as they are played. As we iteratively refined the design, we realised that the main challenge
was to balance game mechanics that encourage the player tolisten carefully to the music, with visual aids that can confirm
the player’s progress and make the task more feasible.
Participants in a small evaluation, regardless of their musical expertise, seemed to enjoy the game and expressed interest in playing it again with music of their choosing. To
prolong interest in the game even further, we would like todemand different modes of musical thinking from solvers
by varying the solving mechanics. As we indicated in thetutorial, certain listening strategies are more efficient in certain
layouts, so to some extent, this variety can be achieved bymanipulating parameters like the size and shape of the grid,
the arrangement of fixed tiles and the duration of the tiles.
But since the interface is so flexible, many more variations
could be imagined. For example, the way the mixing works(cf. Figure 3) could be inverted: each tile could become more
instead of less mixed as its neighbours became more correct.
This version might become harder as the game progresses
instead of easier. Another possibility is to treat the excerpts
with harmonic-percussive source separation, and manipulate
the mixing of these components to focus solvers’ attention onrhythmic or harmonic aspects of the music. Creating, testingand evaluating new game mechanics is the future work weplan to pursue.

Acknowledgements
We would like to thank Matthew Davies for his original implementation of AutoMashUpper Davies et al. (2014).

Funding
This work was supported in part by OngaCREST, CREST, JST;
Core Research for Evolutional Science and Technology.

ORCID
Jordan B.L. Smith
http://orcid.org/0000-0002-0316-1235
http://orcid.org/0000-0003-4832-8024
Jun Kato
http://orcid.org/0000-0001-6506-2796
Satoru Fukayama
http://orcid.org/0000-0003-1167-0977
Masataka Goto

227

References
Brooke, J. (1996). SUS: A ‘quick and dirty’ usability scale.
In P. W. Jordan, B. Thomas, B. A. Weerdmeester, & I. L.
McClelland (Eds.), Usability Evaluation in Industry (pp. 189–
194). London, UK: Taylor and Francis.
Cannam, C. (2012). Rubber band library. Software released under
GNU General Public License (version 1.8.1).
Ciconia, J. (1993). De Proportionibus. In O. B. Ellsworth (Ed.).
Lincoln, NE: University of Nebraska Press.
Crute, T. D. (2010). Effective use of games and puzzles in thechemistry classroom. In Making chemistry relevant: Strategies
for including all students in a learner-sensitive classroom
environment (pp. 267–281). Hoboken, NJ: John Wiley & Sons
Inc.
Csikszentmihalyi, M. (1990). Flow: The psychology of optimal
experience. New York, NY, USA: Harper and Row.
Davies, M. E. P., Hamel, P., Yoshii, K., & Goto, M. (2014).
AutoMashUpper: Automatic creation of multi-song music
mashups. IEEE Transactions on Audio, Speech, and Language
Processing, 22, 1726–1737.
Dubus, G., Hansen, K. F., & Bresin, R. (2012). An overview
of sound and music applications for Android available on
the market. Proceedings of the Sound and Music Computing
Conference (pp. 541–546), Copenhagen, Denmark.
Egozy, E. (2016). Approaches to musical expression in
Harmonix video games. In J. B. L. Smith, E. Chew, & G.
Assayag (Eds.), Mathemusical Conversations: Mathematics
and Computation in Music Performance and Composition(pp. 20–36). Singapore: Imperial College Press and World
Scientific.
Engel, J., Holzer, M., Ruepp, O., & Sehnke, F. (2012).
On computer integrated rationalized crossword puzzle
manufacturing. In E. Kranakis, D. Krizanc, & F. Luccio (Eds.),
Proceedings of the International Conference on Fun with
Algorithms (pp. 131–141). Berlin, Heidelberg: Springer, Berlin
Heidelberg.
Foote, J. (2000). Automatic audio segmentation using ameasure of audio novelty. Proceedings of the IEEE
International Conference on Multimedia & Expo(pp. 452–455). New York, NY: IEEE.
Ginsberg, M. L., Frank, M., Halpin, M. P., & Torrance,
M. C. (1990). Search lessons learned from crossword
puzzles. Proceedings of the National Conference on Artificial
Intelligence (pp. 210–215). Boston, MA: AAAI Press.
Goto, M., Hashiguchi, H., Nishimura, T., & Oka, R. (2002).
RWC Music Database: Popular, classical, and jazz music
databases. Proceedings of the International Conference onMusic Information Retrieval (pp. 287–288). Paris, France.
Goto, M., Hashiguchi, H., Nishimura, T., & Oka, R. (2003).
RWC Music Database: Music Genre Database and MusicalInstrument Sound Database. Proceedings of the International
Conference on Music Information Retrieval (pp. 229–230).
Baltimore, MD, USA.
Gottlieb, M. L. (1998). Secrets of the MIT Mystery Hunt:An exploration of the theory underlying the construction ofa multi-puzzle contest (Bachelor’s thesis). Cambridge, MA:
Massachusetts Institute of Technology.

228

Jordan B.L. Smith et al.

Greenberg, S., & Buxton, B. (2008). Usability evaluationconsidered harmful (some of the time). Proceedings of the
SIGCHI Conference on Human Factors in Computing Systems(pp. 111–120). Florence, Italy: ACM.
Griffin, G., Kim, Y. E., & Turnbull, D. (2010). Beat-syncmash-coder: A web application for real-time creation ofbeat-synchronous music mashups. Proceedings of the IEEE
International Conference on Acoustics, Speech and Signal
Processing (pp. 437–440), Dallas, TX.
Griffiths, M. (2002). The educational benefits of videogames.
Education and Health, 20, 47–51.
Hainsworth, S. (2006). Beat tracking and musical metre analysis.
In A. Klapuri & M. Davy (Eds.), Signal processing methods formusic transcription (pp. 101–29). New York, NY: Springer.
Hansen, K.F., Hiraga, R., Li, Z., & Wang, H. (2013). Music
puzzle: An audio-based computer game that inspires to train
listening abilities. In Advances in computer entertainment.
Lecture notes in computer science (Vol. 8253, pp. 540–543).
Cham, Switzerland: Springer International Publishing.
Hedges, S. A. (1978). Dice music in the eighteenth century. Music& Letters, 59, 180–187.
Hudson, N. J. (2011). Musical beauty and information
compression: Complex to the ear but simple to the mind? BMC
Research Notes, 4, 9.
Jordan, A., Scheftelowitsch, D., Lahni, J., Hartwecker, J.,
Kuchem, M., Walter-Huber, M., ..., Preuss, M., (2012).
BeatTheBeat: Music-based procedural content generation
in a mobile game. Proceedings of the IEEE Conference
on Computational Intelligence and Games (pp. 320–327).
Granada, Spain.
Krebs, F., Böck, S., & Widmer, G. (2013). Rhythmic patternmodeling for beat and downbeat tracking in musical audio.
Proceedings of the International Society for Music Information
Retrieval Conference (pp. 227–232). Curitiba, Brazil.
Lee, C., Lin, Y., Yao, Z., Lee, F., & Wu, J. (2015). Automatic
mashup creation by considering both vertical and horizontal
mashabilities. Proceedings of the International Society forMusic Information Retrieval Conference (pp. 399–405).
Málaga, Spain.
Lin, Y., Liu, I., Jang, J. R., & Wu, J. (2015). Audio
musical dice game:Auser-preference-aware medley generating
system. ACM Transactions on Multimedia Computing,Communications, and Applications, 11, 52:1–52:24.

Müllensiefen, D., Gingras, B., Musil, J. J., & Stewart, L. (2014).
The musicality of non-musicians: An index for assessing
musical sophistication in the general population. PLoS ONE,
9.
Müllensiefen, D., Gingras, B., Stewart, L., & Musil, J. J. (2013).
Goldsmiths musical sophistication index (gold-MSI) v1.0:
Technical report and documentation [Revision 0.3]. Technicalreport, Goldsmiths. University of London.
Müller, M. (2015). Music structure analysis. Fundamentals ofmusic processing: Audio, analysis, algorithms, applications(pp. 167–236). Cham, Switzerland: Springer International
Publishing.
Nierhaus, G. (2009). Algorithmic Composition: Paradigms ofAutomated Music Generation. Vienna, Austria: SpringerVerlag Wien.
Rentfrow, P. J., & Gosling, S. D. (2003). The do re mi’s of
everyday life: The structure and personality correlates of music
preferences. Journal of Personality and Social Psychology, 84,
1236–1256.
Schmidhuber, J. (2009). Driven by compression progress:
A simple principle explains essential aspects of subjective
beauty, novelty, surprise, interestingness, attention, curiosity,
creativity, art, science, music, jokes. Anticipatory behavior in
adaptive learning systems (pp. 48–76). Berlin: Springer.
Smith, J. B. L., Burgoyne, J. A., Fujinaga, I., De Roure, D.,& Downie, J. S. (2011). Design and creation of a largescale database of structural annotations. Proceedings ofthe International Society for Music Information Retrieval
Conference (pp. 555–560). Miami, FL, USA.
Upham, F., & Farbood, M. (2013). Coordination in musicaltension and liking ratings of scrambled music. Presented at
the Society for Music Perception and Cognition Conference(pp. 148), Toronto, Canada.
Wyse, L., & Subramanian, S. (2013). The viability of the
web browser as a computer music platform. Computer Music
Journal, 37, 10–23.