The 8 Queen Problem - Numberphile Numberphile English (auto-generated) English

The 8 Queen Problem - NumberphileYouTube↗ IA↗(long shot)
Science & Technology 1.4M views 24.1K likes 549 dislikes 21 Aug 2015 Show Contributors 3

Numberphile 4.8M subscribers N/A YouTube↗

Contributed subtitles

Portuguese Luan Mark

Click to Play Video

so we're gonna do one of the famous puzzles that you can play with a chess

So we're gonna do one of the famous puzzles that you can play with a chess board.

board it's not chess itself but it's a

It's not chess, itself, but it's a puzzle you can play.

puzzle you can play the standard 8x8 chessboard and Queens so a queen if you

The standard 8 by 8 chess board, and queens.

don't know a queen is the strongest it's the best piece on a chess board because

So a queen, if you don't know, a queen is the strongest; it's the best piece on a chess board

it can move any number of squares to the

'Cause it can move any number of squares to the left and the right.

left and the right it can move any number of squares up and down and you can move to agony as well any number of

It can move any number of squares up and down, and it can move diagonally as well, any number of squares.

squares and oh if there's another piece in its way it takes it haha gotcha right

Oh! If there's another piece in its way, it takes it. Aha! Gotcha!

so that's how our Queen moves diagonally up and down left and right now the

Right, so that's how a queen moves: diagonally, up and down, left and right.

puzzle is can you place eight queens on a chess board so that none of the Queen's can attack each other so all the

Now the puzzle is: Can you place 8 queens on a chess board so that none of the queens can attack each other?

Queens are safe so this wouldn't work as a placement because we've got one Queen here I can take another there under

So all of the queens are safe. So this wouldn't work as a placement, because we've got one queen here that can take another.

attack but maybe something like this would work just fine now I've only got

They are under attack. But maybe something like this would work just fine.

two Queens here all Queens can take each of the Queen so the colors don't matter

Now I've only got 2 queens here. All queens can take each other queen, so the colors don't matter.

the question is can we place eight Queens on the board

The question is, can we place 8 queens on the board? Can we?

can we okay well how many ways can we place eight Queens on the board first of

Well, how many ways can we place 8 queens on the board?

all how many ways are there to do that let's look at that first right which

First of all, how many ways are there to do that? Let's look at that first.

doesn't mean that we've got 56 blanks I think we can do this calculation I think

Right, which does mean that we've got 56 blanks? I think we can do this calculation.

even Brady can do this calculation how

I think even Brady can do this calculation.

many ways can you arrange 64 objects

How many ways can we arrange 64 objects, Brady?

Brady: 64 factorial.

yeah 64 factorial if you have 64 objects there are 64 factorial ways to do that which is 64 times 63 times 60 to 61 all the way down to one so there are 64

James: Yeah, 64 factorial. If you have 64 objects, there are 64 factorial ways to do that: 64 times 63 times 62... all the way down to 1.

objects eight Queens and 56 blanks but you can rearrange their blanks between themselves and it doesn't change the position on the board so when I divide

So, there are 64 objects, 8 queens and 56 blanks. But you can rearrange the blanks between themselves, and it doesn't change the position on the board.

by how many blanks there are 56 factorial ways to arrange the blanks so

So, we're going to divide by how many blanks there are: 56 factorial ways to arrange the blanks.

we have to consider that the Queen's are the same so I can move the Queens between each other I can commute the Queens between each

So we have to consider that the queens are the same. I can move the queens between each other, I can commute the queens between each other

other and it doesn't affect the solution the positions they are on the board so

And it doesn't affect the solution; the positions they are on the board.

for that reason we are also going to divide through by 8 factorial there are

So for that reason, we are also going to divide through by 8 factorial.

eight Queens and they can be swapped around between each other tor divide

There are 8 queens, and they can be swapped around between each other.

through by 8 factorial so the number of

So we'll divide through by 8 factorial.

ways you can arrange those 8 Queens naively is four billion four hundred and twenty six million 165 thousand three hundred and sixty eight so there are

So the number of ways you can arrange those 8 queens naively is 4,426,165,368.

over four billion ways you can place your eight Queens on the board but that's naive Lee doing it that's not

So there are over 4 billion ways you can place your 8 queens on the board, but that's naively doing it.

considering how the Queens attack each other so you're gonna get city solutions

That's not considering how the queens attack each other, so you're going to get silly solutions

like this one or this or this these are no good these aren't solutions so how

Like this one, or this, or this. These are no good; these aren't solutions.

many solutions are there out of that four billion figure that do work so the Queens don't attack what do you think it

