Puzzle 6: A Profusion of Queens

MIT 6.S095 Programming for the Puzzled, IAP 2018
Instructor: Srini Devadas

Can you place N queens on a board with N columns and N rows so no two queens threaten each other? The 8 queens problem on a chessboard is a special case. Prof. Devadas describes a solution to the N queens problem that uses recursive backtracking seach.

License: Creative Commons BY-NC-SA

[upup]

I love this professor so much, thanks for putting this out.. i hope you keep teaching for countless years to come

[wingon]

Back in last lecture, the 4 x 4 example, we were talking about we'd possibly have to place one of our previous queen in a different row to solve the problem. Here we are assuming that once a queen is placed in a column, we don't have to worry about it again. I understand that for each new queen we are placing in the new column, we only have to worry about it conflicting with the existing queen(s), but what if we weren't able to place a new queen in the n-th column without conflicting with some of the existing queen(s), and the possible solution could be achieved by placing one of the previous queen differently?

[mufizshaikh]

excellent explanation. for some reason, chalk and board is better than marker

[pnachtwey]

This is a classic example of where the language constrains the thought. I would use C because C can take advantage of 64 bit words. This may be possible in python.
The key to solving this problem efficiently is how you represent the board. I would not use lists or arrays. They are not efficient.
I would use a 64 bit word to represent 64 squares. Now think in terms of sets of bits. Generate an array of 64 64 bit words. Each 64 bit word represents a set a bit that can be moved to from that square. Now on can easily valid squares by finding the lowest bit set or not set. When a new square is selected, use the bit set for that square to exclude other squares by anding or oring bits. This is super efficient and easier to understand. It doesn't take 50 minutes of rambling instructor. BTW, I have never had a class in this. It is obvious. A 20 queen problem must be solved then make the bit set bigger. Now it may take more than 1 64 bit words but anding and oring bits will still be faster and simpler to implement.