Algorithm to Valid N Queens

The n queens puzzle asks to place n queens on an n×n chessboard so that no two queens are attacking each other. Given a two-dimensional integer matrix where 1 represents a queen and 0 represents an empty cell, return whether the board is valid solution to the puzzle.

Constraints
1 ≤ n ≤ 10 where n is the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5 6 7

matrix = [     [1, 0, 0, 0, 0],     [0, 0, 0, 0, 0],     [0, 0, 0, 0, 1],     [0, 0, 0, 0, 0],     [0, 0, 0, 1, 0] ]

matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

Output
false
Explanation
There are no queens on the 2nd or 4th row.

Example 2
Input

1 2 3 4 5 6 7

matrix = [     [0, 0, 0, 1, 0],     [0, 1, 0, 0, 0],     [0, 0, 0, 0, 1],     [0, 0, 1, 0, 0],     [1, 0, 0, 0, 0] ]

matrix = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0]
]

Output
true
Explanation
This is a valid n queens solution.

Validate N Queen Board

In order to be a valid N Queen Board, it needs to meet the following requirements:

• There should be exactly N queens
• Each row should have exactly 1 queen
• Each column should have exactly 1 queen
• No two queens should be on the diagonals

Therefore, we can go through each row, to find out the queen position, and if missing or more than 1 queens in the current row, we can immediate invalidate the board. Then, we need check if current queen is on the same diagonal as previous queens.

We need a vector to store the positions of queens in each row.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool validateNQueens(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return true;
    int cols = matrix[0].size();
    if (cols == 0) return true;
    vector<int> rr;
    for (int r = 0; r < rows; ++ r) {
        int x = -1;
        for (int c = 0; c < cols; ++ c) {
            if (matrix[r][c] == 1) {
                if (x != -1) return false; // more than 1 queen in current row
                x = c;
            }
        }
        if (x == -1) return false; // no queens found in current row
        for (int i = 0; i < rr.size(); ++ i) {
            if (r - i == abs(x - rr[i])) { // on diagonals 
                return false;
            }
        }
        rr.push_back(x);
    }
    return true;
}

bool validateNQueens(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return true;
    int cols = matrix[0].size();
    if (cols == 0) return true;
    vector<int> rr;
    for (int r = 0; r < rows; ++ r) {
        int x = -1;
        for (int c = 0; c < cols; ++ c) {
            if (matrix[r][c] == 1) {
                if (x != -1) return false; // more than 1 queen in current row
                x = c;
            }
        }
        if (x == -1) return false; // no queens found in current row
        for (int i = 0; i < rr.size(); ++ i) {
            if (r - i == abs(x - rr[i])) { // on diagonals 
                return false;
            }
        }
        rr.push_back(x);
    }
    return true;
}

The time complexity is O(N^2) and the space complexity is O(N).

Another solution is to use four hash sets to remember the distinct rows, columns, the rows-columns (diagonals) and rows+columns (reverse diagonals). Then the sizes of all these four sets need to be equal to the N – the number of rows/columns.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool validateNQueen(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return true;
    int cols = matrix[0].size();
    if (cols == 0) return true;
    unordered_set<int> rr, cc, dd, rd;
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            if (!matrix[r][c]) continue;
            rr.insert(r);
            cc.insert(c);
            dd.insert(r - c);
            rd.insert(r + c);
        }
    }
    return (rr.size() == cc.size()) && (cc.size() == dd.size()) && 
           (dd.size() == rd.size()) && (dd.size() == rows);
}

bool validateNQueen(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return true;
    int cols = matrix[0].size();
    if (cols == 0) return true;
    unordered_set<int> rr, cc, dd, rd;
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            if (!matrix[r][c]) continue;
            rr.insert(r);
            cc.insert(c);
            dd.insert(r - c);
            rd.insert(r + c);
        }
    }
    return (rr.size() == cc.size()) && (cc.size() == dd.size()) && 
           (dd.size() == rd.size()) && (dd.size() == rows);
}

See also: Teaching Kids Programming – Backtracking Algorithm to Solve N-Queen Problem

–EOF (The Ultimate Computing & Technology Blog) —