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)
Download the complete code from this post here NQueensBacktracking.java.
Top comments (0)