# N Queen II

This page explains Java solution to problem `N Queen II` using `Backtracking`.

## Problem Statement

The n-queens puzzle is the problem of placing `n` queens on an `n×n` chessboard such that no two queens attack each other.

Example 1:

Input: 4
Output: 2

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.HashSet;

class NQueensIi {

private HashSet<Integer> cols = new HashSet<>();
private HashSet<Integer> diagonals = new HashSet<>();
private HashSet<Integer> antiDiagonals = new HashSet<>();

int count = 0;
public int totalNQueens(int n) {
solve(0, n);
return count;
}

private void solve(int row, int total) {
if(row == total) count++;
else {
for(int col = 0; col < total; col++) {
if(isValid(row, col)) {

solve(row + 1, total);

cols.remove(col);
diagonals.remove(row + col);
antiDiagonals.remove(row - col);
}
}
}
}

private boolean isValid(int row, int col) {
if(cols.contains(col)) return false;
if(diagonals.contains(row + col)) return false;
if(antiDiagonals.contains(row - col)) return false;
return true;
}
}
``````

## Time Complexity

O(N!)
Where N is total number of elements in the final list and K is number of input lists.

O(N)