By James Bubear, Queensland University of Technology
A Sudoku is a puzzle that most of us will be familiar with having become a staple of most newspapers over the last decade. What many of you may not know is that they are special case of a combinatorial mathematical object called a Latin Square. This intrinsic link between puzzles and games with mathematics is most likely where my personal interest and love of mathematics came from.
Latin Squares are basically a Sudoku without the 3×3 sub square restriction. Which is to say, in a Latin Squares each number needs to appear once and only once in each row and each column.
Latin Squares have been researched for much longer much longer than people have been playing Sudoku. Having been reported to have described as early as 1725 and have thus been used in real worlds applications several applications. One of these applications is in Error Correcting Codes(ECCs). ECCs allow us to send messages where even if we lose some of the message or if it gets changed we are still able to read the original message. They are used in almost all modern forms of communication and in particular Latin Square ECCs are used in broadband internet so it may be thanks to Latin Squares that you can read this article!
I love puzzles but another hobby of mine that I would like to talk about is video games and there is some interesting maths going on there.
Procedural generation is a technique where you generate the next result you need based on the last result you got. One of its more common applications is in Pseudo-random number generation — which is basically how computers roll dice. The algorithms for Procedural generation normally work in these basic steps.
- You give the algorithm a seed to start with. This is an initial value you put into the algorithm so it can run for the first time.
- The algorithm spits out number.
- You can then use for whatever you need.
- Then you pass that number back to algorithm and go back to step 2.
You can do this for as long as you need to get numbers. The algorithms are normally designed so that you will get results with the same distribution and frequency as if you were to actually roll a dice or whatever action you were trying to simulate.
These techniques have been used in video game for a while now one of the more well-known games is Minecraft that uses Procedural generation to generate the world you play in. A game that is set to come out this year which I am particularly excited by is called No Man’s Sky. It is a space exploration game where it is estimated that the galaxy you will be to explore will contain over 18 quintillion planets(US) planets players will be able to explore! That’s 18 000 000 000 000 000 000 and that it would take a single player 5 billion years to do so! The sere scale of this game is mind-boggling and the ability to create this galaxy is largely thanks to the relatively simple technique of Procedural generation.
James Bubear was one of the recipients of a 2015/16 AMSI Vacation Research Scholarship.