Valid N Queens

Description

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

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

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.

---

Intuition

we need to know what is the Queen.
A queen can move in any of the following direction:

• along the row in which it is currently placed
• along the column in which it is currently placed
• or along any of the diagonal direction

Implementation

import java.util.*;

class Solution {
    public boolean solve(int[][] matrix) {
        int queens = 0;
        int n = matrix.length;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (matrix[row][col] == 1) {
                    queens++;
                    if (!isOK(row, col, matrix)) {
                        return false;
                    }
                }
            }
        }
        return queens == n;
    }

    private boolean isOK(int row, int col, int[][] matrix) {
        // row
        for (int i = col + 1; i < matrix.length; i++) {
            if (matrix[row][i] == 1) {
                return false;
            }
        }
        // \
        for (int i = row + 1, j = col + 1; i < matrix.length && j < matrix[0].length; i++, j++) {
            if (matrix[i][j] == 1)
                return false;
        }

        // /
        for (int i = row + 1, j = col - 1; i < matrix.length && j >= 0; i++, j--) {
            if (matrix[i][j] == 1)
                return false;
        }
        return true;
    }
}

Time Complexity

• Time: O(n*2)
• Space: O(1)