Given a chess board NxN, place N queens in a configuration in which they are not attacking each other.
We recursively place queen on the board if it is valid to do so. The algorithm return first board configuration that it finds.
Original solution was proposed by Dijkstra using depth-first backtracking algorithm.
Note: Solutions exist for all natural numbers n with the exception of n=2 or n=3 (proof).
Despite this problem when using bruteforce is very computationally expensive, we can improve on it if we introduce additional constrains. If we assume that one (1) queen can occupy only 1 column, solution requires only 8^8 (8 to the power of 8) combinations. We can even further reduce the complexity to 8! by generating all the permutations, which are then checked one by one for diagonal attack.