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.
I loved the joke at the end.