Skip to content

Instantly share code, notes, and snippets.

@swarooprath
Last active March 29, 2023 07:05
Show Gist options
  • Save swarooprath/bf9eb04ae55b4585c410486add02f70c to your computer and use it in GitHub Desktop.
Save swarooprath/bf9eb04ae55b4585c410486add02f70c to your computer and use it in GitHub Desktop.
NQueen Succint Java Solution
class Solution {
private static final String DOT = ".";
private static final String Q = "Q";
public static void main(String[] args) {
var soln = new Solution().solveNQueens(8);
for (var s : soln) {
for (var r : s) {
System.out.println(r);
}
System.out.println();
System.out.println();
}
}
public List<List<String>> solveNQueens(int n) {
List<List<Integer>> results = new ArrayList<>();
generateSolutions(n, 0, new ArrayList<>(), results);
return results.stream().map(this::stringify).collect(Collectors.toList());
}
private void generateSolutions(int n, int i, List<Integer> slate, List<List<Integer>> results) {
if (i == n) {
results.add(new ArrayList<>(slate));
return;
}
for (int j=0; j<n; j++) {
if (!isAttack(slate, j)) {
slate.add(j);
generateSolutions(n, i + 1, slate, results);
slate.remove(slate.size() - 1);
}
}
}
private boolean isAttack(List<Integer> slate, int n) {
int newPos = slate.size();
for (int i = 0; i<slate.size(); i++) {
if (slate.get(i) == n || Math.abs(slate.get(i) - n) == (newPos - i)) {
return true;
}
}
return false;
}
public List<String> stringify(List<Integer> result) {
List<String> list_strings = new ArrayList<>();
int n = result.size();
for (int r : result) {
StringBuilder sb = new StringBuilder();
sb.append(DOT.repeat(r)).append(Q).append(DOT.repeat(n-r-1));
list_strings.add(sb.toString());
}
return list_strings;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment