Enter the maze

Sudoko in satellite communication

A hacked teapot on a tablecloth

How can satellites use Sudoku puzzles to communicate in a way that extracts twice as much information as was apparently sent? Soren Riis of Queen Mary, University of London explains.

Imagine two ground stations belonging to Jo and Kim that communicate via a satellite. Jo wants to send some information to Kim – just a bit (either a 0 or a 1) and Kim wants to send a bit (0 or 1) back to Jo. The obvious way to do this is for the satellite to get the two bits in turn and then beam them back to earth one at a time. That seems obvious but is it wasteful? Could the satellite do its job by only sending a single bit back in a way that both Jo and Kim get the information the other sent? That just sounds impossible! Surely there is no way they can both extract the possibly different pieces of information meant for them from a single bit! It would mean extracting more information from the message than was actually sent!

Impossible? Can you work out a way to do it?

Hint: There are 4 cases. Let’s call Jo’s bit of information j and Kim’s k. We can list the possibilities:

Case 1: j is 0 and k is 0,
Case 2 : j is 0 and k is 1,
Case 3 : j is 1 and k is 0,
Case 4 : j is 1 and k is 1.

For each of the 4 cases the satellite will transmit either a 0 or 1: you need to work out a bit that can be sent that will allow Kim to work out what k is and Jo to work out what j is in each case. Try to find the ways to fill in the 4 empty cells in the table that solves the problem. Have a go before you read on.

k is 0 k is 1
j is 0
j is 1

The problem is actually very simple. What you need to do is place the bits 0 and 1 in the four cells in a way so that each column and row in the table contains different bits. For example, one solution is

Case 1: j is 0 and k is 0. Send 0.
Case 2 : j is 0 and k is 1, Send 1.
Case 3 : j is 1 and k is 0, Send 0.
Case 4 : j is 1 and k is 1. Send 1.

But how does this help? How does it get round the problem of needing to extract more information than was sent? The trick is that both Jo and Kim have more information than just the bit they receive. They know what they sent too! They can use that together with whatever the satellite sends them to work out what the unknown bit that the other was sending is. Essentially the satellite is using a code where in this case 0 means “the bits I was given are different” and 1 means “the bits I was given are the same”.

So far so good, but we don’t want to just send bits of information. Suppose we are sending a text message. It’s made of lots of letters not just a 1 or a 0. Computers store letters in what is know as hexadecimal. It’s just another code where everything is translated into pairs of the 16 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. For example, the letter ‘a’ is 61, ‘b’ is 62 and so on up to ‘z’ which is 7A.

Go to String To Hex where there is a program that does the translation for you. Check for example that “hallo” translates into the hexadecimal 68 61 6c 6c 6f and that “Queen” translate into 51 75 65 65 6e. Of course you can apply the code backwards to get to the original message. Go back to String To Hex to check that 68 61 6c 6c 6f does actually translate back to “hallo” and that 51 75 65 65 6e becomes “Queen”.

So suppose now that Jo and Kim are both beaming a sequence of hexadecimal numbers to the satellite. We can play the same trick on each digit to reduce the amount of data the satellite sends. As there are now 16 different digits Jo and Kim could be sending instead of 2, we just need to fill in a 16 x 16 table rather than a 2 by 2 one to work out what the satellite should transmit. We need to put a hexadecimal number in each square so that every column and every row contain different numbers. Mathematicians call this kind of table a Latin square. Find a way to do that and you have your code to send hexadecimal messages efficiently from the satellite. As with the binary version, you work out the message sent to you by looking up the message you sent and the message received in the table giving the code being used. Can you work out exactly how this 16x16 table would be used to transmit and decode hexadecimal characters? Try it then read on.

A large sudoku grid

In case you haven’t already noticed, this is where sudoku comes in. Ordinary sudoku is a 9x9 grid where every row and column (and in fact the 3x3 grids too) are different. Hex sudoku is the same but with a 16x16 grid. One (roundabout) way to get a Latin square for sending hexadecimal is to use a solved 16 x 16 sudoko!

Take the 16x16 sudoku solution given in the diagram. We can work out the hexadecimal message transmitted by the satellite as follows. Suppose j is the hexadecimal number 8 and k is the hexadecimal number, f. We find the row that has 8 as its first entry and the column that has f as its top entry. The satellite then beams back the hexadecimal in the square common to that row and column. In the case it is ‘a’.

To decode the number you just do a variation of the above. Kim knows she sent ‘f’, so just as the satellite did starts by finding the column in the Sudoku table headed by f. She then looks down that column until she finds the hexadecimal number the satellite sent (‘a’). The hexadecimal Jo sent her is then just the first entry in that row – ‘8’.

Now lets go for a whole message exchange. Suppose Jo is sending the message “hallo” and Kim is sending the message “Queen”. We can use the 16x16 Sudoku and work out the message sent by the satellite. First the messages are translated into hexadecimal digits.

Jo sends “hallo” which is 68 61 6c 6c 6f

Kim sends “Queen” which is 51 75 65 65 6e

What 10 hexadecimal digits does the satellite beam back to earth? From the table we can work it out: 0b 59 b1 b1 b8

Kim and Jo of course have to do the opposite and decode the message the satellite sends based on what they receive.

Suppose you are Kim and send the world “hallo” (68 61 6c 6c 6f) and the satellite beams back the message 58 5a b8 ba b3 What is the message sent to you by Jo? See if you can work it out using the sudoku grid (the answer is at the end of this article).

So by using solved sudoku grids, satellites can communicate much more efficiently, halving the amount of data they need to transmit for this kind of 2-way communication. Of course the idea can be used elsewhere too. Microsoft have developed a peer-to-peer file sharing system called Avalanche and the maths it uses to communicate can be derived from sudoku squares in a similar way.

When designing ways of coding information to send, different codes give different communication properties. It’s therefore important to design what are called the ‘coding functions’ (read: sudoku squares) in a way that works best for a given application.

So satellites don’t actually waste away their spare time solving sudoku for fun, but they can use solved sudoku to send information without wasting time.

Answer: Jo sent you 74 72 61 69 6e (“train”).