xenoula
asked on
N queens algorithm solved with simulated annealing algorithm.
I have to do a program that will solve the N queens problem with the simulated annealing algorthm.I don't know what data structure i must use? I will not do it with backtracking or with recurcive algorithms but with simulated annealing. Do you know how i must represent the problem?
InteractiveMind
boolean grid [][] ; // ?
ASKER
Why i must use that tyoe of array?
Well, that's how I've stored the sort of data needed for what you're doing, in order to solve similar(ish) problems before.
It allows easy access to the state of specific cells within the grid.
But I suppose that for the N queens problem, it may be more appropriate to create a data type, which represents the grid as horizontal, vertical and diagonal components.
This approach would require 4 arrays — 1 for vertical, 1 for horizontal, 2 for diagonal (positive and negative directions).
If you bear with me a moment, I'll give you a slightly more in-depth explanation of this idea of mine ...
It allows easy access to the state of specific cells within the grid.
But I suppose that for the N queens problem, it may be more appropriate to create a data type, which represents the grid as horizontal, vertical and diagonal components.
This approach would require 4 arrays — 1 for vertical, 1 for horizontal, 2 for diagonal (positive and negative directions).
If you bear with me a moment, I'll give you a slightly more in-depth explanation of this idea of mine ...
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
InteractiveMind thank you very much i will give you the points.
I think you are right in the representation of the problem.The only problem is that i want to solve the problem with simlated annealing which is not an exact algorithm . This algorithm makes random moves and improves the solution according to a objective function. That's why i need to know every queen how many conflicts has with others queens. In my algorithm i will place a Queen only in a free cell but randonly everywhere and then i will check how many conflicts i have. The next step is to calculate the objective function and change random position in the queens that are in conflict.
Thank you.
I think you are right in the representation of the problem.The only problem is that i want to solve the problem with simlated annealing which is not an exact algorithm . This algorithm makes random moves and improves the solution according to a objective function. That's why i need to know every queen how many conflicts has with others queens. In my algorithm i will place a Queen only in a free cell but randonly everywhere and then i will check how many conflicts i have. The next step is to calculate the objective function and change random position in the queens that are in conflict.
Thank you.
Don't feel that you need to close this thread yet ...
ozo could probably help you more than anyone else on this entire site with this problem... perhaps he can suggest a more suitable structure, now that you've elaborated more on the rest of your algorithm..
:)
ozo could probably help you more than anyone else on this entire site with this problem... perhaps he can suggest a more suitable structure, now that you've elaborated more on the rest of your algorithm..
:)
ASKER
I will Spilt the points if someone else can answer my previous comment.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
...with great difficulty?
<uh oh>
Surely it wouldn't get to that combination though ?
<uh oh>
Surely it wouldn't get to that combination though ?
ASKER
don't care about the presentation of the problem.
I will do it in VBA . But i don't care about the presentation of the solution right now becuase is easy.
I will do it in VBA . But i don't care about the presentation of the solution right now becuase is easy.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thank you very much OZO. You have an excellent approach and i think i will follow your advice. The only thing that worry me is if this king of data structure is suitable for all the program. :)
Here what i decided to do.
I choose to have the an array of queens
Queens[n][m];
The n represent the n queens
The m if 0 represent the row for the specific Queen
The m if 1 represent the column for the specific Queen
Am i right OZO, is this what you have in mind?
And i will use this code for the evaluate the objective function because i want to find the total number of conflicts
--------------------------
--------------------------
//with
int queen[N][2];
//you can use
int NumberOfConflicts(){
int conflicts = 0;
for( int i=0;i<N-1;i++){
for( int j=i+1;j<N;j++){
if( queen[i][0] == queen[j][0]
|| queen[i][1] == queen[j][1]
|| abs(queen[i][0] - queen[j][0]) == abs(queen[i][1] - queen[j][1])
){
conflicts++;
}
}
}
return conflicts;
}
--------------------------
--------------------------
and this code to know how many conflicts a specific queen has. I need that information becuase i want to move randomly the queens that are in conflict. more precise if a queen have more conflicts i will move it more than the others.
int NumberOfConflicts(int n){
int conflicts = -1;
int q0=queen[n][0];
int q1=queen[n][1];
for( int i=0;i<N;i++ ){
if( queen[i][0] == q0
|| queen[i][1] == q1
|| abs(queen[i][0]-q0) == abs(queen[i][1]-q1)
){
conflicts++;
}
}
}
return conflicts;
}
--------------------------
--------------------------
i will also add in the queens the something extra
The m if 3 represent the total number of conflicts for the specific Queen.
So Queens[1][3]=4
Means that the specific queen has four conflicts.
--------------------------
--------------------------
Thank you everybody for your reply it was very helpfull.I will close this to give the points but i will open a new one with the same kind of algorithm in order to give more.
Here what i decided to do.
I choose to have the an array of queens
Queens[n][m];
The n represent the n queens
The m if 0 represent the row for the specific Queen
The m if 1 represent the column for the specific Queen
Am i right OZO, is this what you have in mind?
And i will use this code for the evaluate the objective function because i want to find the total number of conflicts
--------------------------
--------------------------
//with
int queen[N][2];
//you can use
int NumberOfConflicts(){
int conflicts = 0;
for( int i=0;i<N-1;i++){
for( int j=i+1;j<N;j++){
if( queen[i][0] == queen[j][0]
|| queen[i][1] == queen[j][1]
|| abs(queen[i][0] - queen[j][0]) == abs(queen[i][1] - queen[j][1])
){
conflicts++;
}
}
}
return conflicts;
}
--------------------------
--------------------------
and this code to know how many conflicts a specific queen has. I need that information becuase i want to move randomly the queens that are in conflict. more precise if a queen have more conflicts i will move it more than the others.
int NumberOfConflicts(int n){
int conflicts = -1;
int q0=queen[n][0];
int q1=queen[n][1];
for( int i=0;i<N;i++ ){
if( queen[i][0] == q0
|| queen[i][1] == q1
|| abs(queen[i][0]-q0) == abs(queen[i][1]-q1)
){
conflicts++;
}
}
}
return conflicts;
}
--------------------------
--------------------------
i will also add in the queens the something extra
The m if 3 represent the total number of conflicts for the specific Queen.
So Queens[1][3]=4
Means that the specific queen has four conflicts.
--------------------------
--------------------------
Thank you everybody for your reply it was very helpfull.I will close this to give the points but i will open a new one with the same kind of algorithm in order to give more.