So, how many solutions are there, out of that 4 billion figure that do work, so the queens don't attack? What do you think?

is in fact only a small fraction of this

It is in fact only a small fraction of this 4 billion.

four billion there are ninety two distinct solutions ninety two out of

There are 92 distinct solutions.

four billion as a percentage is a tiny unbelievably tiny so here is one of the

Now that 92 out of 4 billion as a percentage is... tiny! Unbelievably tiny. So here is one of the solutions you could place.

solutions you could place yeah Queen here I put one here they don't attack

A queen here, I can put one here, they don't attack each other.

each other they're not on the same row they're not in the same column they're

They're not on the same row, they're not on the same column, they're not on the same diagonal.

not in the same diagonal and put a queen yeah again not in the same row column or diagonal I could put one I think down here one here and maybe I'll put one

I can put a queen here. Again, not in the same row, column or diagonal. I could put one I think down here. One here. And maybe I'll put one here.

here and here and where's I put it yeah yeah I think I

And here, and... where shall I put it? Here? Yeah.

got away with that so that would work no

And I think I got away with that. So that would work -

Queens are attacking each other now

No queens are attacking each other.

there are 92 distinct solutions that you

Now, there are 92 distinct solutions you could have.

could have that includes rotating the board and reflecting the board as well

That includes rotating the board, and reflecting the board as well.

so they're not all going to be really different some of them are just turning this 90 degrees that would count as a

So they're not all going to be really different. Some of them are just turning this 90 degrees.

solution now there are eight ways that you could rotate the board and reflect

That would count as a solution. Now, there are 8 ways that you could rotate the board and reflect it.

it for rotations and for reflections so how many actual individual ways are our

4 rotations, and 4 reflections. So, how many actual individual ways are there to do it?

letter to it there's 12 there's only 12 fundamentally different solutions 11 of

There's 12. There's only 12 fundamentally different solutions.

them have 8 reflections and rotations pictures up to 88 one of them only has 4 reflect rotations and reflections

11 of them have 8 reflections and rotations, which takes us up to 88. 1 of them only has 4 rotations and reflections

actually this one I drew this only has four different solutions because if I rotate it 180 its symmetric so that only

And it's actually this one I drew. This only has 4 different solutions, because if I rotate it 180, it's symmetric.

has four as half as many but the others

So that only has 4, that has half as many. But the others have 8.

have eight so that's ninety two distinct solutions twelve fundamentally different

So that's 92 distinct solutions. 12 fundamentally different ones.

ones so you can do this yeah you can do this with other pieces can you place

So you can do this - you can do this with other pieces.

eight nights on the board without

Can you place 8 knights on the board without attacking each other?

attacking each other I think that would be quite easy could you place eight

I think that would be quite easy.

bishops on the board without attacking

Could you place 8 bishops on the board without attacking each other?

each other I think that's quite an easy problem as well maybe or eight rooks so

I think that's quite an easy problem as well.

they get I think these are easier

Maybe 8 rooks? Again, I think these are easier problems.

problems although how many ways you can do it that's a much more interesting question how many how many different ways can you do it we'd like to thank

Although how MANY ways you can do it - that's a much more interesting question. How many different ways can you do it?

lynda.com for supporting this video

Brady: We'd like to that lynda.com for supporting this video.

Linda is a great go-to resource for learning about well all sorts of stuff

lynda.com is a great go-to resource for learning about, well, all sorts of stuff!

you can watch video courses and tutorials put together by top experts in all sorts of fields creative technology

You can watch video courses, and tutorials put together by top experts in all sorts of fields:

business I use Lynda myself especially for Photoshop any sort of trick or thing

Creative, Technology, Business. I use lynda myself, especially for photo shopping .

I can't quite figure out how to do Linda's always got a top tutorial that

Any sort of trick, or thing I can't quite figure out how to do - lynda's always got a top tutorial that teaches me how to do it.

teaches me how to do it funnily enough I was just browsing the site this week and found an amazing coincidence they have a

Funnily enough, I was just browsing the site this week and found an amazing coincidence:

course called code clinics that happens to use the 8 Queens problem it seems

They have a course called "Code Clinics" that happens to use the 8 queens problem.

this puzzle might be quite old but it's a popular aid when teaching people about

It seems this problem might be quite old, but it's a popular aid when teaching people about computer programming.

computer programming so if you're a coder why not check

So if you're a coder, why not check that one out?

on out now with over 3000 video courses and 100,000 tutorials in the vault

Now, with over 3000 video courses, and 100,000 tutorials in the vault,

Linda's a real treasure chest of skills and information and you can sign up now and get free access to all of it for 10

