17 and Sudoku Clues - Numberphile

Key Takeaways

right we're going to talk about numbers in the news because just recently uh the number 17 was in the news this is one for sodoku fans because uh it's just been recently proved by a man called uh Gary Maguire he's a mathematician at University College in Dublin has proven that a Shoku uh need at least uh 17 Clues to solve it so soku if you don't know what they are uh they were they come from Japan they were big in the 1980s but then so were many things but here is a Sudoku it's a 9 by9 grid and the the idea is you fill every row with the numbers 1 to n uh without repeats uh you fill every column with the numbers one to n without repeats and then add for extra difficulty you fill these little squares these 3x3 squares with the numbers 1 to n without repeats and the idea with Sudoku is they'll give you some clue they'll clear most of this away it'll look like something like this they'll give you some Clues and they'll ask you to complete the stoku grid uh and the idea is you there should only be one way to complete the stoku grid if you see them in the newspapers the newspapers give you about 25 Clues to solve the grid but what Sudoku fans were interested in was what is the fewest number of clues that you need to solve that grid and the sidoku fans tried to find the fewest numbers you needed they found puzzles that had 17 numbers but they couldn't find any puzzles with 16 numbers uh if you tried to find puzzles with 16 numbers the answer you got wasn't unique you could get one or two answers from that puzzle so they thought maybe 17 is the smallest number you needed and so just at the beginning of this month this was proved uh by Gary Maguire uh who did a method which was part partly mathematics and partly using computer power let's talk about how many sudokus there are right if I want to fill a Sudoku grid like this the number of possible Sudoku grids is let me write this down for you uh let's see number of grids let's put an S on the end of that number of soku grids is well in words it's 6,700 million I million million uh mathematicians write it like this 6.7 * 10 21 so this is the number of Sudoku grids that there are now importantly uh what they were saying is they're not saying that every Sudoku grid can be solved with 17 Clues they are saying that there are no Sudoku grids that can be solved with 16 or fewer Clues not uniquely anyway so one way to solve this puzzle is to uh take all the possible sedoka grids and check all of them for 16 clue starting positions and to check if they give you a unique answer that's that's one way to do it it's a Brute Force way to do it how many ways I like to pick 16 clues for my Sudoku grid that number 16 clues I can't spell H 16 clues is around about 33 million billion around about 33 times or 10 to the 60 I think I've got that 3.3 * 10 60 now this is a massive number the problem was uh the guy who worked this out Gary Maguire if he he estimated that if he used the method that he already had uh it would take a computer around about 300,000 years to check every possible sidoku grid for every possible 16 clue starting position so he had to make the problem more simple than that this is what he did you see uh sudokus what you can do is if I took the first two rows and swapped them over it would still be a valid Sudoku grid that's allowed right it's the same if I took any of those first three rows and swapped them over you would get a valid sidoku grid the same is true for the next three rows if you SWA them over you'd get a valid grid and the last three rows you swap them over you get a valid grid and these bands as well if you take these as bands and swap the bands over you get a valid grid so if you had a valid 16 clue starting position it would still be a valid 16 clue starting position when you start to swap the rows what you get is a whole family of sudokus uh it's the same for the columns uh it's the same if I rotate the grid and it's the same if I start to swap the numbers if I took all the threes and swap them with all the fives you still get a valid grid you get a whole family so all you need is one representative from each family of Sudoku grids now how many of those are there all they need to do is check one representative from each family now they could also reduce the number of 16 clues that they had to check this number what you can do here's my Sudoku grid again take a look at this you see the seven and n and down here I've got another seven and N in the same columns now if I swap the sevens and nines over I get another valid Sudoku grid now I don't want to get two possible answers from my Sudoku puzzle so if I want a unique solution one of my Clues has to be one of these for numbers these are unavoidable squares so you're at least one of your Clues has to be from those squares so if you can find the unavoidable squares that reduces the number of 16 clues you have to check that's what they did so they were looking for unavoidable squares checking for these uh representatives from families of suda grid then they started to uh by brute force with a computer analyze them it took them 7 million computer hours to do it they started in uh January 2011 they finished the project in December M 2011 and they proved that nothing they checked you couldn't get a 16 clue puzzle from all these Sudoku grids we know 17 puzzles exist 17 clue puzzles exist so therefore they proved it 17 is the smallest amount of squ it's the fewest Clues you need to solve a soku grid uniquely and that's the most important part scientists and mathematicians get ask this all the time but if there's ever an appropriate time to ask this this seems like it surely there are better things to do with your time yeah right completely understand completely well for start we're talking about it because it's a bit of fun right and people know what Sudoku are so they can understand the puzzle that I'm trying to solve here the problem um by doing this the meth it's a hard problem it's a hard problem the methods that they had to develop to solve this problem can be used in other perhaps more serious applications in other problems in mathematics in other problems in combinatorics and so it's although it seems like it's a trivial thing it actually pushes the boundaries of our knowledge so it turns out not to be so do you want to hear my Gary mgu joke go on so this is my Gary McGuire joke Gary McGuire is the guy who solved this puzzle right here's my Gary McGuire joke what did the sodoku say to Gary McGuire You complete me that's a reference to the film Jerry McGuire yeah yeah it's like a joke it's not much like one I'll give you that I I have to be honest sudoku for me uh are not my favorite type of puzzles because it is a game of pure logic now people think mathematicians are just you know logic machines like we're robots uh but that isn't what mathematics is about I'm very keen to stress that this isn't what mathematics is about it's a much more creative thing than that and so for me because this is a game of pure logic that I know a computer can do I have no interest in it but this is very popular with people um crosswords Enthusiast and soku enthusiasts these are very popular kind of puzzles