Networks are everywhere in modern society: roads, wires, water and gas pipes all connect one place to another. Computers are built of networks at many levels, from the microscopic connections between transistors in a chip to the cables and satellites that link the internet around the world. People who build networks often need to work out the most efficient way to make connections, which can be a difficult problem.
This puzzle shows students the decisions involved in linking a network between houses in a muddy city. It can lead on to a discussion of minimal spanning tree algorithms for optimizing networks.
Activity description (PDF)
Translations and other Versions:
 Arabic Language Version
 Chinese Language Version
 Italian Language Version
 French Language Version
 Greek Language Version
 Hungarian Language Version
 Portugese (Brazil) Language Version
 Polish Language Version
 Slovenian Language Translation
Related Resources
 An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there’s some extra technical information.
 More lessons and activities:

 As an extension, try the online games from Wiliam Cook to demonstrate the Travelling Salesman Problem(TSP) below:

 nrich Maths has the following activities with notes and solutions provided:
 [Requires registration] Cre8ate Maths UK has a resource called Working for Efficiency that looks at 3 different network problems that are encountered in practical logistical planning. The resource helps in learning how the Prim’s algorithm works in the real world.
Note: You will need to register (free) as a teacher at Cre8ate Maths UK to access this resource

 The Mathmaniacs web site has a similar activity (lesson 13)
 [Requires registration] TES Connect UK contributor numskull has the Minimum Connector Program. Instructions: Create and solve minimum connector problems interactively using the power of Excel. Use for wholeclass work with a projector, or use the practice sheets for individual/small group work at a workstation. The answer is illustrated stepbystep on a matrix, which can also be input by the user if preferred (for the graphical version of the algorithm, simply draw the graph alongside or on a piece of paper). On the practice sheets your answers can also be checked by the program.
Note: Teachers will need to register on TES Connect UK in order to access resources.

 If you want to find out more:

 Wikipedia: Travelling Salesman Problem : Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. Wikipedia: Route Inspection Problem or The Chinese Postman Problem : to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution.

 Mr Barton Maths UK has some short presentations for introducing some concepts below:
 The Student Room UK has the following revision sections:
 Christine Mumford has excellent explanation and demonstration of the Travelling Salesman Algorithm Heuristics: Nearest Neighbour, MultiFragment, Farthest Insertion developed by Howard Plummer

 Additional resources:
 Mordechai (Moti) BenAri from the Weizmann Institute of Science, Israel has programmed The Muddy City Minimal Spanning Trees Unplugged activity in Scratch which can be downloaded in a zip file of the complete set of activities. Please read the ReadMe.txt for documentation.
Curriculum Links
Great Principles of Computer Science [info]
 Computation, Coordination
ACM K12 Curriculum [info]
 Level I (Grades 35) Topic 11: develop a simple understanding of an algorithm
New Zealand Curriculum [info]

 Mathematics Level 1: Position and Orientation
 Give and follow instructions for movement that involve distances, directions, and half or quarter turns
 Mathematics Level 1: Position and Orientation

 Mathematics Level 2: Position and orientation
 Create and use simple maps to show position and direction.
 Mathematics Level 2: Position and orientation
 Technology Level 1: Planning for Practice
 Outline a general plan to support the development of an outcome, identifying appropriate steps and resources