N-Queens backtraking

#algorithms #java

This is the N-Queens problem solution with a backtraking approach, look here for the N-Queens brute force approach.

If you are not familiar with the N-Queens problem look here for an explanation.

You can find the complete code for this post here: NQueensBacktracking.java.

The main difference from this one and the brute force approach is that we will check if a current permutation is a viable solution every time we add a queen, and if it’s not we will not continue pursuing that particular permutation:

static void findSolutions(LinkedHashSetWrapper perm, int n){
    if(perm.size() == n) {
        System.out.println(perm);
        return;
    }
    for(int i = 0; i < n; i++){
        if(!perm.contains(i)) {
            perm.add(i);
            if(isSolution(perm.copyInnerArray())){
                findSolutions(perm, n);
            }
            perm.removeLastElement();
        }
    }
}

In the next image you can see a solution for N = 4 (clic to enlarge)