Placeholder Image

字幕表 動画を再生する

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

  • Brady: 64 factorial.

  • 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 日
動画の中の単語