Solved

# N queens algorithm solved with simulated annealing algorithm.

Posted on 2006-04-11
3,142 Views
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?
0
Question by:xenoula

LVL 25

Expert Comment

boolean grid [][] ;  // ?
0

Author Comment

Why i must use that tyoe of array?
0

LVL 25

Expert Comment

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

LVL 25

Assisted Solution

So, you may decide to have something like this:

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 ?
0

LVL 84

Assisted Solution

there's no particular way that you must represent the problem
you could also use
int queen[N][2];
0

Author Comment

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.

0

LVL 25

Expert Comment

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

:)
0

Author Comment

I will Spilt the points if someone else can answer my previous comment.
0

LVL 84

Assisted Solution

If you find that a solution to the 4 queens problem is
row[0]=row[1]=row[2]=row[3]=true;
col[0]=col[1]=col[2]=col[3]=true;
diagPos[1]=diagPos[2]=diagPos[4]=diagPos[5]=true;
diagNeg[1]=diagNegs[2]=diagNeg[4]=diagNeg[5]=true;
how would you print it?
0

LVL 25

Expert Comment

...with great difficulty?

<uh oh>

Surely it wouldn't get to that combination though ?
0

Author Comment

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

LVL 14

Assisted Solution

You can represent the board (a single state of the problem) using an n x n array of booleans.

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]==true))
conflicts++;
}

//To calculate conflicts on the same column

for (i=0, j=m; i<NumberOfQueens; i++)
{
if ((i!=n)&&(queens[i,j]==true))
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]==true))
conflicts++;
}
}
else
{
for (i=n-m, j=0; i<NumberOfQueens; i++,j++)
{
if ((i!=n)&&(queens[i,j]==true))
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]==true))
conflicts++;
}
}
else
{
for (i=NumberOfQueens-1, j=m-n; j<NumberOfQueens; i--,j++)
{
if ((i!=n)&&(queens[i,j]==true))
conflicts++;
}
}

return conflicts;
}

_______________

Nayer Naguib
0

LVL 84

Assisted Solution

//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;
}
0

LVL 14

Assisted Solution

ozo: Nice algorithm. However, the author is interested in knowing how many conflicts a specific queen has got rather than the total number of conflicts, so perhaps you need to modify the function so that it either calculates the number of conflicts for a given queen, or returns/fills an array of integers representing the number of conflicts that each queen has.

_______________

Nayer Naguib
0

LVL 84

Accepted Solution

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;
}
0

Author Comment

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

## Featured Post

### Suggested Solutions

Whatever be the reason, if you are working on web development side,  you will need day-today validation codes like email validation, date validation , IP address validation, phone validation on any of the edit page or say at the time of registration…
A short article about problems I had with the new location API and permissions in Marshmallow
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …