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


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)) {
                    diagonals.add(row + col);
                    antiDiagonals.add(row - col);

                    solve(row + 1, total);

                    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

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

Space Complexity