The 5-Queens Puzzle consists in placing four queens on a 5 x 5 chessboard so that no two queens can attack each other. That is, no two queens are allowed to be placed on the same row, the same column or the same diagonal.

#include  #include  #include  using namespace std; void showBoard(const vector> &board); int calculateH(const vector> &board); void move(vector> &board, int queenColumn, int queenDestRow); int evaluateSuccessor(vector> &board, int queenColumn, int queenDestRow); const int EMPTY = 0; const int QUEEN = 1; int main() { srand( (unsigned)time( NULL ) ); int row = 5; int column = 5; // declare and initialize the board vector> board(row, vector(column, EMPTY)); // hill-climbing local search // start with a random state (board configuration), with one queen in each column for (int i = 0; i < column; i++) { board[rand() % 4][i] = QUEEN; } // show the current state cerr << "Start state" << endl; showBoard(board); // Fill in this part ... // show the resulting solution cerr << "Result: h = " << calculateH(board) << endl; showBoard(board); cerr << endl; system("pause"); return 0; } // Shows the board on the screen void showBoard(const vector> &board) { int row = board.size(); int column = board[0].size(); cerr << "The current board:" << endl; for (int i = 0; i< row; i++) { for (int j = 0; j< column; j++) { if (board[i][j] == QUEEN) cerr << "Q" << " "; else cerr << "-" << " "; } cerr << endl; } } // Calculates the number of pairs of queens attacking one another // Returns the h value of the current board int calculateH(const vector> &board) { int row = board.size(); int column = board[0].size(); int result = 0; for (int col1 = 0; col1< column; col1++) { int row1, row2; for (int r = 0; r< row; r++) { if (board[r][col1] == QUEEN) { row1 = r; break; } } for (int col2 = col1+1; col2 < column; col2++) { for (int r = 0; r< row; r++) { if (board[r][col2] == QUEEN) { row2 = r; break; } } if (row2==row1 || row2-row1 == col2-col1 || row1-row2 == col2-col1) { result++; } } } return result; } // Moves the queen in column queenColumn to the row queenDestRow of the same column void move(vector> &board, int queenColumn, int queenDestRow) { int row = board.size(); int column = board[0].size(); for (int r = 0; r< row; r++) { if (r == queenDestRow) { board[r][queenColumn] = QUEEN; } else { board[r][queenColumn] = EMPTY; } } } // Calculates the number of pairs of queens attacking one another, if // the queen in column queenColumn were moved to the row queenDestRow of the same column // Returns the h value of the board if the queen were moved to the new row int evaluateSuccessor(vector> &board, int queenColumn, int queenDestRow) { int row = board.size(); int column = board[0].size(); // Remember the current row number of the queen in the column queenColumn int queenCurrentRow; for (int r = 0; r< row; r++) { if (board[r][queenColumn] == QUEEN) { queenCurrentRow = r; break; } } // Move the queen to the new row to get a successor state move(board, queenColumn, queenDestRow); // Calculate the h value of the successor state int result = calculateH(board); // Move the queen back to its previous row // Return to the current state move(board, queenColumn, queenCurrentRow); return result; }

There is only one place in the code where you have to add your own code to make this algorithm work. It says "// Fill in this part". Basically:

• Outer Loop forever:
  • Middle Loop through each column:
    • Inner Loop: For each successor of the current state (a successor is where you move one queen up or down to a different row in one column) :
      • Use evaluateSuccessor(board, ...) to get the value of the successor.
      • Find the "highest" valued successor (the successor with the smallest h value) of the current state
  • When middle loop is done, the highest valued successor is found:
    • if this value is no better than the current state (h value of current state is obtained using calculateH(board) , and remember, the smaller the h value is, the better ), stop and break the outer loop
    • else, use move(board, ...) to turn current state into that successor.

You shouldnt have to write more than 20 lines of code to make this work. Your program should output a resulting board to the screen using the given function showBoard(board). While hill-climbing local search is not complete, restarting it a few times and you should get a valid solution with h=0.