Find all N-Queens solution
up vote
1
down vote
favorite
This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE
. CORES
dictate how many concurrent threads to use.
I've seen other Java code utilising the same DFS algorithm but getting far faster results (< 1 sec for N = 15 where as my code takes about 15 secs), though they used completely bitwise operators.
How can I improve efficiency further? Is the synchronised hash set or the stringbuilder slowing the code down?
Also it's been several years since I actually coded Java so all critiques are welcome.
package nQueens;
import java.util.*;
public class NQueensRedux implements Runnable {
public static final int BOARD_SIZE = 15;
public static final int DISPLAY_LIMIT = 1;
public static final int CORES = 4;
private Set<String> solutions;
private int start, end, n;
/**
*
* @param n Board size
* @param solutions HashSet of all valid solutions
* @param start The first row on the first column to place a queen
* @param end The last row on the first column to place a queen
*/
NQueensRedux(int n, Set<String> solutions, int start, int end) {
this.solutions = solutions;
this.start = start;
this.end = end;
this.n = n;
}
public static void main(String args) {
Set<String> solutions = Collections.synchronizedSet(new HashSet<>());
ArrayList<Thread> threads = new ArrayList<>();
// Create as many threads as CORES
long startTime = System.nanoTime();
for (int i = 0; i < BOARD_SIZE; i += BOARD_SIZE / CORES) {
Thread t = new Thread(new NQueensRedux(BOARD_SIZE, solutions, i, Math.min(i + BOARD_SIZE / CORES, BOARD_SIZE)));
t.start();
threads.add(t);
}
// Wait for all threads to finish executing
try {
for (int i = 0; i < threads.size(); i++) {
threads.get(i).join();
}
} catch (InterruptedException e) {
System.out.println("Thread interrupted.");
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000000;
System.out.println("found " + solutions.size() + " solutions in " + duration + " millisecondsn");
// Print solution(s)
Iterator i = solutions.iterator();
int k = 0;
while (i.hasNext() && k < DISPLAY_LIMIT) {
String solution = (String) i.next();
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (r == solution.charAt(c)) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("");
k++;
}
}
public void run() {
// True indicates a row is occupied with a queen
BitSet rows = new BitSet(n);
// Iterate through rows between start and end in the first column placing a queen in each
for (int r = start; r < end; r++) {
StringBuilder s = new StringBuilder((char)r + "");
rows.flip(r);
bruteForce(1, s, solutions, rows);
rows.flip(r);
}
}
/**
* Recursive algorithm to do a DFS on all solutions to n-queens
*
* @param c Column to place a queen in
* @param solution String representing queen positions so far. Index is column, value is row
* @param solutions HashSet of valid solutions
* @param rows BitSet of occupied rows at column c not accounting for diagonals
*/
public void bruteForce(int c, StringBuilder solution, Set<String> solutions, BitSet rows) {
// String was chosen instead of array to avoid having to deep copy
if (c == n) {
solutions.add(solution.toString());
return;
}
// Go thru every row and if a queen can be placed, recurse for next column
for (int r = 0; r < n; r++) {
if (canPutQueen(r, c, solution, rows)) {
rows.flip(r);
// cast r to a char and append it to the solution string
solution.append((char)r);
bruteForce(c + 1, solution, solutions, rows);
rows.flip(r);
solution.setLength(solution.length() - 1);
}
}
}
public boolean canPutQueen(int r, int c, StringBuilder solution, BitSet rows) {
int queen;
// A queen can attack at most 3 squares on a previous column
// So check those 3 squares to see if a queen is there
if (rows.get(r)) return false;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == (r - i) || queen == (r + i)) return false;
}
return true;
}
}
java multithreading recursion n-queens
bumped to the homepage by Community♦ 1 min ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
1
down vote
favorite
This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE
. CORES
dictate how many concurrent threads to use.
I've seen other Java code utilising the same DFS algorithm but getting far faster results (< 1 sec for N = 15 where as my code takes about 15 secs), though they used completely bitwise operators.
How can I improve efficiency further? Is the synchronised hash set or the stringbuilder slowing the code down?
Also it's been several years since I actually coded Java so all critiques are welcome.
package nQueens;
import java.util.*;
public class NQueensRedux implements Runnable {
public static final int BOARD_SIZE = 15;
public static final int DISPLAY_LIMIT = 1;
public static final int CORES = 4;
private Set<String> solutions;
private int start, end, n;
/**
*
* @param n Board size
* @param solutions HashSet of all valid solutions
* @param start The first row on the first column to place a queen
* @param end The last row on the first column to place a queen
*/
NQueensRedux(int n, Set<String> solutions, int start, int end) {
this.solutions = solutions;
this.start = start;
this.end = end;
this.n = n;
}
public static void main(String args) {
Set<String> solutions = Collections.synchronizedSet(new HashSet<>());
ArrayList<Thread> threads = new ArrayList<>();
// Create as many threads as CORES
long startTime = System.nanoTime();
for (int i = 0; i < BOARD_SIZE; i += BOARD_SIZE / CORES) {
Thread t = new Thread(new NQueensRedux(BOARD_SIZE, solutions, i, Math.min(i + BOARD_SIZE / CORES, BOARD_SIZE)));
t.start();
threads.add(t);
}
// Wait for all threads to finish executing
try {
for (int i = 0; i < threads.size(); i++) {
threads.get(i).join();
}
} catch (InterruptedException e) {
System.out.println("Thread interrupted.");
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000000;
System.out.println("found " + solutions.size() + " solutions in " + duration + " millisecondsn");
// Print solution(s)
Iterator i = solutions.iterator();
int k = 0;
while (i.hasNext() && k < DISPLAY_LIMIT) {
String solution = (String) i.next();
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (r == solution.charAt(c)) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("");
k++;
}
}
public void run() {
// True indicates a row is occupied with a queen
BitSet rows = new BitSet(n);
// Iterate through rows between start and end in the first column placing a queen in each
for (int r = start; r < end; r++) {
StringBuilder s = new StringBuilder((char)r + "");
rows.flip(r);
bruteForce(1, s, solutions, rows);
rows.flip(r);
}
}
/**
* Recursive algorithm to do a DFS on all solutions to n-queens
*
* @param c Column to place a queen in
* @param solution String representing queen positions so far. Index is column, value is row
* @param solutions HashSet of valid solutions
* @param rows BitSet of occupied rows at column c not accounting for diagonals
*/
public void bruteForce(int c, StringBuilder solution, Set<String> solutions, BitSet rows) {
// String was chosen instead of array to avoid having to deep copy
if (c == n) {
solutions.add(solution.toString());
return;
}
// Go thru every row and if a queen can be placed, recurse for next column
for (int r = 0; r < n; r++) {
if (canPutQueen(r, c, solution, rows)) {
rows.flip(r);
// cast r to a char and append it to the solution string
solution.append((char)r);
bruteForce(c + 1, solution, solutions, rows);
rows.flip(r);
solution.setLength(solution.length() - 1);
}
}
}
public boolean canPutQueen(int r, int c, StringBuilder solution, BitSet rows) {
int queen;
// A queen can attack at most 3 squares on a previous column
// So check those 3 squares to see if a queen is there
if (rows.get(r)) return false;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == (r - i) || queen == (r + i)) return false;
}
return true;
}
}
java multithreading recursion n-queens
bumped to the homepage by Community♦ 1 min ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE
. CORES
dictate how many concurrent threads to use.
I've seen other Java code utilising the same DFS algorithm but getting far faster results (< 1 sec for N = 15 where as my code takes about 15 secs), though they used completely bitwise operators.
How can I improve efficiency further? Is the synchronised hash set or the stringbuilder slowing the code down?
Also it's been several years since I actually coded Java so all critiques are welcome.
package nQueens;
import java.util.*;
public class NQueensRedux implements Runnable {
public static final int BOARD_SIZE = 15;
public static final int DISPLAY_LIMIT = 1;
public static final int CORES = 4;
private Set<String> solutions;
private int start, end, n;
/**
*
* @param n Board size
* @param solutions HashSet of all valid solutions
* @param start The first row on the first column to place a queen
* @param end The last row on the first column to place a queen
*/
NQueensRedux(int n, Set<String> solutions, int start, int end) {
this.solutions = solutions;
this.start = start;
this.end = end;
this.n = n;
}
public static void main(String args) {
Set<String> solutions = Collections.synchronizedSet(new HashSet<>());
ArrayList<Thread> threads = new ArrayList<>();
// Create as many threads as CORES
long startTime = System.nanoTime();
for (int i = 0; i < BOARD_SIZE; i += BOARD_SIZE / CORES) {
Thread t = new Thread(new NQueensRedux(BOARD_SIZE, solutions, i, Math.min(i + BOARD_SIZE / CORES, BOARD_SIZE)));
t.start();
threads.add(t);
}
// Wait for all threads to finish executing
try {
for (int i = 0; i < threads.size(); i++) {
threads.get(i).join();
}
} catch (InterruptedException e) {
System.out.println("Thread interrupted.");
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000000;
System.out.println("found " + solutions.size() + " solutions in " + duration + " millisecondsn");
// Print solution(s)
Iterator i = solutions.iterator();
int k = 0;
while (i.hasNext() && k < DISPLAY_LIMIT) {
String solution = (String) i.next();
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (r == solution.charAt(c)) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("");
k++;
}
}
public void run() {
// True indicates a row is occupied with a queen
BitSet rows = new BitSet(n);
// Iterate through rows between start and end in the first column placing a queen in each
for (int r = start; r < end; r++) {
StringBuilder s = new StringBuilder((char)r + "");
rows.flip(r);
bruteForce(1, s, solutions, rows);
rows.flip(r);
}
}
/**
* Recursive algorithm to do a DFS on all solutions to n-queens
*
* @param c Column to place a queen in
* @param solution String representing queen positions so far. Index is column, value is row
* @param solutions HashSet of valid solutions
* @param rows BitSet of occupied rows at column c not accounting for diagonals
*/
public void bruteForce(int c, StringBuilder solution, Set<String> solutions, BitSet rows) {
// String was chosen instead of array to avoid having to deep copy
if (c == n) {
solutions.add(solution.toString());
return;
}
// Go thru every row and if a queen can be placed, recurse for next column
for (int r = 0; r < n; r++) {
if (canPutQueen(r, c, solution, rows)) {
rows.flip(r);
// cast r to a char and append it to the solution string
solution.append((char)r);
bruteForce(c + 1, solution, solutions, rows);
rows.flip(r);
solution.setLength(solution.length() - 1);
}
}
}
public boolean canPutQueen(int r, int c, StringBuilder solution, BitSet rows) {
int queen;
// A queen can attack at most 3 squares on a previous column
// So check those 3 squares to see if a queen is there
if (rows.get(r)) return false;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == (r - i) || queen == (r + i)) return false;
}
return true;
}
}
java multithreading recursion n-queens
This code is a multi-threading recursive backtracking DFS algorithm to find all solutions to the N-Queens problem. The board size is indicated by BOARD_SIZE
. CORES
dictate how many concurrent threads to use.
I've seen other Java code utilising the same DFS algorithm but getting far faster results (< 1 sec for N = 15 where as my code takes about 15 secs), though they used completely bitwise operators.
How can I improve efficiency further? Is the synchronised hash set or the stringbuilder slowing the code down?
Also it's been several years since I actually coded Java so all critiques are welcome.
package nQueens;
import java.util.*;
public class NQueensRedux implements Runnable {
public static final int BOARD_SIZE = 15;
public static final int DISPLAY_LIMIT = 1;
public static final int CORES = 4;
private Set<String> solutions;
private int start, end, n;
/**
*
* @param n Board size
* @param solutions HashSet of all valid solutions
* @param start The first row on the first column to place a queen
* @param end The last row on the first column to place a queen
*/
NQueensRedux(int n, Set<String> solutions, int start, int end) {
this.solutions = solutions;
this.start = start;
this.end = end;
this.n = n;
}
public static void main(String args) {
Set<String> solutions = Collections.synchronizedSet(new HashSet<>());
ArrayList<Thread> threads = new ArrayList<>();
// Create as many threads as CORES
long startTime = System.nanoTime();
for (int i = 0; i < BOARD_SIZE; i += BOARD_SIZE / CORES) {
Thread t = new Thread(new NQueensRedux(BOARD_SIZE, solutions, i, Math.min(i + BOARD_SIZE / CORES, BOARD_SIZE)));
t.start();
threads.add(t);
}
// Wait for all threads to finish executing
try {
for (int i = 0; i < threads.size(); i++) {
threads.get(i).join();
}
} catch (InterruptedException e) {
System.out.println("Thread interrupted.");
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1000000;
System.out.println("found " + solutions.size() + " solutions in " + duration + " millisecondsn");
// Print solution(s)
Iterator i = solutions.iterator();
int k = 0;
while (i.hasNext() && k < DISPLAY_LIMIT) {
String solution = (String) i.next();
for (int r = 0; r < BOARD_SIZE; r++) {
for (int c = 0; c < BOARD_SIZE; c++) {
if (r == solution.charAt(c)) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("");
k++;
}
}
public void run() {
// True indicates a row is occupied with a queen
BitSet rows = new BitSet(n);
// Iterate through rows between start and end in the first column placing a queen in each
for (int r = start; r < end; r++) {
StringBuilder s = new StringBuilder((char)r + "");
rows.flip(r);
bruteForce(1, s, solutions, rows);
rows.flip(r);
}
}
/**
* Recursive algorithm to do a DFS on all solutions to n-queens
*
* @param c Column to place a queen in
* @param solution String representing queen positions so far. Index is column, value is row
* @param solutions HashSet of valid solutions
* @param rows BitSet of occupied rows at column c not accounting for diagonals
*/
public void bruteForce(int c, StringBuilder solution, Set<String> solutions, BitSet rows) {
// String was chosen instead of array to avoid having to deep copy
if (c == n) {
solutions.add(solution.toString());
return;
}
// Go thru every row and if a queen can be placed, recurse for next column
for (int r = 0; r < n; r++) {
if (canPutQueen(r, c, solution, rows)) {
rows.flip(r);
// cast r to a char and append it to the solution string
solution.append((char)r);
bruteForce(c + 1, solution, solutions, rows);
rows.flip(r);
solution.setLength(solution.length() - 1);
}
}
}
public boolean canPutQueen(int r, int c, StringBuilder solution, BitSet rows) {
int queen;
// A queen can attack at most 3 squares on a previous column
// So check those 3 squares to see if a queen is there
if (rows.get(r)) return false;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == (r - i) || queen == (r + i)) return false;
}
return true;
}
}
java multithreading recursion n-queens
java multithreading recursion n-queens
edited Jul 9 at 0:06
![](https://i.stack.imgur.com/zIlNw.jpg?s=32&g=1)
![](https://i.stack.imgur.com/zIlNw.jpg?s=32&g=1)
Jamal♦
30.2k11115226
30.2k11115226
asked Jul 8 at 18:05
sth128
62
62
bumped to the homepage by Community♦ 1 min ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 1 min ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
0
down vote
The
row
conveys the information easily obtained fromsolution
, and therefore looks redundant. Consider
public boolean canPutQueen(int r, int c, StringBuilder solutions) {
int queen;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == r || queen == (r - i) || queen == (r + i))
return false;
}
return true;
}
and you may abandon
rows
altogether.
BTW, the doc comment on
rows
is very misleading:
* @param rows BitSet of occupied rows at column c not accounting for diagonals
As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.
The threads do not compete for any data, except
solutions
. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have aSet
: the algorithm produces no dupes, so a per-threadList
suffices), and let the main thread to combine them.
I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?
In any case, when in doubt, profile.
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was usingsolution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.
– sth128
Jul 10 at 13:39
add a comment |
up vote
0
down vote
I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.
For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
The
row
conveys the information easily obtained fromsolution
, and therefore looks redundant. Consider
public boolean canPutQueen(int r, int c, StringBuilder solutions) {
int queen;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == r || queen == (r - i) || queen == (r + i))
return false;
}
return true;
}
and you may abandon
rows
altogether.
BTW, the doc comment on
rows
is very misleading:
* @param rows BitSet of occupied rows at column c not accounting for diagonals
As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.
The threads do not compete for any data, except
solutions
. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have aSet
: the algorithm produces no dupes, so a per-threadList
suffices), and let the main thread to combine them.
I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?
In any case, when in doubt, profile.
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was usingsolution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.
– sth128
Jul 10 at 13:39
add a comment |
up vote
0
down vote
The
row
conveys the information easily obtained fromsolution
, and therefore looks redundant. Consider
public boolean canPutQueen(int r, int c, StringBuilder solutions) {
int queen;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == r || queen == (r - i) || queen == (r + i))
return false;
}
return true;
}
and you may abandon
rows
altogether.
BTW, the doc comment on
rows
is very misleading:
* @param rows BitSet of occupied rows at column c not accounting for diagonals
As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.
The threads do not compete for any data, except
solutions
. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have aSet
: the algorithm produces no dupes, so a per-threadList
suffices), and let the main thread to combine them.
I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?
In any case, when in doubt, profile.
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was usingsolution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.
– sth128
Jul 10 at 13:39
add a comment |
up vote
0
down vote
up vote
0
down vote
The
row
conveys the information easily obtained fromsolution
, and therefore looks redundant. Consider
public boolean canPutQueen(int r, int c, StringBuilder solutions) {
int queen;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == r || queen == (r - i) || queen == (r + i))
return false;
}
return true;
}
and you may abandon
rows
altogether.
BTW, the doc comment on
rows
is very misleading:
* @param rows BitSet of occupied rows at column c not accounting for diagonals
As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.
The threads do not compete for any data, except
solutions
. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have aSet
: the algorithm produces no dupes, so a per-threadList
suffices), and let the main thread to combine them.
I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?
In any case, when in doubt, profile.
The
row
conveys the information easily obtained fromsolution
, and therefore looks redundant. Consider
public boolean canPutQueen(int r, int c, StringBuilder solutions) {
int queen;
for (int i = 1; i <= c; i++) {
queen = solution.charAt(c - i);
if (queen == r || queen == (r - i) || queen == (r + i))
return false;
}
return true;
}
and you may abandon
rows
altogether.
BTW, the doc comment on
rows
is very misleading:
* @param rows BitSet of occupied rows at column c not accounting for diagonals
As a reviewer I had very hard time trying to understand how there might be an occupied row at the column we are working at. You surely meant attacked.
The threads do not compete for any data, except
solutions
. Notice that the per-thread sets of solutions are guaranteed to be disjoint (they surely differ at the first column). Consider each thread to work on its own set of solutions (again, there is no need to have aSet
: the algorithm produces no dupes, so a per-threadList
suffices), and let the main thread to combine them.
I don't know whether these recommendations would enhance the performance. How does a single-threaded version perform?
In any case, when in doubt, profile.
answered Jul 8 at 21:16
![](https://i.stack.imgur.com/xpA5S.jpg?s=32&g=1)
![](https://i.stack.imgur.com/xpA5S.jpg?s=32&g=1)
vnp
38.2k13096
38.2k13096
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was usingsolution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.
– sth128
Jul 10 at 13:39
add a comment |
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was usingsolution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.
– sth128
Jul 10 at 13:39
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was using
solution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.– sth128
Jul 10 at 13:39
Yes I should have termed it "attacked" and not "occupied". The BitSet was added to enhance performance. I was using
solution
to check squares being attacked however using the BitSet reduces O(n) to O(1) at least if the Queens were Rooks. I actually wanted to find a way to include all the attacked diagonals in the BitSet as well but I can't think of an efficient way to do it. A single thread runs for about a minute compared to the 15 seconds in multi-threading. I will try simply not having a sync set. Thanks.– sth128
Jul 10 at 13:39
add a comment |
up vote
0
down vote
I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.
For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.
add a comment |
up vote
0
down vote
I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.
For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.
add a comment |
up vote
0
down vote
up vote
0
down vote
I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.
For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.
I'd suggest to do not use StringBuilder as a source of data - it could be replaced with List or even plain arrays because StringBuilder-s used to invoke charAt(idx) and then some if comparing obtained char as int.
For me usage of number of CORES (I assume it will not be hardcoded but obtained from system props) is a kind of bad practice. You think that if you start as many threads as number of cores than all these threads will run in parallel and all of them will do calculations at the same time and you will get the result as soon as possible. Such assumptions are not correct because does not take into account thread scheduling on OS and hardware level which indeed exists and sometimes has much bigger impact on overall performance than code constructions you wrote. I strongly suggest to consider Fork/Join methodology in case you use Java modern enough.
answered Jul 8 at 21:41
![](https://lh4.googleusercontent.com/-jFCapbY7yck/AAAAAAAAAAI/AAAAAAAAAAA/0AmbrJe3A0w/photo.jpg?sz=32)
![](https://lh4.googleusercontent.com/-jFCapbY7yck/AAAAAAAAAAI/AAAAAAAAAAA/0AmbrJe3A0w/photo.jpg?sz=32)
Alex Zherebtsov
1
1
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f198093%2ffind-all-n-queens-solution%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown