17 and Sudoku Clues - Numberphile

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

I loved the joke at the end.

👍︎︎ 1 👤︎︎ u/Atomdude 📅︎︎ Mar 28 2016 🗫︎ replies
Captions
JAMES GRIME: Right. We're going to talk about numbers in the news, because just recently, the number 17 was in the news. This is one for Sudoku fans, because it's just been recently proved by a man called Gary McGuire, he's a mathematician at University College in Dublin, has proven that a Sudoku needs at least 17 clues to solve it. So, Sudoku, if you don't know what they are, they come from Japan. They were big in the 1980s, but then, so were many things. But here is a Sudoku. It's a 9x9 grid, and the idea is you fill every row with the numbers 1 to 9 without repeats. You fill every column with the numbers 1 to 9 without repeats. And then for extra difficulty, you fill these little squares, these 3x3 squares with the numbers 1 to 9 without repeats. And the idea with Sudoku is they'll give you some clues. They'll clear most of this away. It will look something like this. They'll give you some clues, and they'll ask you to complete the Sudoku grid, and the idea is there should only be one way to compete the Sudoku 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 Sudoku 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. 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 by Gary McGuire, who did a method which was 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. Let's see, number of grids. Let's put and S on the end of that. Number of Sudoku grids is, well, in words it's 6,700 million million million. Mathematicians write it like this. 6.7 times 10 to the 21. So this is the number of Sudoku grids that there are. Now, importantly, 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 take all the possible Sudoku grids and check all of them for 16 clue starting positions. And to check if they give you a unique answer. That's one way to do it. It's a brute force way to do it. How many ways are there to pick 16 clues from my Sudoku grid? That number, 16 clues, I can't spell. 16 clues is around about 33 million billion. Around about 33 times 10 to the 16. Think I've got that. 3.3 times 10 to 16. Now, this is a massive number. The problem was the guy you wrote this out, Gary McGuire. He estimated that if he used the method that he already had, it would take a computer around about 300,000 years to check every possible Sudoku 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, 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 Sudoku grid. The same is true for the next three rows. You swap them over, you 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. And what you get is a whole family of Sudokus. It's the same for the columns. 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 3s and swapped them with all the 5s, 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, we 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 this 7 and 9? And down here I've got another 7 and 9 in the same columns. Now, if I swap the 7s and 9s over, I get another valid Sudoku grid. Now, I don't want to get two possible answers for my Sudoku puzzle. So if I want a unique solution, one of my clues has to be one of these four numbers. These are unavoidable squares. So 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 an unavoidable squares, checking for these representatives from families of Sudoku grid, then they started to, by brute force with a computer, analyze them. It took them seven million computer hours to do it. They started in January, 2011. They finished the project in December, 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 amounts of squares. it's the fewest clues you need to solve a Sudoku grid uniquely. And that's the most important part. MALE SPEAKER: Scientists and mathematicians get asked 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. JAMES GRIME: Yeah. Right. Completely understand. Completely understand. Well, for a 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. By doing this, the method-- 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 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 w hear my Gary McGuire joke? MALE SPEAKER: Sure. JAMES GRIME: So this is my Gary McGuire joke. Gary McGuire is the guy who solved this puzzle, right? And here's my Gary McGuire joke. What did this the Sudoku say to Gary McGuire? You complete me. That's a reference to film Jerry Maguire. Yeah. It's like a joke. MALE SPEAKER: Yeah. JAMES GRIME: It's not much like one, I'll give you that. I have to be honest, Sudoku for me are not my favorite type of puzzles because it is a game of pure logic. Now, people think mathematicians are just logic machines, like we're robots. 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, and crosswords enthusiasts and Sudoku enthusiasts, these are very popular kinds of puzzles.
Info
Channel: Numberphile
Views: 1,976,910
Rating: 4.9077024 out of 5
Keywords: sudoku, puzzle, sudoku clues, numberphile, number phile, number, numbers, maths, mathematics, mathematical, numerals, count, counting Mathematics
Id: MlyTq-xVkQE
Channel Id: undefined
Length: 8min 40sec (520 seconds)
Published: Tue Jan 24 2012
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.