# 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. Chas Larcomb says:

Reminds me of Sudoku

2. Husain Yandarov says:

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

3. Ben Dover says:

I myyyyve the queen

4. Ben Dover says:

Is he a bit queen, if you catch my drift?

5. yasir says:

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

6. The Creative Process says:

Ok, now try to putting 8 women in a 8" × 8" room without them fighting xD

7. HansLemurson says:

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.

8. Unofficial vg says:

I knew it would be similar to knight's moved

9. Suani Avila says:

They don’t work with a queen in a corner. I did that and gave up lol

10. Cole Scheer says:

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.

11. Geoffroy MB says:

He looks a bit like Prismo from Adventure Time.

12. Joshua Tommy says:

I took a shot at it and got configuration number 5.

13. Sean Magguilli says:

This is sudoku

14. Chotu Singh says:

i solved it in 1min😂

15. Chotu Singh says:

a7, b2, c4, d1, e8, f5, g3 and h6
put queens on these squares..

16. GAANE DIWANE says:

I have 12 solutions of this puzzle

17. Training Grounds says:

How many useless conjectures are there in mathematics?

18. Axel Holm says:

I can place 9 B)

L. Knight.

Makes sense.

20. Garrison Pendergrass says:

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

21. Bertold Szekeres says:

He keeps saying 4 billion but it's much more like 4 and a half billion roughly.

22. energicko says:

And I thought my mind was blown in 3D chess' queen to queen level three…

23. Yoshiyahoo says:

So 1 trillionth of a percent of the ways you can arrange 56 blanks and 8 queens are solutions, got it

If you're watching this video you are almost certainly wasting your life, speaking from experience miself.

25. Qaer Kyr says:

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!)

26. Steve Bergen says:

Almost the 'horse' movement pattern.

27. Snowflake Hub says:

Who else found the solution on their own?

28. Maichael Sorokhaibam says:

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😂

29. Smug Anime Girl says:

My gut feeling was to do "64 choose 8", I tried it in Wolfram Alpha, and you get the same amount of combinations!

30. Xanman Gaming says:

Now how many Amazons can you place on a standard chessboard without them being able to attack?

31. Chimas HW says:

Bishops and rooks are the same result?

32. A Kirigwi says:

Why 8? Can we say like, as many number of queens as possible without attacking each other?

33. Star Mayhem says:

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

34. Star the Triple Devil says:

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.

35. Star the Triple Devil says:

3:28 Thanks for reminding me how the views on my videos are basically nothing.

36. Star the Triple Devil says:

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.

37. Vaz says:

i wish he'd have mentioned how you find a solution.

I came for a NUMBA

39. hector chumpitaz says:

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

40. Noah Bryant says:

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?

Can you do the same task, but with knights

42. Hien Duong Van says:

ALL CHESS PIECES…
ARE QUEENS!!!

43. William Tseng says:

omg numberphile is terrific!!

44. Gary Lewis says:

i heard of a lisp computer program that can generate these queens positions.

45. Donaldo says:

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.

46. Alpha Beta says:

This problem reminds me of sudoku!

47. Nelson aka SpOOKY says:

solved this in prolog… ez

48. Matan Kribus says:

did it in like… under a minute.. give me a better one

49. Tiny Tim says:

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

50. Jesse Carpenter says:

That’s cool because I noticed they’re placed a Knight’s distance apart.

51. Mike McGomer says:

This was an old computer problem in a masters in the 70's

52. Alex Calinescu says:

This problem is way too simple… I was 16years old when our programming teacher told us to program this in C…

53. Null Null says:

from codejam 😀

54. Ciao! says:

Can you do a video for the solution?

55. Peref L. says:

Sudoku

56. ICY Counter-Strike and League Of Legends says:

My friend actually did this in 10 mins

57. amaan siddiqui says:

THE ACTUAL ANSWER IS …. USE ALL THE QUEENS OF SAME COLOUR AND THEY WONT ATTACK EACH OTHER …..

58. TruthNerds says:

Eight queens? Wow! Henry VIII only had six.

59. zubayedhossainkhan khanhossainzubayed says:

how did you get the number 92??

60. GMP Gaming says:

>Queens finally position not attacking each other.

>A Knight enters the board.

61. Martim Cunha Rocha says:

8 rooks would be easy, right? 8! is what I'm thinking…

62. Wayne Wallace says:

And out of all those how many of those games involve smart moves and not random crappy moves?

63. Olaf van Rijnsbergen says:

The trick is to put them a knight's move away from eachother..

64. OnlyARide says:

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

65. Cumbat says:

You've played sodoku

Now it's time for sodoku hard mode

66. pdutube says:

2:35 – 4,426,165,368 is the precise age of the Earth! Forbidden knowledge! Cthulhu rises!

67. Ιορδάνης Αρβανιτιδης says:

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

68. Eric Nickerson says:

No idea this channel had 2.8 million

69. Neon Lights says:

I knew how to solve it lol

But Numberphile is so awesome I came anyway

70. Jane Doe says:

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.

71. Aerig says:

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 🙂

72. 111 23 says:

The sound that pen makes is disgusting. Gives me shivers.

73. Spectator says:

now do 9 queens

74. I'll have to put this as a name for 3 months says:

The problem is you would have to buy 8 sets of chess to have 8 queens

75. medexamtoolsdotcom says:

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.

76. Hosaam Alama says:

Can you explain how you found out the number of distinct solutions?

77. Cameron Gray says:

Nearly 1 million views

78. Quinnen Crawford says:

You can place 8 rooks on the board exactly 5760 ways.

79. William Clark says:

I give this 3! + 3! – 2! out of 10 stars

80. to go 3Years says:

How could I know there are only 12 fundamentally different solutions?

81. TheSeri0usGuy says:

Just for the record: Ben Finegold once converted 9 queens without mating or stalemating his opponent.

82. Nathaniel Neubert says:

83. Robbie Stone says:

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

84. Citrus Sinensis says:

can this be generalized for a nxn grid

85. gameplaz says:

That was easy

86. Calisthenics 1999 says:

Can you place 8 pawns on the board without the attacking each other. That’s the real question

Ha ha gotcha!!

88. Karlnikolas Alcala says:

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

89. Lord Skeptic says:

3:29 it 0.0000020786% (rounded to the nearest 10^-10)

90. dVPulse says:

how did he work out the 92 solutions?

91. Endermage77 says:

What's the relation between n rooks + n bishops to a board of size x?

92. Jinn Bottle says:

Each has to be a Knight’s pattern of moves from every other one.

93. JustGamingChair says:

I gotta different challenge. Replace one queen with a rook and a Bishop. What’ll happen?

94. T. says:

95. Aritro Chatterjee says:

Please like my comment, I feel so lonely being the only one in my family able to play chess!

96. David Zéboulon says:

Would it be possible to make a video explaining why every Numberphile starts mid-sentence?

97. Tilok Saha says:

Can anyone tell me whats with the brown paper and why it is always torn on the side

98. John Ruben Saragi says:

0:13
King: am i a joke to you?

99. 20_Марин Христов says:

Well, because of rotating and reflecting there aren't really 4 bil, but less