The Maths of Sudoku and Latin Squares

The Gresham College lecture that you're listening to right now is giving you knowledge and insight from one of the world's leading academic experts. Making it takes a lot of time. But because we want to encourage a love of learning, we think it's well worth it. We never make you pay for lectures, although donations are needed. All we ask in return is this. Send a link to this lecture to someone you think would benefit. And if you haven't already, click the follow or subscribe button from wherever you are listening right now. Now let's get back to the lecture. So thank you very much for coming. We are gonna talk about the mathematics behind Sudoku. On the way we're gonna meet a sacred Chinese turtle. Uh, we're gonna visit a bleak Welsh hillside and a Parisian apartment block. We're gonna encounter different kinds of number squares like Latin squares that we'll, we'll meet soon. But let's just begin. Probably everyone in the room knows what a Sudoku is, but just in case, let's establish the ground rules. So a Sudoku grid, this is a completed one. Uh, it's uh, a square of side nine. And it features the numbers one to nine with the following rules. These numbers have to appear exactly once in each row, in each column, and in each of these little three by three blocks. So that's what a completed Sudoku grid looks like. But that's not what we see when we start the puzzle. We see a partially completed grid, something like this. And then our job is to use just the rules that we know to complete fill in the rest of the numbers. Um, you may not have noticed this, but by convention, the squares that are filled are usually, um, symmetrical. They have a rotational symmetry. Um, we do 180 degree rotation. The numbers aren't gonna match, but the squares that are filled have that pattern. And if we are trying to create a Sudoku puzzle, it must be the case that this grid can be completed in exactly one way. So there's a unique solution. There is a solution, and that's got to be unique, only one solution. And it should be obtainable without guesswork. In an ideal world, uh, well <laugh> in an ideal world, so it should be obtainable. Occasionally, one or two of us may, uh, resort to a guesses on occasion. Uh, but let's, let's, let's pretend we never do that. So this is not, by the way, a masterclass on how to solve Sudoku because there's lots of resources about that that you could find. There are books, there are websites. But just to sort of give a basic idea of the sort of thing you might do, um, we filled in a few entries already. So at this point, of course, you are gonna use these rules constantly. So for example, you could say that, look in this row, there's only one number that we haven't got, and there's only one space. So we've got to put a one in that space. There it goes. Now we've got a column that only has one number missing the numbers one to nine must appear exactly once in each row, in each column, in each block. So in this one we can see that there's, what is it, a three missing and we can put that in. And then now look in this central block, we've now arranged things so that there's only one gap there as well. And we can put a six in that gap. So we can proceed like this. We can get slightly more sophisticated. So there's one technique which is very useful, um, which is often called slicing. So imagine cutting your Sudoku into three thick slices, each of which contains three rows, and it also contains three blocks. So you can see I've highlighted the middle slice of my Sudoku cake there. Now that's useful to notice because it means in that slice every number is gonna show up exactly three times, once in each row, once in each each block, but three times in total. So if we look at, say the sixes here, there are two sixes so far in that block. Um, we can eliminate lots of possibilities for where the remaining six, there must be another six where it could go. So it can't go in either of the rows that contain a six. So it's not in that row. It's not in that row. It can't go in either of the blocks that already contain a six. So it's not in the left hand block. It's not in the middle block. And we can see there's only one place it can go 'cause it must go in the top row of the right hand block. And there's only one empty space in that row. So that's great. So we can pop our final six in there. And of course, well, it's slightly unconventional with cake, but you can slice vertically as well and do the same thing with vertical slices of your sudoku. Another option available, which is useful sometimes is even if you can't absolutely pinpoint where uh, numbers go, sometimes you can narrow it down and you can get pairs of numbers that have to go in some order into two spaces. So for instance, if you look at this vertical slice here, look at the nines. Uh, you've got two nines, where's the third one gonna go? It's got to go in the right hand column.'cause the other two columns have a nine and the top block. So there's two vacant cells where it could possibly go. There's nine, we don't know which one it goes in, but there's also threes. And by exactly the same reasoning, um, the other three that is in that vertical slice must go in one of those two uh, squares that are highlighted. Now we don't know which way around they go, but we know that those two squares contain a three and a nine in some order. So no other squares in that little block can contain a three or a nine. So even though we don't know which is which at this point, that can help us with other entries. For instance, in this uh, row up here, there's gotta be a three somewhere. We haven't got one yet, but it can't be in either of those, uh, little empty spaces on the right hand, the end of that row because we know that the three that must be in that block, um, is in the top or the bottom square that we've highlighted. It doesn't matter which one it is for us to deduce, but it's not in that cent middle row there. So we know that the three has to go in, in on the left hand end of this row where I've put it. So these kind of ideas and some others can help you to complete the Sudoku grid. And at each stage you are proceeding using just, you know, pure logic. You're not guessing at any point. Uh, as I've said, lots of resources you can find if you want to, to learn lots more tips and tricks about Sudoku. Uh, if you want to be loyal to Gresham College, you can seek out the book on Sudoku by our former Gresham professor of Geometry, Robin Wilson. Um, but you know, that's, that's, that's my recommendation anyway. But mathematically speaking, what have we done? We haven't actually had to do any arithmetic with the numbers. So if people say correctly that Sudoku is mathematical, it, it sometimes there's a misapprehension that it's mathematical because it's got numbers in it, but that isn't the reason it's mathematical. The reason it's it's mathematical, it's because we're using the structure and we are thinking logically about how to complete the puzzle. And there are also mathematical questions we can ask about, about Sudoku. For example, how many possible complete Sudoku grids are there? Can we count them? Can we work out, classify them? How many puzzles are there? That's slightly different.'cause a puzzle is a partially completed grid, which has a unique solution that can be arrived at without guesswork. So how many of those and can we make those and related, how many clues do we actually need to be able to do this? So if you just put one number into a empty grid, of course you're not going to be able to find a unique solution to that. What's the minimum number you need in order to be able to actually finish that puzzle? It might be very hard, but what's the smallest number you need? But let's begin by saying Sudoku is in the UK at least fairly recent, um, in, you know, geological timescales. The first Sudoku ever in the UK printed in a national newspaper was in November, 2004 in the Times newspaper. So it's fairly recent, um, coming to, to the uk. But you know, there's, we sort of all feel that like Sudoku is this ancient Japanese thing that, you know, imagine the Sudoku master crafting this perfect puzzle on the slopes of Mount Fuji or something like this that is complete nonsense.<laugh>, I mean stand line. This picture I've just made, that's just as a massive lie. Sudoku was invented in America in the 1970s. Uh, it wasn't called Sudoku then. It was called something like number place. And there were these puzzles that were like Sudoku and then they got picked up by a Japanese, uh, puzzle magazine who started printing them, um, about a few years later. And they really took off in Japan and then they made their way to, to the uk and you need back to America. But these puzzles, this kind of number grid is less than 50 years old. And in the grand scale of mathematical ideas, that's very recent, there are much older squares of numbers. And we're gonna go now on a little journey through the history of these, some of these squares of numbers, partly because they'll feed into our thinking about Sudoku. Um, but partly 'cause they're just super interesting already in their own right. And we're going to begin with the oldest kind of number square. And that's the magic square. So this is a picture of um, what's believed to have been the oldest magic square, uh, that we know of. And it's called the low shoe square. So this is a picture from a Tibetan scroll. This is some centuries after the, the square probably originated. Let's put the numbers into modern format. Here they are. And this shows you this is a magic square. So what's a magic square? This time we do need to do some arithmetic with the numbers because a magic square is one where the sum of the numbers in every row, every column and every diagonal is the same. We call it the magic number. So if you pick a row or a column or diagonal vis and everyone picks one, and you should find that the sum of the numbers is 15 always. So this is a magic square. This square, um, is reputed to have originated in the following way. There was a big flood in China and the people were trying to appease the river God by making sacrifices to say, please stop the flooding. Um, and as a sign that their prayers were going to be answered, that God sent a sacred turtle and he crawled out of the river and on his back into his shell was carved this magic square. Okay? So that, that's the origin. It is claimed of this magic square. It's a particular kind of magic square. It features the numbers one to nine. Um, so that, you know, you can have other ones which don't do that. If you start with the first, you know, however many numbers that you need in this case, if it's an order three square, so it's three by three square, then you need to, to fill it, you need the numbers one up to nine. Um, that's called a classical magic square. Okay? But you don't, they don't all have to be classical. So the oldest order, four magic square that we know about, um, is this one. This is not a classical magic square 'cause that would have to contain the numbers one to 16. This doesn't, but it's still a magic square. The sum of the numbers in each row column diagonal, uh, is, is a, is constant. And so this comes from a book, uh, an old Indian book by uh, Rahmi. And its purpose stated in the book was, um, to give you different recipes for making perfume with four ingredients. So here's what you do. You get your four ingredients, A, B, C, and D, and you pick a row column or diagonal. Let's say we pick the first row. And that tells you to use two quantities of ingredient a, three of ingredient B, five of C, eight of D. And the total amount, because it's a magic square, whichever row column or diagonal you pick the total volume of the perfume that produce will be the same. So that's, this is what was stated the purpose of this square. So that's an order four magic square. Now Sudoku grids, um, let's have a mini Sudoku. That's where you can see what it is. It's got the numbers one to four instead of the numbers one to nine. But the same principles apply. Uh, those are not magic squares necessarily because um, the sums along the diagonals do not have to uh, fit in with this rule. They're called semi magic squares, an example of a semi magic square. And so a semi magic square has the same sum of the rows and the columns, but we don't mind about the diagonals. Now Sudoku sort of gets into that classification. It's not cheating exactly, but of course, because this one has the numbers 1, 2, 3, and four in every row and in every column obviously the sum of those numbers is always gonna be the same. They're the same numbers. So Sudoku is a semi magic square. So-called. Now the most famous magic square in western art is in this picture melancholia by albe dura. You might not be able to see it so clearly because it's in the top right hand end of that picture, but I've, I've enlarged it so you can see it, uh, better. So this is a classical, it's got the numbers one to 16 order four magic square. The picture was made in the year 15, 14. And you can see 1514 is those two numbers in the middle of the bottom row. Uh, 1514 was the year that JIRA's mother died, hence the melancholia. But there's lots of other symbolism in this picture, for example. Um, at that time different planets were associated to different characteristics of various kinds. The planet's SA was associated with melancholy. It was also associated completely independently, I should say with geometry. Geometry does not make you sad.<laugh> makes you happy. Um, but that's why there's a lot of geometry going on in this picture as well. Now magic squares of different sizes were also associated to different planets, but the size of magic square that's associated to Saturn is, if I remember rightly, order six six by six square. So what's this four by four square doing in there? Well, if you are feeling melancholy, an antidote to that might be to do something a bit more jovial and jovial. Things are associated with the planet Jupiter, 'cause JoVE is another word for Jupiter. So four by four magic squares are associated with Jupiter. But these, this is an antidote your melancholy. So that's what that square is doing in there. Now we could work out the magic number of this particular order for classical magic square. We can just add up the numbers in one of the rose cons or diagonals, but we don't have to because it turns out that every classical magic square of a given order has the same magic number. Here's that dura one again reproduced here just just for a note. We can prove this and we do something that mathematicians quite like to do, which is to work out the same thing in two different ways and then say, oh those, then these things, uh, they're both equal to this middle thing, so they're the same as each other. And the thing we're going to do, the thing we're going to work out is the sum of all the numbers in that square. And you'll, you'll see why this helps us. So if you want to work out the sum of all the numbers in that square, well we just have to add up the numbers. One to 16, fine. Now there's a cute little trick to doing this without actually having to do any work. It's another thing mathematicians like, um, so we can also write that s that sum, we can just add them up in the other direction, right? 16 down to one. And the reason that's useful is if we now add those two equations together on the left, we've got twice the sum the thing we're interested in. On the right, you can see all those pairs add up to the same thing. 17 one plus 16, two plus 15 all the way down. So on the right we've got 16 lots of 17 on the left, we've got twice the thing we're interested in. So if we just halve everything, we now find that our sum S is half of 16 times 17. We don't need to work that out yet or indeed ever because there's another way to work out the sum of all the numbers in the square. And that is to notice every row sums two the same thing, the magic number that we're trying to find. Let's call that magic number M. Then we know that there's sum of all the numbers in the square. It's just four lots of the magic number 'cause we've got four rows. Great. So now we've got two different expressions for our s make them equal to each other and we can find out m we don't even need to find s not interested in that. We can find M directly. It's one eighth of 16 times 17. And we're at the point now where even I can do that with a live audience <laugh>, an eighth of 16 is two and two times 17 is 34. So the magic number, and you can check this for the juris square, but it'll be true for any order for classical magic square. The magic number is 34 has to be, and really the four, the fact of it being four was not involved in any of this stuff. We didn't need it to be four that wasn't special. And you can actually use this same process to work out the magic number of any order. NN is of course our favorite number. Um, any classical magic square of order n so an n by n square, it will contain the numbers one up to n squared. So if you just replace all the fours in what I did before with Ns, um, you know, the same reasoning applies. And you get this formula for the magic square, uh, the magic number of a classical magic square of order M. So we can work out for example, when n equals three. What's that? Uh, the low shoe square. The magic turtle square. Um, if N is three, you can put in that into this uh, this equation and you find that the magic number is 50 and here is the square and you can check yes indeed, that that's true. It also shows you that there cannot be a classical magic square of order two. And the reason for that is if you put n equals two into that little formula there, uh, two squared plus one is five and half times two is one. So you get five, that would be the magic number. But if you try and actually make five, what's got to go with one to make five? You know, this, this square would have to have the numbers 1, 2, 3, and four in it. But one would always have to be paired with four. So four would have to go actually in every single one of those gaps to make this be a magic square. And that's not allowed. Where are two and three gonna go? So there are no classical magic squares of order two, but it turns out there are definitely classical magic squares of every other order. So two doesn't work. Everything else you can do and methods for finding these things were being developed in, in, you know, from hundreds of years ago, one of the most interesting writers and kinda mathematicians working on magic squares was um, Mohamed ib Mohammed Alani Al Kwi who was born in, I put this sort of red, red uh, blob there. He was born in what's now northern Nigeria and then he moved north and he lived and worked uh, mostly in Cairo in Egypt. And it was there when in 1732 he wrote a treatise on magic squares. And in that he did loads of stuff. He classified, he found all the order three classical magic squares and he gave away of producing a magic square of any odd order. So order five, order seven and so on. And that there are algorithms that produce all other sizes as well. I'm gonna show you his method. You not gonna try it for like making a seven by seven magic square on your way home, the train or something. So here let's make a five by five one and it's the same rule for any size as long as it's an odd number. So you put a one in the middle of the top row and then the basic principle is you move upwards and diagonally to the right. So up one square and right one square. Now already you are thinking, but Sarah, you can't move up one square, you're already at the top. So what you do then you imagine you're playing like an old fashioned game of S space invaders. This may be you guys in the olden days there are these games where the memory on the computer wasn't, wasn't very high. So when you went off the top of the screen, you just reappeared at the bottom of the screen. Kind of saves memory in producing the game. When you go off the right hand side of the screen, you reappear on the left hand side. So you, that's exactly what you do with this method. So with this one, if we go up one that brings us, actually we reappear at the bottom of the square and then you go one to the right. So you move in diagonally. So your two goes there and then you move diagonally up one, right, one, three up, one right one where we loop back to the left hand side four, move diagonally again. Now six, we want to put where that one already is. The rule in that situation is you just move down a square instead. So we get six here, then we're moving diagonally again, 7, 8, 9, 10, oh our way is blocked, move down then diagonally uh, from 11, 12, 13, 14, 15 our way will be blocked again. We want to put 16 where the 11 is. No worries, we just moved down a square 16 and then we can finish 17, 18, 19, 20. Oh we blocked, moved down diagonally, diagonally, diagonally. And there we are. So that, I mean you can check, I'm not gonna do all the additions right now. That indeed is a classical magic square of order five. So that's the method and that will allow you to create one of, of any odd order. Okay? So the great thing is once you've got one magic square of a given size, you can make more. This is again, mathematicians really like making use of something we already have and using it many times. So here is our low shoe square sacred turtle sitting on the top with that square we can make another one. And what we do is we can rotate that square 90 degrees to the right and what you get is another magic square. The reason is that the rows have become columns. The columns have become rows. The diagonals are still diagonals but it doesn't affect the sums. So you still have this same magic property. So that's one of the symmetries of a square. Actually any of the symmetries of a square will still give you a magic square. You're not affecting that property. There are eight symmetries of a square, including the one where you just sit there and don't do anything. Um, there are then there are three kind of rotations you can do apart from that. And then there are reflections in the, in the various symmetry lines. So from one starting square that actually gives you a set of eight magic squares. So eight for the price of one is a pretty good deal. Those eight squares, we call those the orbit of the original square. Uh, because the orbit is everywhere you can get to and we are getting there by symmetries, which are of course wonderful. So our original low shoe square could give us eight squares. We can also use this idea to find actually all of the order eight of no of the order three classical magic squares. So these three by three ones, here's what we do. We say start with a blank square. Where's one going to go? Where can we put one? Well are the options. Now remember the magic number here is 15. So the sum of every row column and diagonal is 15. So wherever the number one goes in its row, in its column and if it's on a diagonal, you've got to have two other numbers and the sum of the three of them is 15. So the sum of the two mystery numbers is 14. And there's actually only two ways to do that. You can have nine plus five or eight plus six. You can't have seven plus seven, you've only got one seven. So there's two possibilities for one, um, to, to be able to, to go with one to make a row column or diagonal. So one cannot go in the center because then it's in four, it's involved in four sums, a row, a column, and two diagonals. It can't go, it's a corner 'cause then it's involved in three sums, a row, a column, and a diagonal. So it must be in one of these off diagonal places. That's the only option. We dunno which one, but what we're gonna do is we're gonna say, well I'll just rotate it until it's on the left. And that's, I haven't lost anything because when I'm done with this and I've got all the possibilities I can, can then reproduce all the ones I I rotated by just working out, you know, these orbits. So let, we can assume without any worrying that one is on the left hand side there. Now where is nine? Nine has the same problem as one. It only can fit with two different pairs of numbers to make 50. Here they are. They can go with one and five or it can go with two and four. That's the only possibilities. So again, nine cannot go in any, any square where there's a diagonal. It can't go in any of these three places because then it would be involved in at least three sums. We know that nine must go with one in either its row or its column. So there's only one one place left. It must be like this. And then five must be in the middle. And the column containing one must have a six and an eight in it in some order. But again, we don't really care which, which way it is in the particular square we're thinking of because we can just reflect it and then assume that six is at the top and we'll do the orbit and get everything back when we're done. Now this is great 'cause at this point we now know we have got actually everything that allows us to complete the square because the two diagonals have two of the three numbers. That means there's only one option for the remaining ones. And then we can fill in those last two squares. We've got our square. So what we've shown is that every single order, three classical magic square is in the orbit of this guy. So we can just reconstruct all of them there. They all are. Those are the ones you can get by rotations. These are the ones you can get by reflections. That is it. That's the full list. So the low shoes square must be somewhere in there. I dunno if you spotted it. Here it is. That's it. There are eight. Now you could say there are somehow really there are one, there's one but it's just one and then all it's symmetries. So if you want to say that, and that's often what mathematicians will do if we're trying to work out how many of these magic squares there are of different sizes by that same token. So if we're saying somehow there's really just one of order three, then here are the numbers which grow absolutely vast of how many there are of bigger, bigger orders. And that order six, which is a ridiculously large number, it's got a little question mark over it because it's still not absolutely confirmed. Even though magic squares have been studied for thousands of years, it's still not absolutely confirmed that this is the exact number. Um, there's lots of computer checking that's being done. This is the latest as at September this year. They're pretty sure, but they're not absolutely certain. So vast numbers. And we have, I mean if you think about order nine, which is kind of comparing to Sudoku, we don't even know at all how many there are of that size. That's how huge this, this search space is. But this is for classical ones that involve the numbers one up to n squared. If you're allowed to put any numbers you like in there are infinitely many. And the reason is once you've got one is that perfume one from before. What you could do is double all the numbers in that square. That'll still be a magic square or treble or multiply by anything. And you'll still get another magic square. If you multiply all of the entries by the same fixed constant, the answer will still be a magic square. And if you've got several different magic squares, you can add them together and make more. So once you've got one, you can get infinitely many. So that gives you, you know, if, if you remove the classical requirement, you can get infinitely manu magic squares. And there's, before we we're gonna move on from magic squares, but just to say there's other kinds of ways you can explore, you can think about magic cubes, you can think about different magic. So this one in the middle, it's not a magic square by our definition, but in this square the product of ev of the numbers in every row column and diagonal is constant. So that's a different kind of magic. And then on the right, this is called, this is an anti magic square. The requirement here is that the sums of the rose columns and diagonals must all be different. So there's lots of scope for exploring, which is cool. Okay, let's think about another kind of number square Latin squares. So Latin squares, which were in the title of the lecture, they are well sudokus are Latin squares, but not necessarily vice versa.'cause a Latin square requires you, this is an order nine one, it's a Sudoku as well as it happens. But the numbers in this case, one to nine appear exactly once in each row and in each column Sudoku have an extra requirement. They also need the numbers to appear once in each block. So every Sudoku is a Latin square, but not every Latin square is a Sudoku. Now Latin squares have loads of interesting applications. One of them is in experiment design. So here is a Latin square on a hillside in Wales. Um, what they were doing here was they were trying to look at different species of tree and see how they did in in harsh weather conditions. Now when you're doing that, you want to kind of get rid of any extraneous things that might make one tree do better than the other. But for kind of the wrong, not the thing you're looking for, you need a very big patch of land to do an experiment involving five species of tree. So you can't guarantee it's impossible to guarantee that, you know, the soil conditions, the humidity, the moisture content, the aspect of the slope, all of those things, you can't make them completely constant across an area of land that big. So instead of having like, you know, plot one, plot two, plot three plot plot four and plot five, what you do is to create a Latin square, a five by five array, and you have a plot, um, or uh, you know, an area of land for each species, one in each row and in each column. And that kind of, you know, separates them out and, and hopefully then has a sort of sample of each part of the different bits of land so that it's a fairer experiment. Somehow it gives you more robust data. Now we talked about order three Latin squares. You can think about order three, uh, order three magic squares. We can think about order three Latin squares here is one. So this would have, if it's numbers, you'd want the numbers one to three in each row and in each column exactly once. Um, but it doesn't have to be numbers as we've seen. It could be trees or it could be colors. How many possible ways are there? Well, if you've got your first row, and I haven't specified how I'm assigning these, these, these colors to the numbers, but here's your first row. You can then think about the first column. There's only two ways to finish that. Here they are. And actually it turns out once you've got this far, the rest is determined, right? There's only one Latin square that looks like each of these kinds. Here they are. So now there's two kind of basic Latin squares, but we need to know where to put the numbers. So which number is gonna be red? Well, there's three possibilities. One, two or three. Once you've chosen that, there's two possibilities for what's gonna be yellow. And then whatever's left must be green. So three times, two, six possibilities, meaning there are 12 order three Latin squares and the numbers go up, but it's not as crazy as for magic squares. Here's some numbers. They're big numbers order six a mere 821 million. And we do know exactly how many there are of order nine. It's that rather large number here, 10 to the power 27, um, you know, five, five times that. So we know how many there are of order nine. It's a smaller problem, not much smaller, but it's a bit smaller. Now why they called Latin squares to answer that, um, we need to see an old puzzle. This is quite a cool puzzle. You take a standard pack of playing cards and what you do is you take the top four value cards from each of the four suits. So the jack, queen, king, and ace from each of the suits, which are spades, hearts, clubs, and diamonds. That gives you 16 cards. And your job is to arrange them in a square so that in every row and in every column there is exactly one heart, um, one spade, one club, one diamond. So one of each suit and exactly one of each card value. So there should be one king, for example, in each row, in each column. And there should be one diamond in each row, in each column. And implicit in this of course is, you know, you've got a standard pack of cards. You, you should have each pair occurring exactly once. So like one king of hearts, one ace of spades in there. Now this has lots of solutions, it's a fun puzzle. But after a while, maybe you could do it a little bit after this, in the 19th century in the court of, uh, Catherine, the great of Russia in Petersburg, they were all trying to solve the 36 officers problem. That is exactly this, this card problem. But bigger in this problem, you have six army regiments and six ranks in each regiment. So you have 36 soldiers in total, and you have to arrange them in a, in a six by six square, such that in every row and in every column there is one of each regimen and one of each rank, and no pair is repeated. So you don't have like two generals from regimen one or something. So what we've got here, actually let's take with the cards. You've got two Latin squares happening at the same time. You've got a Latin square with the suits one, one of each suit in each row in each column, and you've got a Latin square with the card values, one in each row, one in each column. So you've got two Latin squares overlaid with this extra requirement that every pair of, uh, objects occurs exactly once one ace of spades. So these, these, this kind of pairings, we have two Latin squares together that have this special relationship with each other. We now call those orthogonal Latin squares. But when Catherine the Great couldn't do this problem and she asked a nearby mathematician to help her, the guy she asked, um, who was visiting from Petersburg at the time, was one of the best mathematicians of all time, Leonard Oiler. And when he started thinking about this problem, he realized that what you had was two of these particular squares. And he would use, he used some notation in the first square. He called the things in that square, the set that was being used. He labeled them with Latin letters, A, B, C, D. And in the other squares, he labeled the things in that set, um, with Greek letters, alpha, beta, gamma, delta and so on. So he called them Greco Latin squares. We now call them orthogonal Latin squares. And Latin squares is kind of a back formation from that because if you're just dealing with one of them, we just call that a Latin square now. But that's where that came from. And he was asked, he asked himself, well actually, can we always make these things? We know we can do it with the cards. That's order four. He could not do it either. For the 36 officers, he couldn't solve that problem and equals six version, he and he realized he could do, whenever it's an old number, he could do it. Um, whenever it's a multiple of four, he could do it. It's impossible for n equals two, just like magic squares, he couldn't do it for n equals six. So his conjecture is that you can always make these things, these orthogonal Latin squares, unless your n the size of the square is even, but not a multiple of four. So it's two more than a multiple of four. So you can't do it for n equals two. And he and he con injected, you can't do it for n equals six or 10 or 14 or any of these, but you can do it for everything else. Now oiler, as I said, one of the greatest mathematicians of ever, um, of all time. And so when he conjectures something, you tend to believe it. So it was a great shock when in 19 59, 3 mathematicians found order, 10 oral Latin squares. It was on the front cover of Scientific American. It was all like world news exciting. Uh, and so this was kind of relatively recent mathematics when, um, I'm sure you can already tell where this is going. This is the ideal way to structure your novel. Yes. So in 1978, George Pek structured his novel life, a user's manual around these order 10 orthogonal Latin squares. He set it in a Parisian apartment block, 10 by 10, a hundred rooms and every chapter happened in one of the a different room. And he gave the chapters a unique flavor. And what he did was he tap particular characteristics or objects and he put them in lists of 10. So it might be like fabrics and colors, and you use the orthogonal Latin square structure to ensure that each pair from these sets occurred in exactly one chapter. So there's only one chapter, you know, that would have red silk in it. There's only one chapter that would have green velvet, something like this. So every chapter gets its unique flavor from this structure. Now the book actually that one of the main themes of the book is failure. Lots of the characters are trying to complete things, do things. One of 'em is trying to complete a lot of jigsaw puzzles of particular places, and he isn't able to do it. Um, and so then what better structure to put under your book than this emblem of the kind of, the only time, almost the oiler, this great mathematician actually failed to predict something. So this is, you know, it's, it fits in with the book. There's another really cool bit of structure. How do you decide which room you're going to have in your next chapter? Well, the stories follow a night's tour of a 10 by 10 chess board. But remember this is a book about failure. It only has 99 chapters. The tour is never completed. And I love what per he blames one of his own characters. He says the little girl on pages 295 and 394 is solely responsible for this laps. So it's, it's very cool. Now, obviously this is the most important application of Latin squares, but occasionally there are some, I mean, you know, the real world's over rated, but there there are some, there are some other applications. I just wanna mention one and then we're gonna go back to Sudoku. Uh, so the one I want to mention involves a kind of extension of this idea of these orthogonal Latin squares, two Latin squares that you put 'em on top of each other, they're both Latin squares and every pair that you see from, from the sets that are involved occurs exactly once they're one ace of spades rule. It turns out that if you are lucky, sometimes you can make more of these orthogonal squares. In other words, you can have a whole set of, of Latin squares, of a particular size where every pair of them has this, this property, they are orthogonal. And so you call a set like this a set of mutually orthogonal Latin squares, which is a long phrase. Now, can we find these things we know, you know, sometimes you can't even find two orthogonal Latin squares. In the case of the officer's problem, you couldn't do it, it's impossible. Uh, but sometimes you're, you are lucky and you are lucky when the order of the square, so the size of the square, um, let's call it Q, when that number Q is either a prime number or a power of a prime number, then you can guarantee that you'll be able to find a set of Q minus one mutually orthogonal Latin squares. So when qic equals three for example, it's a prime number. We can guarantee that you can find two orthogonal Latin squares. So that's one of the ones that actually oil managed to find. Now what use is that? Well, it turns out there is an application in a rather unexpected place. Uh, it's when you want to send messages, they don't have to be secret, but they're sent across what we call a noisy channel where, for example, maybe you are like a space probe 150 million miles from Earth and you're sending a signal back and you know that going across all that distance of space every so often, like a passing neutrino will bump into you and maybe turn one of your ones into a zero or something like this. So it's that kind of situation where sometimes a message can be corrupted a little bit and you, and you want to still be able to understand it at the other end. So what you don't want to do is just send, you know, say you are wanting to send yes or no, and maybe yes is one and no is zero. If you just send that yes or no, if that's a small chance, but if that message gets corrupted and it's only one letter that you're sending, when you receive on the other end a message, you can't tell that something's gone wrong. You know, you're, you are expecting a one or a zero. If you receive a zero, who knows whether that was what was meant. So what you can do is you can add a bit of redundancy to this, uh, a sort of a checking mechanism. So for instance, suppose you want to send yes or no, what you do is to duplicate your message. So now you can either send one, one for yes or zero, zero for no, and let's you know, we can assume that it's quite rare for there to be any kind of problem. You know, not very many errors are introduced. We can assume, let's say that, that at worst there'll be one, one digit that gets tweaked. So us on the receiving end, if we receive zero one, we know that that is not a message that could have been sent. The, you know, we, we got a collection of messages that could be sent. We'll call that the code, the code words here would be one, one and n naught, we receive naught. One, something's gone wrong. So we have detected the error, but we don't know what was originally said. However, if we send everything three times, which is bit inefficient, but if we do that, so if I send either NN naught or 1 1 1 and and you receive naught one, one, again, that's not a code word, so something's gone wrong. But if we're assuming at most one, uh, digit has been changed, then we, we can say what the original message was, we can correct the error. So what's happening here is we've got a collection of words. We call it a code, and the words of the code words, so words, these strings of, of digits or letters. In our case in this example, the code consists of the words naught, naught, naught, and 1, 1 1. And then what we do is when we receive a message, if it's not a correct code word, we know something's gone wrong and we've confined what was the original message, the correct message by finding the closest code word. So what does that mean closest? Well, there's this very simple idea of distance between words, which is the number of places where they differ from each other. So, uh, for example, we've received 0 1 1. The distance between that and 0 0 0 is two because they differ in two places, whereas the distance between 0, 1, 1 and 1 1 1 is one because they only differ in that first position. So we do have a closest word and then that can be our answer. We think it's um, the original word was 1, 1, 1, right? So that's how we correct the error. The reason that works, um, is because those code words that we've got, um, are distanced three apart. They differ from each other in three places. So you can't be distance one from both of them. If you're distance one from this guy, you must be at least distance two from that guy because they're three apart in total. So we can guarantee to be able to correct an error if our, our code that we've got has this property that all of the words in it are at least three apart from each other. They different, at least three places. Okay? So remembering that what we'd really like, we'd like to be able to correct an error but have as many messages as possible, as big a code as we can.'cause that gives the greatest versatility to, to our system. So how big can this be? Well, let's have a think about this. Um, maybe we can make it bigger by allowing more letters, right? So, um, we had three, we had zeros and ones. So our alphabet was rather small. Our alphabet just had two letters. I mean the English alphabet has 26 letters. Maybe we can use that. And we also, we had, we had words which only had three letters in. Maybe we can have slightly longer. So let's imagine that we've got code and it has got words in it that have four letters and those letters can be drawn from an alphabet. And let's say the alphabet has Q letters. So we talked, we had two letters, zeros and ones, but we could have more letters maybe that gives us more words to play with. So what's the best we could hope for if we want every, all of those words that are in our code to be at least different, at least three places. Well, if you've got two words in the code, A, B, C, D and E, F, G, H, it's A and B are the same two letters as ENF, that's bad because then it would mean that those two words could only possibly differ in two places the last two places. So that can't happen. So any two code words have got to have the first two letters can't match. So everyone has to have a different first two letters. How many different first two letters are there? Well if your first two letters are A and B, there are Q choices for a, it comes from an alphabet of Q letters and Q choices for B there are q squared possible first two letters. And so that means the size of your code, you can't have more than that'cause any two code words have a different beginning. So that's the absolute upper maximum that you can hope to achieve, right? That's good. Um, if we can get there. Now here's Latin squares coming back. This is possible precisely when there is a pair of orthogonal Latin squares of order Q. So squares of side Q, that is, that's super cool. What are Latin squares doing there?<laugh>, that seems really weird. I'll show you, I'll just do a little example. So that's the same theory I've written up at the top. I'm gonna give you just an example here, here I've got Q equals three. So I'm making three order three Latin squares. Those two are orthogonal to each other. Uh, and here's how we make the code for each row and column. Um, we get uh, a code word. So in the second row, first column, this is the code where we're gonna make 2 1, 2, 3. How do we get the last two bits? So two for the second row, one for the first column, and then what's the entry in the left hand square? It's two. What's the entry in the right hand square? It's three. So we can do that and we can make nine words in that way. And it turns out this is one of these codes. And the reason is that if you, any one of these words can be completely determined just by knowing any two of its letters, that means no two of the words can have the same two letters in the same places. For example, if you are given the last two letters, one of these words, what does that tell you? That tells you the entries in these squares, right? But these are orthogonal. So every pair appears exactly once in that structure. And so we can say exactly which row and column it appears in by just finding it that. So that's one you can check the other possibilities. So these, this code and all others you can produce like it do indeed differ all the words differently, at least three letters so they can correct one error. So, and this is, we can get this from these, from these Latin squares. It's fantastic. There is a more general result. I will put it there for 10 seconds. You can actually do this if you have more mutually orthogonal squares, you can correct more errors. So that's really, really cool. Okay, well let's get back to Sudoku. Um, in, in the last five minutes. So we've seen some Latin squares, not all of those vast number of Latin squares of border nine of course are going to be Sudoku. Um, because we have an extra requirement for Sudoku, we need this block rule. So actually it is known how many or how many Sudoku grids there are. Um, I want to show you a really clever way of finding an estimate of that number that I think is kind of nice and intuitive and it somehow, it gives me more <laugh> more information in a way than the exact number does. So I want to just show you what this idea is. So Sudoku have to have three properties. They have to be Latin squares. So the numbers appear once in each row and column, but they also are what I'm gonna call block grids. That the numbers appear exactly once in each block. So what we're gonna try and do is first to establish how many block grids there are, how many, so then we're not, they're not yet required to be Latin squares. How many of these grids are there that satisfy this block rule? So we'll do a mini Sudoku example first. Um, so in this this size of Sudoku grid, you have the numbers one to four and we are just interested so far in, in making the ones that satisfy the block requirement. So in other words, in each of these little blocks, you've gotta have the numbers 1, 2, 3, and four somewhere in some order. So how many ways there to do it? Well, let's just focus on this top left hand block and we've gotta put the number one somewhere. There's four places we could put it. And then there's three places left where the next number could go and then two places where the next number could go. And then there's only one remaining place and the final number goes in there. So there's four choices times three times two times one. We call this number four factorial. It's the product. So n factorial is the product of the numbers from one up to N. So four factorial, that's the exclamation mark that's pronounced factorial, uh, which of course we can calculate. It's 24. So there's 24 ways to make a block. We've got four blocks. Remember we don't care about the Rowan column rule yet. So is 24 times, 24 times 24 times 24, which I'm sure you've just worked out in your head is about 331,000 ways to make a block grid. Now we need more than that. What we next want to work out is actually how many of these block grids satisfy also the row rule that the numbers one to four appear exactly once in each row. So let's think about that. Let's think about these top two rows. Once you filled in the left hand block, which of course there are 24 ways to do, then there's only two ways to complete the top row. It could be three, four or four three. There's only two ways to complete the second row. One, two or two one. So four ways to complete these first two rows. Two times two, um, once you've chosen your block. So 24 times, four ways to complete the first two rows and then you can do the second two rows in the same way. So if you do that, don't worry about the detail, but I just want you to see the, the idea of this, this argument. You get some number 9,216 block grids that also satisfy the row rule. Now what we then do is we say actually that is a particular fraction of the total number. It's oh, it's 1 36 of all of the block grids. Um, satisfy this row rule. And you can do the same exact calculation but just uh, tilted by 90 degrees and say that by the same reasoning, 1 36 of the block grids satisfy the column rule. What we want to know is what proportion of the grids satisfy both the row rule and the column rule? Those are our Sudoku. Okay, so let's move back up to the standard size with exactly the same kind of ideas. The number of order nine block grids. So we don't care about rows and columns yet, but those standard Sudoku had these nine blocks. Each block contains the numbers one to nine in some order. The number of those is, this looks quite harmless, but nine factorial raised to the power nine is a very, very large number.<laugh>, we don't need to calculate it, but that's how many order nine block grids there are. And we can do a calculation, it's a bit more involved. That tells us how many of those block grids satisfy the row rule and it's one 10th of them. You'll notice I haven't told you what n is. I I will put it in the transcript, but it's a very large number, which is known exactly it's something like 128 trillion. We, we don't need to write it down explicitly right now, but we can work out this fraction. One 10th of them satisfy the row rule. And so also one 10th of them satisfy the column rule. Now here's the assumption that we're gonna make, which is an incorrect assumption, but it's useful.<laugh>, uh, we are gonna assume that satisfying the row rule is independent of satisfying the column rule. The reason that's a helpful assumption, even though it's not actually quite correct, it's nearly correct, we're not quite, is that if you've got two independent events, then that you can multiply their probabilities to find out the probability of both of them happening. Same time. For example, if you have a pack of cards, one 13th of those cards are ACEs. One quarter of those cards are hearts. So because those independent, we can say that one 13th times one quarter, which is one 52nd, 52, 1 50. Second of the cards are ACEs of hearts, which is, that's what we find the pack of cards. So if being satisfying the row rule is independent from satisfying the column rule, then we could say that one of, one of all of the block grids are pseudo kus. And if you work out that number, it's about this big number, 6.65, seven times 10 to the 21. Big number. What's really brilliant is I've said it's, this isn't, they're not quite independent, but they're really nearly independent. You can work out the exact answer. It requires a lot of fiddly calculation and lots of computer time. And I'm sure you were almost there in your heads, but it's this, but if you look that's really very, very close to this estimate, it's a really great estimate. I think it's, it's a useful calculation to do. It's only not 0.2 of a percent out. So that's how many we did mention one other question. We know we've got all these grids now, but of course to make puzzles you need to remove some of the numbers. How many clues is enough to guarantee that you're gonna have a unique answer? So this is counterintuitive again, um, look at this grid. It has 77 of the numbers filled in. Surely, surely we can complete this, but we can't. The and the top row on the second row, sorry there. Um, the missing numbers are one and two and on the, what's that? The seventh row, the missing numbers are also one and two, there is no way to know how they should go. It's either one, two on the top and two one on the bottom or the other way round. We do not have enough information to write this down. So unless you are careful, you, you know, you risk getting into these situations where even if you have lots of numbers, you can't complete the grid. So this is not a trivial problem. You can't just remove 30 of the numbers and think it's all gonna be fine. There has to be some, you have to be really careful that you still have a unique solution. Um, and so we talk about minimal grids, which is where, um, you've got some of the entries filled in and it's got a unique solution. But if you remove any one of those entries, then what you have then has multiple solutions. So those minimal grids are kind of the best case scenario in terms of you can complete this with a unique solution. Um, but anything less does not give you uniqueness. And then, you know, if you want to make an easier puzzle, you can add a few things. You know, you've got a unique solution by that time. Um, but, but you can't remove anything. Now how many do you need, do you think? Well, it turns out there's a lot of activity on this. It took about 20 years to resolve, I guess. Um, in about 10 years ago it was found you have to have 17 entries, at least not any 17. There are lots of seven ways to put 17 numbers in that don't give you an unique solution, but 17, easy enough, as long as you choose them carefully. If you have 16, it's never enough. 16 is not going to be enough. Wherever you put them, however cleverly you place them, you will, you will not get a unique solution with 16. But with 17, yes, but what's not known, and if you're going to become mathematicians, this is still an open problem. Uh, how many of these minimal grids are there? What are these minimal grids? And this is an ongoing, uh, area of active investigation. And so just to finish, I'm gonna mention in one minute some variations of Sudoku like we saw with magic squares. Um, many variations for you to explore bigger doku, go as big as you like cube doku or hyper cube doku. Go as high as dimensional as you like. I like this one. Ven doku, uh, these are all Sudoku grids. I haven't put any number in. You'll notice because I <laugh>, but you can, you could imagine a puzzle where you had three P Sudoku grids satisfying the Sudoku rules, but there's an overlap. So that gives you more information about the places that are in two or three of these grids. That means you can get away with fewer clues at the beginning. So that's kind of an interesting question. How few clues do you need? Um, magic doku, it's also a magic square. Got the low shoe, magic square in the middle as well. Just added, added little thing. And this last one, now I don't know if I've invented, well, I have invented it, but I dunno if anyone else has invented it. I was trying to think what's like that anti magic square. So here I present the su don't coup <laugh>. The rule here is every rule has to break exactly once. So every row, column and block must contain exactly three of the numbers, but not all four. So the top row, it's got 1, 2, 3, it hasn't got a four. So this missing square, there's empty square. What could go in that square in order to maintain this rule? Well, in that block that it's in, you've got one, two, and three, you haven't got four. So if you put four in there, you'd have a correct block not allowed. So it can't be four. Look at the row it's in. Um, you can't put one in there. Otherwise that row would be right. And the column, you can't put three in there. Otherwise that column would be right. So for a genuine, so don't coup, the only number that can go in that missing space is two. Now I have not tried to make an order nine, so don't coup. If you've got a, a free hour, uh, I invite you to do that. I don't even know if it's possible, but there we are. So that's plenty from me. We'll come back next time. I'm gonna be talking about, uh, mathematical puzzles and paradoxes, including the one that I've hinted at there. But we'll stop there for today. Thank you very much, Sarah. Thank you very much. And uh, just at the beginning before we were starting, we were talking about the puzzles in the paper and Sarah saying, well, I work so much on this that I actually do the crossword. And I was thinking, well, maybe after this I'll have a go at the pseudo ku, but after this I think I'll be sticking to the word search. Um, that was, that was brilliant. Thank you so much. I'm sure you guys have some questions. I'm gonna start you off just with, um, a little one from here. Uh, so lifer uses manual. This is an interesting idea. So, um, taking that idea, are there ways that you can actually, I mean these are, this is incredible the amount of mathematics that goes into preparing the game, let alone doing the game. Yes. But are there sort of applications that you can use practically for these sorts of, this sort of logic? And are there any sort of careers that come that could come out of it? So I mean, yes, being able to be logical, <laugh> is a good skill to have. I mean, so we talked about there are some applications directly of, of these Latin squares and other kinds of structures like this. Um, but the process of thinking things through and being able to say we reason our way through a problem, that is really great skill to have. It can, you know, I mean, any job that's a useful skill to have. But for example, I mean of course you can become a mathematician, but you could computer programmers. Mm-hmm, <affirmative>, this is exactly what you do. You have to cover every, if you're writing a program, you have to cover every eventuality. You have to make sure you haven't missed out any possibility. You've got to follow your way through a kind of branching narrative of, of the algorithm and make sure that it does what you want it to do. So this is for me, I mean, writing a program is very, like constructing a mathematical proof and these same kinds of ideas of how is this fitting together? I have to know how it all works are just absolutely relevant there. So yeah. Um, when, when you were talking about Greek Latin squares Yeah. You, you mentioned the, um, was it four m plus two? Um, the Yes. Um, 6, 10, 14 sequence. Yeah. And that the ten one had been solved. Yes. I think Ronald Fisher proved that the six one couldn't be. Yes. Um, has any progress been made on 14 18, 2, 2, Et cetera? Yes. So in fact, it's kind of the worst possible outcome for oiler because, so n equals two can't be done. Uh, n equals six, actually it was a, a guy called Gaston Terry who proved that in the right at the beginning of the 20th century. He proved it was impossible and it was aptly named a proof by exhaustion because he had to check not absolutely every possibility, but he managed to reduce it. He said everything that we could try is equivalent to one of this. Still very, very long list of things to check. And he did do that checking by hand in like 1905. Um, yes, 1959, the order 10 ones were found. And that kind of opened the flood gates because then suddenly there was this, oh, maybe people had sort of assumed there weren't gonna be these others, but actually it's been shown since then that you can do it for every single order. So 14, 18, all of those, they exist. These, these orthogonal Latin squares. The only two numbers where it fails are the ones the oiler <laugh> had had direct experience of two and six. And so, you know, unfortunately yes, his dataset was not big enough, uh, to, to see that what, that the pattern did not continue. So you can make order, um, n orthogonal Latin squares for every N except for two and six. If you Set your terms and you set your constraints, is it theoretically possible to solve any puzzle in the world? Hmm, <laugh>. Okay, well if the theoretically, but the puzzle has to be set up in order to be able to be solved. So this is one of the things about Sudoku that I say, you know, you have, there has to be a unique solution. There has to be a solution and only one. So if your puzzle has been designed kind of correctly then such that that's the case, then yeah, theoretically it can be solved. But it's of course actually doing it. As we all know, <laugh>, sometimes those killer Sudoku, uh, you know, you may not necessarily do it in the most elegant way, but it is theoretically possible to do it. Yes, There we go. Okay, thank you so much. Please join me in thanking Professor Sarah.