I've been trying for days to figure out how to place 8 queens on a chessboard without them attacking each other. I saw this puzzle in a logic class and got obsessed with it, but I can't visualize the solution or understand the strategy properly. Can someone walk me through it step by step?
The key thing is that you have to think about one queen per column, not try to place them all at once. If you guarantee that there's one queen in each column of the board, half the problem solves itself because they can't be in the same column anymore. From there on it's just a matter of making sure they don't attack each other on diagonals and rows.
The method that works best is to go column by column from left to right, and in each column try from top to bottom. You place a queen in a row, check that it doesn't attack any of the ones you've already placed (neither diagonally nor in a row), and if it doesn't work, backtrack and try the next row. For example, in column 1 you can start with the queen in row 1. In column 2 you can't put it in row 1 or on the diagonals, so you try row 3, row 4, etc. If at some column you can't find a valid spot, you backtrack to the previous column and move that queen to another row, and keep going from there.
There are several valid solutions, so there's no single correct path. The first solution you're typically going to find has the queens in positions like (1,1), (2,3), (3,5), (4,2), (5,8), (6,6), (7,4), (8,7) or something similar, depending on where you start. Patience is everything here. Some people say that drawing an actual board or using an interactive app helps a ton to visualize, because following it just mentally is pretty tedious.
Basically you have to think in terms of constraints, not positions: one queen per column (as already mentioned), one per row, and none on the diagonals. The trick that helped me was trying it with pencil and eraser instead of trying to visualize everything in your head - start with the first column at the very top, then try the second column in the second row, and when you run into a conflict (the new queen attacks an earlier one), just backtrack and move the last queen you placed to a different row, without starting from scratch.
There are multiple valid solutions, so there's no "the" correct answer - what matters is understanding that it's a problem of systematic trial and error, not inspiration. If you get stuck, graph paper and visual markers (like arrows or crosses on the diagonals) help you keep your sanity when looking at everything at once.
Log into answer.
