8 Queens Problem Implementation in C++ Program Problem \"Place 8 queens on an 8

Question

8 Queens Problem Implementation in C++ Program Problem "Place 8 queens on an 8 times 8 chessboard in such a way that they cannot check each other" There are totally different placement possibilities of 8 queens in the board. However with the solutions assignments (eliminating the possibilities will horizontal and vertical check), the number is reduced to 8! Design of an incremental evolutionary algorithm for the eight- queens problem. That is, a solution must represent a way to place the queens on the chess board one by one. How big is the search space in your design? A genotype is defined as 8. Randomly numbers between 1 and 16 will begenerated based on their equations (sorted according to the constant of the equation) and substitution of x=0 to 7 respectively. 8 points (x) are constructed Evaluation function is defined as: f=Max(number of equal calculated Y,8-Num of lines of "family-2" that a point is lied on) This shows Maximum number of horizontal or diagonal checks each time, the two points with the most checks will be selected as offsprings and two random lines will be replaced by two random numbers. The process will continue until f=0. Family-1 include y=x-7, y=x-6, ..., y=x-1, y=x, y=x+1, y=x+1, ..., y=x+7. Family-2 include y=-x-7, y=-x-6, ..., y =-x-1, y=-x, y=-x+1, ..., y=-x+7. BEGIN INITIALISE population with random candidate solutions; EVALUATE each candidate; REPEAT UNTIL (TERMINATION CONDITION is satisfied ) DO SELECT parents; RECOMBINE pairs of parents; MUTATE the resulting offsprings; EVALUATE new candidates; SELECT individuals for the next generation;

Explanation / Answer

Dear, #include using std::cout; using std::endl; #include using std::setw; #include #include bool queenCheck( const char [][ 8 ], int, int ); void placeQueens( char [][ 8 ] ); void printBoard( const char [][ 8 ] ); void xConflictSquares( char [][ 8 ], int, int ); void xDiagonals( char [][ 8 ], int, int ); bool availableSquare( const char [][ 8 ] ); inline int validMove( const char board[][ 8 ], int row, int col ) { return ( row >= 0 && row < 8 && col >= 0 && col < 8 ); } int main() { char board [ 8 ][ 8 ] = { '' }; srand( time( 0 ) ); placeQueens( board ); printBoard( board ); return 0; } bool availableSquare( const char board[][ 8 ] ) { for ( int row = 0; row < 8; ++row ) for ( int col = 0; col < 8; ++col ) if ( board[ row ][ col ] == '' ) return false; // at least one open square is available return true; // no available squares } void placeQueens( char board[][ 8 ] ) { const char QUEEN = 'Q'; int rowMove, colMove, queens = 0; bool done = false; while ( queens < 8 && !done ) { rowMove = rand() % 8; colMove = rand() % 8; if ( queenCheck( board, rowMove, colMove ) ) { board[ rowMove ][ colMove ] = QUEEN; xConflictSquares( board, rowMove, colMove ); ++queens; } done = availableSquare( board ); } } void xConflictSquares( char board[][ 8 ], int row, int col ) { for ( int loop = 0; loop < 8; ++loop ) { // place an '*' in the row occupied by the queen if ( board[ row ][ loop ] == '' ) board[ row ][ loop ] = '*'; // place an '*' in the col occupied by the queen if ( board[ loop ][ col ] == '' ) board[ loop ][ col ] = '*'; } // place an '*' in the diagonals occupied by the queen xDiagonals( board, row, col ); } bool queenCheck( const char board[][ 8 ], int row, int col ) { int r = row, c = col; // check row and column for a queen for ( int d = 0; d < 8; ++d ) if ( board[ row ][ d ] == 'Q' || board[ d ][ col ] == 'Q' ) return false; // check upper left diagonal for a queen for ( int e = 0; e < 8 && validMove( board, --r, --c ); ++e ) if ( board[ r ][ c ] == 'Q' ) return false; r = row; c = col; // check upper right diagonal for a queen for ( int f = 0; f < 8 && validMove( board, --r, ++c ); ++f ) if ( board[ r ][ c ] == 'Q' ) return false; r = row; c = col; // check lower left diagonal for a queen for ( int g = 0; g < 8 && validMove( board, ++r, --c ); ++g ) if (board[ r ][ c ] == 'Q' ) return false; r = row; c = col; // check lower right diagonal for a queen for ( int h = 0; h < 8 && validMove( board, ++r, ++c ); ++h ) if ( board[ r ][ c ] == 'Q' ) return false; return true; // no queen in conflict } void xDiagonals( char board[][ 8 ], int row, int col ) { int r = row, c = col; // upper left diagonal for ( int a = 0; a < 8 && validMove( board, --r, --c ); ++a ) board[ r ][ c ] = '*'; r = row; c = col; // upper right diagonal for ( int b = 0; b < 8 && validMove( board, --r, ++c ); ++b ) board[ r ][ c ] = '*'; r = row; c = col; // lower left diagonal for ( int d = 0; d < 8 && validMove( board, ++r, --c ); ++d ) board[ r ][ c ] = '*'; r = row; c = col; // lower right diagonal for ( int e = 0; e < 8 && validMove( board, ++r, ++c ); ++e ) board[ r ][ c ] = '*'; } void printBoard( const char board[][ 8 ] ) { int queens = 0; // header for columns cout

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.