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.

Input: 4
Output: 2

Solution

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

Space Complexity

O(N)