deepgoyal61
BAN USERpackage com.example;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class NQueenProblem {
public Map<Integer, Integer> calculatePositions(int n) {
Map<Integer, Integer> finalMap = new HashMap<Integer, Integer>();
calculatePositions(0, n, finalMap, new HashSet<Integer>(), new HashSet<Integer>(), new HashSet<Integer>());
return finalMap;
}
private boolean calculatePositions(int row, int n, Map<Integer, Integer> finalMap, Set<Integer> usedColumnsSet,
Set<Integer> lowerPositionsSet, Set<Integer> upperPositionsSet) {
for (int column = 0; column < n; column++) {
if (usedColumnsSet.contains(column)) {
continue;
}
int lower = row + column;
if (lowerPositionsSet.contains(lower)) {
continue;
}
int subtracter = 2*column + n - 1;
int upper = subtracter - lower;
if (upperPositionsSet.contains(upper)) {
continue;
}
if (row == (n - 1)) {
finalMap.put(row, column);
return true;
}
usedColumnsSet.add(column);
lowerPositionsSet.add(lower);
upperPositionsSet.add(upper);
boolean result = calculatePositions(row + 1, n, finalMap, usedColumnsSet, lowerPositionsSet, upperPositionsSet);
if (result) {
finalMap.put(row, column);
return true;
} else {
usedColumnsSet.remove(column);
lowerPositionsSet.remove(lower);
upperPositionsSet.remove(upper);
}
}
return false;
}
public static void main(String[] args) {
NQueenProblem nQueenProblem = new NQueenProblem();
System.out.println(nQueenProblem.calculatePositions(4));
}
}
- deepgoyal61 June 05, 2016