lynda's a real treasure chest of skills and information. And you can sign up now, and get free access to all of it for 10 days

days by going to lynda.com slash numberphile that's ly NDA comm slash numberphile oh

By going to lynda.com/numberphile

and there's also a link in the video description

Oh, and there's also a link in the video description.

our thanks to Linda for their support of numberphile

Our thanks to lynda for their support of Numberphile.

Similar videos:

The Josephus Problem - Numberphile
Numberphile
6M views 165.9K likes 2.3K dislikes 28 Oct 201636% match

The 10,958 Problem - Numberphile
Numberphile
2.9M views 48.7K likes 2.4K dislikes 18 Apr 201733% match

The Problem with 7825 - Numberphile
Numberphile
1.3M views 27.9K likes -1 dislikes 17 May 201829% match

The Uncracked Problem with 33 - Numberphile
Numberphile
1.7M views 22.7K likes 429 dislikes 06 Nov 201529% match

The Centrifuge Problem - Numberphile
Numberphile
959.5K views 25.4K likes 450 dislikes 03 Dec 201828% match

The Moving Sofa Problem - Numberphile
Numberphile
1.5M views 26.2K likes 688 dislikes 23 Mar 201728% match

Lewis Carroll's Pillow Problem - Numberphile
Numberphile
379.6K views 11.9K likes 369 dislikes 28 Apr 202027% match

Peaceable Queens - Numberphile
Numberphile
311K views 9.6K likes 100 dislikes 15 May 201926% match

The Illumination Problem - Numberphile
Numberphile
3M views 50.6K likes 1.6K dislikes 28 Feb 201726% match

Ham Sandwich Problem - Numberphile
Numberphile
884.6K views 21.3K likes 727 dislikes 15 Dec 201726% match

Nissan Juke Fuse Box Location and How to check fuses on Nissan Juke
Lurgs How To Guides
13.7K views 86 likes 5 dislikes 07 May 201825% match

Kakeya's Needle Problem - Numberphile
Numberphile
676.2K views 9.5K likes 1.4K dislikes 15 Oct 201525% match

My Aquariums powered by 12v solar power
Chickie's Solar Tech
3.8K views 13 likes 16 dislikes 15 Feb 201725% match

El problema de las 1000 reinas. ¡Un millón de dólares en juego!
Derivando
1.1M views 40.7K likes 569 dislikes 29 Sep 201725% match

Euclid's Big Problem - Numberphile
Numberphile
1.6M views 19K likes 447 dislikes 12 Dec 201424% match

Chaos Game - Numberphile
Numberphile
798.9K views 33.8K likes 168 dislikes 27 Apr 201724% match

Why is this 15-Puzzle Impossible? - Numberphile
Numberphile
881.4K views 21.2K likes -1 dislikes 21 Apr 202024% match

Stable Marriage Problem - Numberphile
Numberphile
872.6K views 12.5K likes 385 dislikes 04 Sep 201423% match

The Square-Sum Problem - Numberphile
Numberphile
532.9K views 13.3K likes 118 dislikes 11 Jan 201822% match

The Three Square Geometry Problem - Numberphile
Numberphile
1M views 18.4K likes 585 dislikes 18 Sep 201422% match

A Colorful Unsolved Problem - Numberphile
Numberphile
653.1K views 17K likes -1 dislikes 27 Feb 201922% match

Penney's Game - Numberphile
Numberphile
429.3K views 12.1K likes 81 dislikes 20 Jul 201622% match

The Prime Problem with a One Sentence Proof - Numberphile
Numberphile
368.4K views 6.7K likes 148 dislikes 18 Jul 201622% match

Mondrian Puzzle - Numberphile
Numberphile
443.9K views 8.4K likes 176 dislikes 14 Nov 201621% match

2.920050977316 - Numberphile
Numberphile
348.8K views 17.1K likes 169 dislikes 26 Nov 202021% match

The Dollar Game - Numberphile
Numberphile
637.2K views 15K likes -1 dislikes 31 Aug 201821% match

Superpermutations - Numberphile
Numberphile
348.8K views 11K likes 105 dislikes 29 Jan 201821% match

A Surprising Pi and 5 - Numberphile
Numberphile
435.7K views 15K likes 177 dislikes 31 May 202020% match

The Four 4s - Numberphile
Numberphile
1.3M views 25.5K likes 2.2K dislikes 06 Feb 201720% match

How to Win a Guessing Game - Numberphile
Numberphile
555.7K views 7.9K likes 555 dislikes 21 May 201520% match

Settings Privacy About Contact Donate