Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

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?

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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 ...

int D ; // the width of the grid (this should be equal to the height)

.

bool row [D] ; // rows

bool col [D] ; // columns

bool diagPos [2*D-1] ; // positive diagonal strips

bool diagNeg [2*D-1] ; // negative diagonal strips

Then, when you wish to check if a particular cell [at (x,y)] is available, you could do this:

if ( row[y] || col[x] || diagPos[x+y] || diagNeg[x+D-1-y] )

{

// it is occupied, look elsewhere

} else

{

// it is available !

}

And then, of course, if you wanted to place a queen in an available cell (x,y), you'd do something like this:

row[y] = true ;

col[x] = true ;

diagPos[x+y] = true ;

diagNeg[x+D-1-y] = true ;

This is probably the easiest way to allow you to check the availability of a particular cell, without having to do _any_ iteration !! :-)

You can then perform your annealing algorithm — for example, you may check all surrounding cells if they're available, and if so, shove a queen there, or perform some other tests to decide whether it's most suitable..

Does that help ?

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.

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..

:)

row[0]=row[1]=row[2]=row[3

col[0]=col[1]=col[2]=col[3

diagPos[1]=diagPos[2]=diag

diagNeg[1]=diagNegs[2]=dia

how would you print it?

I will do it in VBA . But i don't care about the presentation of the solution right now becuase is easy.

A queen on column n and row m could be represented by queens[n,m]=true.

Now to calculate the number of conflicts for a queen at column n and row m you can call the following function (I have not compiled this code, so try it at your own risk): :-)

//NumberOfQueens should hold the total number of queens (which is also equal to the number of rows and the number of columns)

int NumberOfConflicts (int n, int m)

{

int i,j,conflicts=0;

//To calculate conflicts on the same row

for (i=n, j=0; j<NumberOfQueens; j++)

{

if ((j!=m)&&(queens[i,j]==tru

conflicts++;

}

//To calculate conflicts on the same column

for (i=0, j=m; i<NumberOfQueens; i++)

{

if ((i!=n)&&(queens[i,j]==tru

conflicts++;

}

//To calculate conflicts on \ diagonal

if (n<m)

{

for (i=0, j=m-n; j<NumberOfQueens; i++,j++)

{

if ((i!=n)&&(queens[i,j]==tru

conflicts++;

}

}

else

{

for (i=n-m, j=0; i<NumberOfQueens; i++,j++)

{

if ((i!=n)&&(queens[i,j]==tru

conflicts++;

}

}

//To calculate conflicts on / diagonal

if (n<NumberOfQueens-m)

{

for (i=n+m, j=0; i>=0; i--;j++)

{

if ((i!=n)&&(queens[i,j]==tru

conflicts++;

}

}

else

{

for (i=NumberOfQueens-1, j=m-n; j<NumberOfQueens; i--,j++)

{

if ((i!=n)&&(queens[i,j]==tru

conflicts++;

}

}

return conflicts;

}

_______________

Nayer Naguib

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;

}

_______________

Nayer Naguib

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;

}

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialHere 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.

Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.