字幕表 動画を再生する

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

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

• The standard 8 by 8 chess board, and queens.

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

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

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

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

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

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

• 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.

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

• 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 8 queens on the board? Can we?

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

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

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

• I think even Brady can do this calculation.

• How many ways can we arrange 64 objects, Brady?

• 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.

• 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.

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

• 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

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

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

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

• So we'll divide through by 8 factorial.

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

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

• 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 many solutions are there, out of that 4 billion figure that do work, so the queens don't attack? What do you think?

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

• There are 92 distinct solutions.

• Now that 92 out of 4 billion as a percentage is... tiny! Unbelievably tiny.

• So here is one of the solutions you could place.

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

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

• 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.

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

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

• No queens are attacking each other.

• Now, there are 92 distinct solutions you could have.

• 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 solution. Now, there are 8 ways that you could rotate the board and reflect it.

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

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

• 11 of them have 8 reflections and rotations, which takes us up to 88.

• 1 of them only has 4 rotations and reflections

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

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

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

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

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

• I think that would be quite easy.

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

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

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

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

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

• 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, Business. I use lynda myself, especially for photo shopping .

• 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.

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

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

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

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

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

• 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

• By going to lynda.com/numberphile

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

• Our thanks to lynda for their support of Numberphile.

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

A2 初級

8クイーン問題 - Numberphile (The 8 Queen Problem - Numberphile)

• 1 0
林宜悉 に公開 2021 年 01 月 14 日