Optimising generic backtracking algorithm for N Queens
For my N Queens problem solver, I'm currently using backtracking and I'm reaching an average of 7ms in runtime. However, I'm looking to optimize my backtracking further so that it has a better time complexity.
public boolean solveQueen( int col) {
if(col == qColumn) {
solveQueen(col +1);
}
if(col >= board.length) {
printBoard();
System.out.println();
return true;
}
for(int i = 0; i < board.length; i++)
if(notUnderAttack(i,col))
{
placeQ(i,col);
solveQueen(col +1);
removeQ(i, col);
}
return false;
}
As well from what I read, N queens backtracking has a time complexity of O(N!) but with my backtracking, I'm skipping a column since I'm placing a queen down first so shouldn't it be O(N!-1)?
Will appreciate any feedback that comes my way ^^
java
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
add a comment |
For my N Queens problem solver, I'm currently using backtracking and I'm reaching an average of 7ms in runtime. However, I'm looking to optimize my backtracking further so that it has a better time complexity.
public boolean solveQueen( int col) {
if(col == qColumn) {
solveQueen(col +1);
}
if(col >= board.length) {
printBoard();
System.out.println();
return true;
}
for(int i = 0; i < board.length; i++)
if(notUnderAttack(i,col))
{
placeQ(i,col);
solveQueen(col +1);
removeQ(i, col);
}
return false;
}
As well from what I read, N queens backtracking has a time complexity of O(N!) but with my backtracking, I'm skipping a column since I'm placing a queen down first so shouldn't it be O(N!-1)?
Will appreciate any feedback that comes my way ^^
java
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
add a comment |
For my N Queens problem solver, I'm currently using backtracking and I'm reaching an average of 7ms in runtime. However, I'm looking to optimize my backtracking further so that it has a better time complexity.
public boolean solveQueen( int col) {
if(col == qColumn) {
solveQueen(col +1);
}
if(col >= board.length) {
printBoard();
System.out.println();
return true;
}
for(int i = 0; i < board.length; i++)
if(notUnderAttack(i,col))
{
placeQ(i,col);
solveQueen(col +1);
removeQ(i, col);
}
return false;
}
As well from what I read, N queens backtracking has a time complexity of O(N!) but with my backtracking, I'm skipping a column since I'm placing a queen down first so shouldn't it be O(N!-1)?
Will appreciate any feedback that comes my way ^^
java
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
For my N Queens problem solver, I'm currently using backtracking and I'm reaching an average of 7ms in runtime. However, I'm looking to optimize my backtracking further so that it has a better time complexity.
public boolean solveQueen( int col) {
if(col == qColumn) {
solveQueen(col +1);
}
if(col >= board.length) {
printBoard();
System.out.println();
return true;
}
for(int i = 0; i < board.length; i++)
if(notUnderAttack(i,col))
{
placeQ(i,col);
solveQueen(col +1);
removeQ(i, col);
}
return false;
}
As well from what I read, N queens backtracking has a time complexity of O(N!) but with my backtracking, I'm skipping a column since I'm placing a queen down first so shouldn't it be O(N!-1)?
Will appreciate any feedback that comes my way ^^
java
java
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
asked Jan 19 at 18:37
Julius VelvetJulius Velvet
84
84
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Your question could be interpreted in two ways. Would you like to reduce the algorithmic complexity of this problem or would you like to make it run a bit faster?
Reducing the algorithmic complexity is not going to work. The N-Queen problem is a famous problem, millions of developers have seen it by now. In order to understand better the meaning of the expression "algorithmic complexity" I suggest reading some extra material. The preface of this doc + doing the first two exercises could be a good start.
Making the application run a bit faster is doable. Knowing Java more and implementing little tricks gives you an endless source of ways to reduce a few percentages of runtime. Before you even start that you should setup a reliable test-system (for example JMH) to track your progress. You can look into object allocation details, JIT, in-lining, the size of your variables, etc. Some may be a bit scary at first, but it is a fun way to learn new things.
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fstackoverflow.com%2fquestions%2f54270196%2foptimising-generic-backtracking-algorithm-for-n-queens%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Your question could be interpreted in two ways. Would you like to reduce the algorithmic complexity of this problem or would you like to make it run a bit faster?
Reducing the algorithmic complexity is not going to work. The N-Queen problem is a famous problem, millions of developers have seen it by now. In order to understand better the meaning of the expression "algorithmic complexity" I suggest reading some extra material. The preface of this doc + doing the first two exercises could be a good start.
Making the application run a bit faster is doable. Knowing Java more and implementing little tricks gives you an endless source of ways to reduce a few percentages of runtime. Before you even start that you should setup a reliable test-system (for example JMH) to track your progress. You can look into object allocation details, JIT, in-lining, the size of your variables, etc. Some may be a bit scary at first, but it is a fun way to learn new things.
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
add a comment |
Your question could be interpreted in two ways. Would you like to reduce the algorithmic complexity of this problem or would you like to make it run a bit faster?
Reducing the algorithmic complexity is not going to work. The N-Queen problem is a famous problem, millions of developers have seen it by now. In order to understand better the meaning of the expression "algorithmic complexity" I suggest reading some extra material. The preface of this doc + doing the first two exercises could be a good start.
Making the application run a bit faster is doable. Knowing Java more and implementing little tricks gives you an endless source of ways to reduce a few percentages of runtime. Before you even start that you should setup a reliable test-system (for example JMH) to track your progress. You can look into object allocation details, JIT, in-lining, the size of your variables, etc. Some may be a bit scary at first, but it is a fun way to learn new things.
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
add a comment |
Your question could be interpreted in two ways. Would you like to reduce the algorithmic complexity of this problem or would you like to make it run a bit faster?
Reducing the algorithmic complexity is not going to work. The N-Queen problem is a famous problem, millions of developers have seen it by now. In order to understand better the meaning of the expression "algorithmic complexity" I suggest reading some extra material. The preface of this doc + doing the first two exercises could be a good start.
Making the application run a bit faster is doable. Knowing Java more and implementing little tricks gives you an endless source of ways to reduce a few percentages of runtime. Before you even start that you should setup a reliable test-system (for example JMH) to track your progress. You can look into object allocation details, JIT, in-lining, the size of your variables, etc. Some may be a bit scary at first, but it is a fun way to learn new things.
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
Your question could be interpreted in two ways. Would you like to reduce the algorithmic complexity of this problem or would you like to make it run a bit faster?
Reducing the algorithmic complexity is not going to work. The N-Queen problem is a famous problem, millions of developers have seen it by now. In order to understand better the meaning of the expression "algorithmic complexity" I suggest reading some extra material. The preface of this doc + doing the first two exercises could be a good start.
Making the application run a bit faster is doable. Knowing Java more and implementing little tricks gives you an endless source of ways to reduce a few percentages of runtime. Before you even start that you should setup a reliable test-system (for example JMH) to track your progress. You can look into object allocation details, JIT, in-lining, the size of your variables, etc. Some may be a bit scary at first, but it is a fun way to learn new things.
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
answered Jan 19 at 21:25
Gergely BacsoGergely Bacso
10.1k12852
10.1k12852
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f54270196%2foptimising-generic-backtracking-algorithm-for-n-queens%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
