I did this in about 20 minutes in Python in an interview. The trick to solving things fast is to use the structure of the problem to make your problem solving

I did this in about 20 minutes in Python in an interview. The trick to solving things fast is to use the structure of the problem to make your problem solving procedure less general. That is, you do premature optimization, except instead of trading readability for runtime speed, your are trading readability for program length. With real problems, there is a similar tradeoff, so I think this is a useful skill to demonstrate. But it does take practice to find the tradeoff that works best for interview questions, which is not the same as for real life coding. In my solution, I use mutable state to reduce the amount of code. board is mutated to avoid the boilerplate of copying objects. valid is mutated as a kind of optimization, but the real reason is it makes the program simpler. def complete_board(board, l): """If possible, completes a board (whose first l rows have been filled with 1 queen per row). Returns true if this is possible, false otherwise board is a list of ints representing the position (0-based) of each queen""" N = len(board) if l == N: return True # determine the valid positions for a queen in the r'th row valid = [True] * N for row, col in enumerate(board[:l]): valid[col] = False s = l - row if col + s < N: valid[col + s] = False if col - s >= 0: valid[col - s] = False for col, v in enumerate(valid): if v: board[l] = col if complete_board(board, l + 1): return True return False