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.