The 8 Queen Problem – Numberphile

The 8 Queen Problem – Numberphile


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.

100 thoughts on “The 8 Queen Problem – Numberphile

  1. У МЕНЯ ЕСТЬ ПОШАГОВАЯ СХЕМА РАЗМЕЩЕНИЯ НЕОГРАНИЧЕННОГО КОЛИЧЕСТВА ФЕРЗЕЙ НА ПОЛЕ ПРИ СООТВЕТСТВЕННОМ УВЕЛИЧЕНИИ КЛЕТОК ПОЛЯ ДО БЕСКОНЕЧНОСТИ! ХУСАИН ЯНДАРОВ 16.12.1956 Г.Р АВСТРИЯ ТЕЛ + 436769460971

  2. the trick you can use it that place them in a L shape (close to the way the knight/horse moves) and put one where the action is least in the chess game OR IS IT

  3. I remember working out a solution in Highschool, and found that it was actually a part of a set of solutions that were all translations of each other (assuming X and Y wrapping on the board), and then graphed out the larger repeating pattern of queens with markers for where 8×8 segments would make legal boards. There was at least one 2×3 cluster of board translations where you could shift up/down 3 times and left/right twice (or any combination) and still be assured of a legal board.

    The symmetric spirally pattern shown first in the video was NOT a part of that solution set.

  4. So I believe you can place up to 14 bishops without any of them attacking each other. Put 8 on row 1 and 8 and remove the bishops in the top left and bottom left corner.

  5. how about 8 queens each in 8 colors (64 total), such that each color doesn't attack another of the same color?

  6. You started with the factorials but actually those factorials you mentioned are C(n,k) = Combinations of 64 taken 8 = n! / ((n-k)!*k!) = 64! / (56!*8!)

  7. I don't get it🙄 let's say we get one solution of which the queen can be swapped positions….So it'll be like 8! Or where am I going😂

  8. Grime: How many ways you can rearrange the queens
    me: apply no 2 queens on the same line rule, 8! = 40320
    (Grime checks for every square)
    Grime: 64ncr8 = 4426165368
    me: ohh okay

  9. 2:37 So less than the view count of Despacito but still too much for you to list even if you listed them at a rate of one arrangement per second.

  10. This problem was mentioned in a course I had last year (well, this year since it was the spring of 2018). Although a detailed explanation of an algorithm figuring out a solution was only made for a simplified version of this, the 4 queen problem (4×4 chess board). Basically how it went was that each row could only have one queen, and then it continued case by case, always returning whenever it was impossible to place a queen, until a solution was found.

  11. Using my method: dp + dps + SPM + SP a distribution can be solved without resorting to a program although we can verify if it recovers with my GENREINA program. Now with the basic serial for the 7 families that I have discovered, all distributions from N = 4 to N = infinity are solved without the need for a program, that is, they are only listed knowing that if 100 n of the inidicada family works then for 1000n or 10000n will also work.
    The serial method I developed for 3 months, date that I found out about this challenge. I was passionate about this problem and I managed to work in it for approximately 20 hours a day

  12. If the most efficient sphere packing in dimension n=24 is only 0.19% (from Sunday's Spheres and Code Words video), can the relationship between distinct eight queens arrangements per the 4,426,165,368 ways that the eight queens can be arranged, give us an "n" dimensionality representation of the queen problem? Are there such kinds of parallels between combinatorics and studies like n-dimensional densest sphere packing?

  13. Rare that I downvote a numberphile vid. Expected more on this topic. What was in this vid could have been conveyed in 30-60 seconds comfortably.

  14. This is pretty easy I just setup a chess board and used pawns as queens and didn't put and on the same rank file or diagonal and a bit of brute Force and knowing that a queen can't attack something that's a knights move away made it really easy

  15. My solution wasn't the nice symmetrical one, but at least I got one. 🙂 Behind the read more.

    A2, B7, C3, D6, E7, F5, G1, H4

  16. its not an actuall problem worth to make a video if I solved it before watching your answer 😂

  17. We used to spice up our chess by allowing all pieces to upgrade at the opponent's rank. Bishop upgraded to cardinal and could reflect at the board edges, upgraded pawns could move backwards and explode, upgraded queens could teleport anywhere etc.

  18. There's something I don't understand about the number of placement possibilities for the 8 queens. I'm sure I'm doing it wrong, but I can't seem to crack the flaw in my reasoning.
    Basically, if you want to place 8 queens on a 64 tile board, the first queen has 64 possibilities. The second queen has 63 possibilities left as one has been taken already. The third queen has 62 possibilities, and so on until the 8th queen has 57 possibilities left.
    My reasoning would be that instead of 64! divided by 56! 8! one should come to the same solution by multiplying 64 * 63 * 62 * 61 * 60 * 59 * 58 * 57. However, this gives a result of 178,462,987,637,760.
    So please, anyone, where is my flaw? Thanks 🙂

  19. Why are you obsessed with the number 8? Because obviously you can have 14 bishops on the board without them hitting each other, 8 on one edge, 6 on the other (everything but the corners on the opposite side). 8 is just the limit with queens or rooks. The question isn't how many different ways you can do 8 with all the pieces, but how many can you have and not necessarily just 8. Obviously with queens, it makes the search much, much easier if you observe every one has to be in a different row and column, so you'll have 1 in each column, and the first one has 8 choices for its row, the 2nd one has 7 remaining choices, etcetera, so it's actually only 8! to search through or 40 thousand and that will be a fraction of a second to a computer, as opposed to searching through billions.

  20. i think for the rooks, the amount of ways you can have them placed without any being able to attack anything is 8 factorial

  21. I was surprisingly able to come up with a solution to the problem immediately after he opened up the problem. It's very simple, you just needed to apply the moves of the the knights. Because, if the knight can eat the queen, the queen wont be able to see it. This is why knights are often used for trapping 'em.

    to solve the problem, place the first queen on the upper-left corner square, then think about the possible moves of a knight in that position. Those possible moves represent the possible positions of the second queen to be placed such that both queen will be safe. Hence, put the second queen on the square that is 2 squares to the right and 1 square to the bottom. repeat this move and you will be able to place four queens safe.

    For the fifth queen, just put it one row lower than the last and one column away from the first queen. In other words, put the fifth queen on the square that is, from the first queen, one square to the right and five squares to the bottom. Now, from the fifth queen in place, repeat the pattern that applies the knight's moves, which was done to the first 4 queens.

    I hope you followed me, you would be with ease if you have with you a chess board

Leave a Reply

Your email address will not be published. Required fields are marked *