17 and Sudoku Clues - Numberphile


Uploaded by numberphile on 24.01.2012

Transcript:

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.