C++/8 Queens

Advertisement


Question
QUESTION: Hi

my problem is about 8 queens problem by Using an exhaustive technique,my problem is that what actually exhaustive means for choosing 8 queens in this programe,could you plz just give me hint about 'Using an exhaustive technique' and the way that these 8 queens should be choose

thanx
Bita

ANSWER: Hello Bita.

I can think of only 2 interpretations of "exhaustive". One is that your instructor wants you to find all 92 arrangements of the eight queens.

The other is that you are supposed to use an optimistic algorithm which sets a queen down on an available location, then searches in a systematic way for the next available location of the next queen until all queens are placed. When the algorithm comes to a situation where it cannot place a queen, it backtracks. It undoes the previous decision, and continues the previous search.

For example if queen 6 is placed, then the search starts for queen 7's position. If queen 7 cannot be placed, the placement for queen 6 is undone, and the search continues for a new placement of queen 6.

The key is to have a systematic search strategy.

Consider a regular chess board with rows 0 to 7 and columns 0 to 7. You can represent it with
bool board[8][8];

You know that each column can hold just 1 queen so one approach is to place a queen at column 0, place the queen at the first available row (row 0), then continue with column 1 placing a queen at the first available row so that it does not attack other queens on the board.

The algorithm is most easily implemented with a recursive function
bool queens(int col, int count);
where col is the column on which a queen is to be positioned, and count is the number of queens left. The function returns true if a successful arrangement is found, and false otherwise.

I found it useful to have a separate attacks function like this
bool attacks(int row, int col)
returning true if a queen at row,col would attack any other queen on the board.

Is that enough of a hint?

Best regards
Zlatko.

---------- FOLLOW-UP ----------

QUESTION: could you plz check out this code,when i want to print the checki in the last loop it prints that checki is NULL though i initialize it in the last loop?

could you plz tell me whats my problem?

for( int queen1 = 0 ; queen1<57 ; queen1++ )
{
checki[ m ] = queen1/8;
checkj[ m ] = queen1%8;
cout<<m<<endl;

for( int queen2 = queen1 + 1 ; queen2<58 ; queen2++ )
{
checki[ m++ ] = queen2/8;
checkj[ m ] = queen2%8;

for( int queen3 = queen2 + 1 ; queen3<59 ; queen3++ )
{
checki[ m++ ] = queen3/8;
checkj[ m ] = queen3%8;
for( int queen4 = queen3 + 1 ; queen4<60 ; queen4++ )
{
checki[ m++ ] = queen4/8;
checkj[ m ] = queen4%8;

for( int queen5 = queen4 + 1 ; queen5<61 ; queen5++ )

{
checki[ m++ ] = queen5/8;
checkj[ m ] = queen5%8;
for( int queen6 = queen5 + 1 ; queen6<62 ; queen6++ )
{
checki[ m++ ] = queen6/8;
checkj[ m ] = queen6%8;

for( int queen7 = queen6 + 1 ; queen7<63 ; queen7++ )
{
checki[ m++ ] = queen7/8;
checkj[ m ] = queen7%8;
for( int queen8 = queen7 + 1 ; queen8<64 ; queen8++ )
{
checki[ m++ ] = queen8/8;
checkj[ m ] = queen8%8;
for(int k = 0 ; k<8 ; k++)
{
cout<<"Check : "<<checki[ k ]<<" , "<<checkj[ k ]<<endl;/*<--------here is the problem when k = 7 it prints checki is NULL*/
}
obj.determine( checki , checkj );
m = 0;

system("pause");
}
}
}
}
}
}
}
}
}


thanx
Bita

Answer
Bita, I cannot say what the problem is from this code fragment. Please post the entire program.

If you think you are initializing checki in the last loop, then use a debugger or put in print statements to view the values of m.

Perhaps you intended to do the "Check" printout loop after the queen8 loop, not in it.


Best regards
Zlatko.

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Zlatko

Expertise

No longer taking questions.

Experience

No longer taking questions.

Education/Credentials
No longer taking questions.

©2016 About.com. All rights reserved.