Backtracking Flashcards
N Queens: find all the ways you can place n queens on a n * n chess board such that no two queens can attack each other
We know that in a given solution, each queen has to be in a different row, column, and negative and positive diagonal.
Indices will tell us which column and row we’re in, but what about the diagonals?
Each negative diagonal (diagonal going from top left to bottom right) has a unqiue (row - col) value that remains the same at each square in that diagonal.
For positive diagonals, we use (row + col) instead.
Our backtrack function will take in a row and find a valid position for a queen at that row. If there is one, it will place it there and recurse with row + 1.
To allow us to check if a given position is valid, we will use a hashset and keep track of each col, pos_diag, and neg_diag and we know how to represent these all numerically.
If a squares col, pos_diag, and neg_diag are unique, that is a valid spot.
So the core of this will be a loop over each column of a given row, if the square at that row and column is viable, we will place it there, update our sets, and recurse with (row + 1). You do this for each column in that row
