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.
typedef vector<vector<bool>> Board; bool Valid(int r, int c, Board &b, int n) { // check row for (int j = 0; j < n; ++j) { if (b[r][j]) return false; } // check column for (int i = 0; i < n; ++i) { if (b[i][c]) return false; } // check diagonal upper left to down right for (int c1 = c, r1 = r; c1 < n && r1 < n; c1++, r1++) { if (b[r1][c1]) return false; } for (int c1 = c, r1 = r; c1 >= 0 && r1 >= 0; c1--, r1--) { if (b[r1][c1]) return false; } // check diagonal lower left to upper right for (int c1 = c, r1 = r; c1 < n && r1 >= 0; c1++, r1--) { if (b[r1][c1]) return false; } for (int c1 = c, r1 = r; c1 >= 0 && r1 < n; c1--, r1++) { if (b[r1][c1]) return false; } return true; } bool Place(Board &b, int left, int n) { if (left == 0) return true; // all queens are placed on board for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Valid(i, j, b, n)) { b[i][j] = true; if (Place(b, left - 1, n)) { return true; } else { b[i][j] = false; } } } } return false; } void QueenSolver(Board &b, int n) { Place(b, n, n); }