Sciences & Technology
Can you accurately read a graph? It may not be as simple as you think
Can you solve the skeleton puzzle?
‘Minimum obstacle skeletons’ could be used to optimise mass telecommunications and transport networks. But first, we need to solve a puzzle
Published 15 July 2025
This is a square.
Our aim is to stop any straight path from crossing the square.
So we'll build fences. Fences must be straight and cannot go outside the shape.
How many fences do we need to build?
Four fences around the perimeter of the square will work. But can we do it with fewer fences?
Yes. Three will work, like so.
How about two?
Not this way.
But there is a way to do it.
Here's the solution
No paths can get through here.
Can you solve it?
The X-shape is the only solution for a square, but with other shapes, there’s usually more than one way to draw the lines and solve the puzzle.
Can you find the least number of fences needed to stop any straight paths through these shapes (take a screenshot or sketch these shapes to start drawing)
Answers at the end of the article.
How many fences are needed for this ten-sided crown?
A regular hexagon with six sides.
This is also a hexagon, but with an irregular shape.How many fences are needed for this ten-sided crown?A regular hexagon with six sides.This is also a hexagon, but with an irregular shape.1 / 3
A new type of skeleton
You might be wondering if there’s any point to these puzzles, apart from giving your brain a workout.
Well, these puzzles are examples of a new type of mathematical ‘skeleton’ that the inventors – Dr Nicolau Andres-Thio, Associate Professor Marcus Brazil, Associate Professor Charl Ras, Professor Doreen Thomas and Dr Marcus Volz from the University of Melbourne – are calling a ‘minimum obstacle skeleton’.
Here, Associate Professor Charl Ras explains how they came up with an algorithm that can solve the problem for any type of shape and why it can help optimise massive networks like Australia’s National Broadband Network.
Associate Professor Charl Ras, Senior Lecturer, School of Mathematics and Statistics
For certain shapes, finding the skeleton is a fun puzzle that anyone can try.
There is even a neat trick for shapes with corners that all point outwards: the number of skeleton lines is always half the number of edges (rounded up for odd numbers of edges).
However, add in some corners that point inwards and suddenly everything changes. There is no known formula for these shapes.
You can try to find a solution by hand, but for shapes with hundreds or thousands of sides, that might take months.
To overcome this challenge, we set about searching for another way to understand these skeletons.
Most shapes (like the puzzle examples above) have more than one solution. We proved that amongst those solutions there is always one skeleton with a key feature: every skeleton line touches a corner of the shape.
By focusing on these skeletons, we were able to narrow down the necessary types of skeleton lines to just four essential types.
With these new categories, we made an algorithm that can rapidly find a minimum obstacle skeleton for any polygon (shape with straight sides). This new algorithm makes it possible to find minimum obstacle skeletons for huge, complex polygons with thousands of sides.
The 10,000-sided shape above (yes, it’s a single connected shape) was generated by creating a random polygon on a normally distributed set of points, which in itself is an interesting research problem.
Our algorithm then fills in the lines to create the minimum obstacle skeleton.
This ability to construct a skeleton on a polygon of this size in a reasonable time just goes to show the significant effect that insights into the mathematical properties of a structure can have on the efficiency of optimisation algorithms.
Our aim for the new skeletons is to improve software for optimising large-scale networks that connect thousands of locations, like national internet networks, which need to be direct but also avoid numerous obstacles like existing buildings and protected zones.
Representing these obstacles on maps with minimum obstacle skeletons rather than polygons could make tests for obstacle avoidance more efficient, without losing any accuracy.
Our work on large network problems has recently focussed on improving the disaster-resilience of critical communications networks.
Sciences & Technology
Celebrating the “grandmother” of optimisation on International Women in Maths Day
This work is part of a wider project to improve approaches that minimise the length and cost of networks.
It was inspired by an unsolved problem called the laser beam detector problem, which has a reputation amongst mathematicians for being “notoriously difficult”.
The presence of natural and human-made obstacles in large-scale, complex infrastructure networks raises significant challenges and opportunities for engineers, computer scientists and mathematicians in the field of network design.
Our work on skeletons is just the beginning.
Our current goal is to combine this work with our research on the design of minimum length networks to create a powerful unified model for the design of modern infrastructure networks.
This will help make Australia a leader in the ongoing endeavour of creating an interconnected society.
Solution
Did you solve the skeleton problems? Scroll back up to give them a go or scroll down for the answers.
For the ten-sided crown, the solution requires only four fences
For a regular hexagon, the answer is three, but there are two different solutions
For the irregular hexagon, the answer is also three, and now there are three different solutionsFor the ten-sided crown, the solution requires only four fencesFor a regular hexagon, the answer is three, but there are two different solutionsFor the irregular hexagon, the answer is also three, and now there are three different solutions1 / 3