The 8 Queen Problem - Numberphile

Key Takeaways

so we're gonna do one of the uh 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 eight by eight chessboard and queens so a queen if you don't know a queen is the strongest it's the best piece on a chess board because 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 and oh if there's another piece in its way it takes it haha gotcha right so that's how a queen moves diagonally up and down left and right now the puzzle is can you place eight queens on a chessboard so that none of the queens can attack each other so all the queens are safe so this wouldn't work as a placement because we've got one queen here i can take another under attack but maybe something like this would work just fine now i've only got two queens here all queens can take each other queen so the colours don't matter the question is can we place eight queens on the board can we okay well how many ways can we place eight 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 you arrange 64 objects brady 64 factorial yeah 64 factorial if you have 64 objects there are 64 factorial ways to do that which is 64 times 63 times 62 61 all the way down to one so there are 64 objects eight queens and 56 blanks but you can rearrange the blanks between themselves and it doesn't change the position on the board so when i 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 so 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 eight factorial there are eight queens and they can be swapped around between each other so we'll divide through by eight factorial so the number of ways you can arrange those eight queens naively is four billion four hundred and twenty six million one hundred and sixty five thousand three hundred and sixty eight so there are over four billion ways you can place your eight 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 four 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 92 out of 4 billion as a percentage is a tiny unbelievably tiny so here is one of the solutions you could place yeah queen here i put one here they don't attack each other they're not in the same row they're not in the same column they're not in the same diagonal and 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'd i put it here yeah i think i got away with that so that would work no queens are attacking each other now there are 92 distinct solutions that you can 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 eight ways that you could rotate the board and reflect it four rotations and four 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 eight reflections and rotations takes us up to 88 one of them only has four rotations reflections actually this one i drew this only has four different solutions because if i rotate it 180 it's symmetric so that only has four that has half as many but the others have eight so that's 92 distinct solutions 12 fundamentally different ones so you can do this yeah you can do this with other pieces uh can you place eight knights on the board without attacking each other i think that would be quite easy could you place eight bishops on the board without attacking each other i think that's quite an easy problem as well maybe oh eight rooks so they get i think these are easier problems although how many ways you can do it that's a much more interesting question how many how many different ways can you do it we'd like to thank lynda.com for supporting this video linda 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 linda myself especially for photoshop any sort of trick or thing i can't quite figure out how to do linda'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 eight queens problem it seems this puzzle 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 linda'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 that's lynda.com number five oh and there's also a link in the video description our thanks to linda for their support of numberphile