The 8 Queen Problem - Numberphile
HTML-код
- Опубликовано: 20 авг 2015
- Our thanks to lynda.com - use our link: www.lynda.com/numberphile
More links & stuff in full description below ↓↓↓
Dr James Grime discusses a famous chess problem - placing eight queens "safely" on a chess board.
Extra footage: • Eight Queens (extra fo...
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/stores/numberphile
Other merchandise: store.dftba.com/collections/n... 
Наука
James Grime is hands down, my favorite mathematician on this channel.
I'm stricken between Dr Grime, Matt Parker and Cliff Stoll!
+Bobby Sanchez He's awesome
***** but what are you?
Bobby Sanchez you mean singingbanana right?
Please answer the query: what are you?
Numberphile is on a chess kick. :)
Hi
Hi everyone izzzz jerry
Magnus Carlsen is World Champion from 2013 to 2020 ....but we are now in 2020....we don't know the future....
Pleasure to see you here. :)
Sup Jerry
The bane of all undergrad programming curriculae. :) Love it.
I think you meant to put ae, right?
Not sure you did, but in case you did, here's a fun fact: Both curricula or curriculums are proper for the plural form of curriculum.
yay! found you! :D
@@finchisneat Well if we go all latin, the plural of curriculum should be curricula. Even better, there isn't an ae anywhere in the declination of um. Curriculae don't exist lol.
Just for the record: Ben Finegold once converted 9 queens without mating or stalemating his opponent.
You're one of my people
I saw that one. It was funny to watch. I’m surprised that his opponent didn’t resign.
But they couldn't attack each other. Still a very fun and funny stream though
Stalin, Josef Stalin i guess the opponent figured what he was trying to do and wanted to see it happen
Very suspicious
5:45
There are 8 places you can place a rook in the first row, and after you place it you take away 1 square from all rows beneath it, so 7 options for the second row, 6 for the third... In the end there are 8! = 40320 ways to arrange 8 rooks in a chessboard, which is also an easy upper bound for the queens problem
Where did 64! Came from?
I noticed something interesting about this. All of the distinct solutions require at least a few pairs of queens to be a knight's attacking distance away from one another, yet it seems there is no solution in which every queen can be a knight's distance from another queen, the solution always requires at least one queen to not be a knight away, but rather an outlier.
If one hasn't memorized these solutions, I would think the fastest way to solve it is to start placing queens one knight's distance from one another and then fill in the gaps when it is no longer possible but you just have one or two left.
It’s very interesting, as the video started I solved it myself and this is the exact way I found a solution
You can put up to 32 knights on the board without attacking each other but all have to stay on the same colour
A knight on a dark sq will only attack light sq, so all dark sq can be filled with knights!
@@cpgautam172 I once hated the knight but as I imagine a diamond shape with different color from the Knight, its super easy 😂
you mean bishops...
@@hey_hey4394 no he doesn't.
@@hey_hey4394 Knights or bishops work because A dark squared night cant ever attack another dark square
He never gave us an algorithm for finding a solution.
On3Thought Look up the backtracking algorithm.
On3Thought Move the queens as if they are a knight while making sure that there is only one per column and row.
On3Thought Extra footage is still coming up.
PassingTimeAlong That's not guaranteed to solve the puzzle.
NFITC1
Nor is it guaranteed to end up with all the solutions.
Numbers, am I right?
Dr. Behrends There's one in the title
Dr. Behrends Maths isn't about numbers, if you think that maths is about numbers, then you probably think ...
IceNoob88 Go be pretentious somewhere else.
Dr. Behrends Dude, it was a reference to one of their video
IceNoob88 Well, guess I haven't watched that video.
I did this on professor layton
Lucky Abat I knew someone else was gonna write that xD
Same!!!
Lucky Abat I think it's also in The 7th Guest.
One of my favourite puzzles from all six games. Well, that and Princess Escape from the first, maybe.
***** Yeah, it is. Where I encountered it first.
This is actually super helpful. I'm doing a project with linear optimization with integer programming and this problem came up. I needed a quick way to understand the problem, and as always, you guys delivered a fantastic presentation. Thank you!
When I studied computer science, this problem taught us recursive procedures. It's like the backtracking solution, we wrote a procedure to find a square on a new row where that queen was not under attack. The procedure assumed the previous rows were solved. If it did find a possible square, it would call itself (that's the recursive part) and look for a square with a new queen in the next row. But if it didn't, it returned an error to the previous instance of the procedure so that instance would try another square on the previous row. Though that instance had found a possible square looking back, it learned from its child instance that that square was not valid by looking forward.
It was so fun to learn that I still remember it today. One of the many things that made me love mathematics and computers.
By the way, our little program found the 96 solutions in a few seconds using a 1981 mainframe computer.
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 8x8 segments would make legal boards. There was at least one 2x3 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.
Hmm maybe that's how chess piece moves was invented? I always wondered how the knight moves were invented. If you notice the only way the Queens could attack each other was if they could attack with the properties of the knight, which a queen cant do. Interesting indeed...
If you placed 32 knigths on the dark squares they wouldn't attack each other
a knight attacks the same squares four bishps that are 3 squares away on files and ranks from that knight would, but only the diagonals that connect the bishops and not the ones outside of them
Knight is a trully unique piece at it has power none can replicate, even the queen
I once needed to solve this problem during an actual game. Down to a single king against an opponent who wanted to embarrass me by populating the board with eight queens. My challenge simply became figuring out where to put my King such that when he crowned a new queen I'd still be safe yet I could get myself fenced in an unable to move. It was great fun to pull a draw out of certain defeat.
Holy that was cool
That's cool but it's a different problem
@@lumer2b But is it? Sure there were two more pieces one the board (the kings) and overlapping areas from the queens didn't matter but the problem was finding the hole in the opponent's setup such that the kind was safe but couldn't move due to the queens.
@@nobodyimportant72 Yes, completely different. The overlapping area of the queens is the whole problem of this video. The video is not about a king evading 8 enemy queens, but 8 queens evading each other all at once, which is much harder to do because of all the overlap.
Can you somehow get to the number 92 through algebra and calctulations?
Chvocht CZ Most likely.
Chvocht CZ for sure he did it through algorithms , but I imagine the the formula is very complicated so he chose to not show it.
+Chvocht CZ Finding all the solutions to the N Queen Problem is NP Hard. That means that the only way to count them is to run an exponential algorithm. For 8 queens, computers can easily brute-force it. But once you start getting up even to like 20 queens, it gets much harder to find all the solutions. No algorithm has been found to do it faster than exponential (doing so would show P = NP which is one of the millennium problems with a prize of a million dollars). So no, the only way to get to 92 is to search an exponentially large search space.
Chvocht CZ In short, to paraphrase Chvocht for everyone who isn't a Computer Science/Math major, you have to check all 4 billion of those combinations that the professor mentioned to get the number 92
Alex Quintero You cannot really solve this problem with 20 queens on a regular chessboard though. You'd need at least a 20x20 chessboard.
From what I can tell, this puzzle is kind of like an interesting variation on Sudoku. You can't have the same object (the queen) in the same row, column or diagonal. The only solution is to have 1 in each row, 1 in each column, and place them such that they are not in any diagonals either.
I feel like this almost helps to give you sort of an intuition for why there should be infinitely many primes, and why they thin out
Like as the board keeps filling with more and more lines, if you play on an infinite chessboard, there will still always be a place to put another queen, and it’ll usually be closer than you’d might at first expect
The solution seems pretty forward: each queen needs to be within one knight's move distance of one another. This is a common principle when checkmating with king and queen to avoid stalemating or blundering the queen.
i tried this when i saw the title but there is not enough squares so eventually ur gonna go down the board and get sniped by the first queens you placed.
Great video, please post as much as you can
Numberphile So to put the queens safe just put them in a knightish fashion (the places a knight would jump) but it seems as if the actual pattern is just one that you move up down left right and if some queen leaves the board, it appears on the other side. So could it be, that there is only one method and we are just looking at different pictures of this method, that combined will actually show you the whole structure?
You might be onto something there. It definitly works in some positions and imo they would be fundamentally similar.
More interesting question would be... how many knights you can place without attacking each other.
I suppose question about bishops is more interesting... I can think a solution to place 14
+raumaan kidwai b2 and g7 are attacking each other as well as h1 and a8
+raumaan kidwai my solution is a1-a8 and h2-h7, but that is definitely not the only possible one.
you could put them all in a line
Steven Mac that is not the best solution. Just read other replies for the answer.
I remember first learning about this puzzle when I was playing the game The 7th Guest. It was one of the puzzles in that game that I was able to solve.
Yay, another James video! He's definitely my favorite.
Or similiar task to put 5 queens on a board that they can attack any place on the board (so not a single one spot is safe from them)
So good to see this singing banana back on Numberphiles.
James is the best. He always makes me feel reassured even when I don't have a clue what he's talking about.
I love your enthusiasm.
"How many ways could you put 8 rooks though?"
[Sudoku: Invented]
One time while I was trying to solve this, I decided to use the decimal numbers you get when you divide 2 by 7 (0.2̅8̅5̅7̅1̅4̅) then put the other pieces in the spots for 6 and 3, and it worked somehow. It also worked with the decimal for 4/7. Is there any connection between the two?
What do you mean by using the decimal numbers?
+Chran6710 I'm not sure if there's any connection to the chess problem, but the decimals for sevenths are cyclic. They all contain the sequence 142857
1/7=0.142857142857...
3/7=0.428571428571...
2/7=0.285714285714...
6/7=0.857142857142...
4/7=0.571428571428...
5/7=0.714285714285...
I think he means if you go by the column from a-h, then you would (using 2/7) have queens on the square A2, B8, C5, D7, E1, F4 G6 H3
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.
I remember the class in college where we wrote a Java program to solve this problem for an n by m board with k queens. Fun times.
we solved this problem in school using java (blueJ) :D
you just need a brute force method to do it and it worked great
we made it even better by giving the opinion to resize the chessboard,
for exapmle if you have a 9 by 9 field and 9 queens there are way more solutions (exponential growth)
when we tried 20 java killed itself and everything was laggy xD
Brute force seems to be a bad idea
but there is no other way ...
Backtracking is a much better idea than brute force
EliteLiker Backtracking.
+Hee You can still call it brute force if you have backtracking. It's just a different way of traversing the solution space.
The rooks question seems quite easy.
1. Divide the chess board into columns. Each column contains exactly one rook (because you need 8 that don't cross). The placement of the rooks in each column is distinct, because there are no two rooks in the same row. We can now get all possible placements by permutating the columns, giving us 8! = 40320 distinct solutions
(there used to be a long comment here about how you can easily remove the symmetries, which turned out to be really hard. For now I used a computer to remove reflections, 90 degree rotations and 180 degree rotations of solutions, and any combination of those symmetries. The number of non-symmetrical solutions to the 8 rook problem is 5282, if my code is correct.)
For an interesting related problem, can you prove the following: When eight rooks are on the chessboard with none attacking each other, the number of rooks on light-colored squares must be an even number.
This is really useful for me!! I was wondering how to distribute native trees in order to make a forest that looks natural but does have a pattern.
James is my all-time favourite numberphile!
First time I actually knew how to do the math before he did it
HAHA! GOTCHA!
Hey I watch your videos just wanted to say thanks 🙏 for making them
The 8 queens could be phrased as how many solutions of the 8 bishops also work for the 8 rooks. With knights, you can fit 32 on a board if you use all squares of the same color, since a knight's move always moves it to a square of the opposite color of the one it's currently on.
I want to thank you for teaching me about something I have never understood, even through college, I'm 24 now and I just got to understand this problem statement 🤯. Thanks a lot!!
2.6x10^-6 %
You can actually place 32 knights on a chessboard! Can you figure out the lone unique solution?
Cubik There's 2 solutions, aren't there? :P
josh basserabie Yep! but they're reflections of each other so I specified that there was only one distinct solution :)
Cubik There are 92 *distinct* solutions to the 8 queens problem, and there are twelve *unique* solutions. So josh basserabie is correct.
Cubik I think the cool thing about that is the proof that you can't do it with 33
pinabaszfasz But Cubik originally said unique.
Great Work!!!
I tried doing this when I was a kid. Never thought of it as a puzzle, just something I did out of boredom lol.
In 1962 I was taking my first course in programming. This problem was presented. My first version took around 5 pages of FORTRAN. Since then I have learned about 30 different programming languages. I have programmed this problem in each of them as a training exercise to learn the language. My shortest program was 3 lines of SAS. C++ was about half a page of code.
Represent the board in a single 8 member list. (2,5,7,1,....) is a queen on the second row of the first column, second column 5th row, 3rd 7th row, 4th 1st row, etc. Each position is checked in turn for the next column and rejected if it is on the same row, column or diagonal as one already placed. This can be done by hand quite easily to find at least one. Elimination of the permutations ( 3 rotations, and 4 reflections on vertical, horizontal or diagonals) is straightforward on a computer.
I'm impressed that you learned so many coding languages!
George Steele So the video at the end is what YOU did?
git? :D
Wow, factorials are exciting!
(please laugh at my joke i have nothing else going for me)
Factorial(Hahaha).
Miles Aaway OMG IM DYING
WHO DID THIS😂😂💯
hey Я Ilan Zatonski let me guess, a fan of a sentient forehead?
memebiiiig boy
A Professional Comedian am i right
Interesting videos guys!
This is highly interesting to find, as I actually used this problem many years ago as a riddle for my D&D game. A chessboard with a riddle hint indicating (through deduction) that the 8 Queens need to be positioned in "positions of peace".
Let's say these pieces are all on an actual board in a given arrangement. They are each made of stone, roughly 5-9 feet high depending, and weigh a great deal. The floor is smooth so they can slide if given a proper push from one or more individuals in any direction. Any time that two of them "threaten" (even just sliding past one another mid-move), a spell or some other effect detonates causing damage.
My question is this: "Is there an algorithm that will tell you (assuming pieces must slide and cannot be picked up) that will, according to these rules - and similar to a Rubik's Cube - allow you to identify the LEAST number of "threats" invoked by slide-positioning 8 Queens to "Safe" positions from any given starting set?"
>Queens finally position not attacking each other.
>A Knight enters the board.
>Ninth queen enters the board.
how many knights can you place on a chessboard such that they are all safe
John Turner 32
32. Just put then all on the same color. The knight always switches the color it's on when it moves, so if all the knights are on the same color, none can attack each other.
John Turner you share the same name as my grandfather, funny
PokemonTom09 that awkward moment when a comment inside the thread gets more likes than the comment which started it.
That technique only finds the maximum if the chessboard is 4x4 or larger.
Concerning placement of Rooks on the board, I believe the solution would be that the first can be placed in any of 64 places, the second in anything but the 15 blocked by the first, second in any but the 15 blocked by the first or the 13 blocked by the second (not double counting the 2 spaces blocked by both of them), and so on, giving 64×49×36×25×16×9×4×1 arrangements, divided by 8! gives 40,320.
i remember during my engineering day we had to solve this n-queens problem using different strategies and write programs using those solutions. at first I thought it was pointless but since starting working for myself I did find the utility of the subject course undertaken.
I'm just guessing by I feel like the solution is releted to sudoku
I love this puzzle. First solved it in primary school haha.
Logicraft Redstone I highly doubt that...
22NightWing Depends where you were educated, I suppose.
22NightWing
I wouldn't doubt it, as the seperation is a L-shape, that of the knight's movement, that is the only thing he needs to know, then he would only need to position them with trial and error, coming to several solutions with very little time.
cha0s10242 Yes, that! xD
22NightWing if you are a chess enthusiast as a kid (many kids are, and there are in fact kids' chess tournaments), this is one of the first puzzles that you are given. And most kids can figure out a solution after some trial-and-error.
Finding efficient algorithms for solving the n-queens problems (for nXn boards) led to the discovery of GSAT a powerful general-purpose method for solving many kinds of problems.
I learned the solution to this problem back when I played "The 7th Guest." One of my favorite puzzles in the game.
Incredibly; both 4426165368 and 12 are numberwang!
The people who designed chess really must have loved them some numberwang.
All these years i still have no idea why numberwang is funny or why it's supposed to be funny.
Thaaaaaaaaats Numberwang!
Most fun computer program to write
One of my college professors did a lot of (published) work on n-queens in computer science (Dr. Tim Rolfe from EWU). Very cool
I love this kind of problems! :) (reminds me of some of the Professor Layton puzzles haha)
I never thought about the theory behind this, it's really interesting. Though practically it is quite easy to solve - place the first queen wherever and the next one a knight's jump away, then just continue this with a bit of care.
"The Queen is the strongest piece"
King: Hold my castle
Well King is the most important peace, but Queen is the strongest
I was just asked by my computer science teacher to solve this problem by an algorithm, so having seen that video some time ago I decided to watch it back again to understand it better :D
Need more new videos with James! Love the guy :)
pawns may actually be interesting. not because it is hard, because you can't rotate the board.
A bit like an easier version of Sudoku, come to think of it.
Gotta love when you make a combination calc without saying the word "combinations" at all
As a chess player, and someone who has learned the game deeply, I had this memorized before. I clicked the video to see if there were other solutions... did not disappoint
And here's the difference between mathematics and computer science:
A mathematician approaches the problem in regard of how many possible arrangements are there and how many of those are solutions,
where a computer scientist would devise an algorith to find those as quickly as possible
In a sense, computer science is to mathematics what engineering is to physics.
In order to find a solution you need to be both.
A mathematician is going to have to do some bruteforcing solutions that would be best solved with an algorithm.
A computer scientist needs to fundamentally understand the problem to write the algorithm in the first place, needing to be a mathematician in the process.
4 billion or 4 milliard?
+Da34Box 4 milliard.
James is baaack!
If your board is n times n big, and you have n many queens, when does this work? It obviously doesn't work for n=2 or n=3 but for example n=50 or bigger?
the solution is all in the Knight's movement.. niiiice
The real question is: Can you place the 8 queens in a manner that they are all attacking each other?
you can. Put them in a straight horizontal, diagonal or vertical line. They will be all atacking all
True that
Philip Pirrip No you can't
+Philip Pirip 2:59 answers your question tho'
If you want all eight queens attacking the other seven queens, just use three dimensions.
Plenty of other interesting questions you can ask on a similar vein, such as maximum number of pieces like this, or minimum number to cover every square. With queens that last one can be done with 6, but I imagine it can probably be done with less too
Regarding to that mention at the end:
The 8 Queens Problem was actually one of the first problems I learned about at school (about 2009) when we did stuff about iterative vs recursive programming.
I once made a program that solves 8 Queen problem and the Knight's tour on C language just to impress my chicks..
Number of different ways you can do 8 rooks is just 8! Pretty simple if you think about it
That was a lovely explanation of the formula for n-choose-m.
This is one of the few things I have never thought about.
8 is the maximum because there are only 8 horizontal lines, so only 1 queen per line safely.
Doesn't work
GRIME!!!!!!
ikr? I missed his videos so much
An interesting follow up question to the video: What is the minimum number of queens you need to cover each and every square on the board without anyone of the queens attacking each other? Would love if you guys make a video on this.
I needed an algo of this, a week ago
Just put them on every possible knight's move
+Ken Z That's a smart way to think about it
Yes. Because knights are the only piece in chess that can take a queen without requiring the queen to make a bad move or be forced because of a fork, pin, skewer.
COOL STORY BRO\
It's not actually that easy though.
Its definitely not that simply. Because Knights only take the piece they land on...not the ones in their path.
If they took the ones in their path it would simply be a tiling problem.
How many L's can fit on the board.
But its more complicated than that by far.
I remember trying to do this with 9 queens. It never worked :(
+Nick Brett I appreciate your ambition! :-)
That was how I was told to do it. They were mistaken on the number of queens.
+Nick Brett If you think about it, on an 8x8 board doing 9 queens is impossible since they each need at least a row and column to themselves. In smaller squares the number is even lower than that. Eg. in a 2x2 board you can only have one queen
I found that out when I tried to d it for about half an hour.
Try putting a pawn on the board first. :)
love this kind of videos ! awesome
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
I didn't watch the video after solving before hand. So, I have no idea about their solution. haha
I want to watch but i cant stand the marker sounds on the paper. please use a white board..
True that! I don't know why, but those sounds are soooo annoying!
vince1987 I love it
An easier solution to the problem.Put eight white queens wherever you want on the board since they can't attack each other.
Or just be really stubborn
I think a video about the Catenary Curve would be a good ideia =)
Back in the 1970s implementing this in ALGOLW was an exercise on the pre computer science programming class in Cambridge. If you could turn in correct solutions to about four problems of this complexity you could skip the summer school and go straight onto the comp sci tripos. I made it which meant I could go off for the summer and get a paid hardware design job.
Im triggered. "The queen is the best piece". Is that sexual harrasment? The knight is better in some cases just saying.
Jonathan Hansen ??
Queens are overrated.
Plus, it's not the best piece. What do you protect more, the Queen or the King?
Sir Gordinni Best is used as in, most powerful. Situationally, other pieces can be more powerful, but overall, the Queen takes the cake. Because the rich get richer (foods).
pawns are the best because you get 8 of them haha
The Eloquent Elephant Knights can jump over other pieces and the queen can't.
Knights > Queen
Thats a really easy puzzle to solve with back-tracking. I wrote a program for this exact problem long ago. But if you increase the size of the chessboard and the amount of queens, there is an insane amount of possiblities.
Such a video is perfect for getting people interested in math. Well done! How anyone could explain math in a more engaging manner than Dr. Grimes I don't know.
Could you do a video about Tree(3)? :)
You guys should do a video on the Banach-Tarski paradox!
what is the maximum number of knights bishops and rooks can you place on the board.
Each rook at each line. None of these can share the same row. Adding one rook will subtract one line for next combinations. Therefore number of solutions is at most 8*7*6*5*4*3*2*1, 8!. Now, considering 8 rotations and reflections, we must decrease the ceiling 8 times. Therefore there are at most 8! / 8 = 7! solutions, 5040. I haven't subtracted symmetrical solutions which have less than 8 transformations. Probably there are some.
I would like to know how to calculate the number of possible ways to arrange the Queens = 92?
Is it only by process of trial and error, or is there a mathematical reasoning behind it?