### Eight Queens Fun

I am just going through a C++ book for fun and I have run into an issue when trying to solve the 8 Queens problem. I am able to run my program and get 7 queens on the board but the eighth queen is tripping me up!! I have used the heuristic of labeling the board spaces by putting a number at each location indicating the number of ways a queen can be placed in that location (by adding the row, column, and diagonals associated with that position). Anyway so whenever a queen is placed the rest of the row/column/diagonals become zero for any position that would be in that line of sight. Then I recalculate the remaining possible positions and find the lowest number to place the next queen in. I initially start the queen in the lowest elimination position and then continually place a queen in the lowest elimination position from here on out.

I am looking for someone to possibly explain my error or help me get to the solution.

Here is the code:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239`` ``````// Another puzzler for chess buffs is the Eight Queens problem. Simply stated: Is it possible to place eight queens on an empty // chess board so that no queen is "attacking" any other, i.e., no two queens are in the same row, the same column, or along the // same diagonal? Use the thinking developed in Exercise 4.24 to formulate a heuristic for solving the Eight Queens problem. Run // your program. (Hint: It is possible to assign a value to each square of the chess board indicating how many squares of an empty // chess board are "eliminated" if a queen is placed in that square. Each of the corners would be assigned the value 22, as in Fig // 4.31) Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be: Place the next queen in // the square with the smallest elimination number. Why is this strategy intuitively appealing? #include using std::cout; using std::endl; #include using std::setw; const int rows = 8; const int columns = 8; void placeQueens(int[][columns], int, int); void printBoard(int[][columns], int, int); bool moveToLowestEliminationNumber(int[][columns], int, int); void clearRowColumnAndDiagonal(int[][columns], int, int, int, int); void adjustValues(int[][columns], int, int); void adjustValue(int[][columns], int&, int, int, int, int); int main() { int board[rows][columns] = {{22, 21, 20, 19, 18, 17, 16, 22}, {22, 24, 24, 24, 24, 24, 24, 22}, {22, 24, 26, 26, 26, 26, 24, 22}, {22, 24, 26, 28, 28, 26, 24, 22}, {22, 24, 26, 28, 28, 26, 24, 22}, {22, 24, 26, 26, 26, 26, 24, 22}, {22, 24, 24, 24, 24, 24, 24, 22}, {22, 21, 20, 19, 18, 17, 16, 22}}; printBoard(board, rows, columns); placeQueens(board, rows, columns); printBoard(board, rows, columns); return 0; } void placeQueens(int board[][columns], int rows, int columns) { bool moveMade; bool end = false; int numberOfQueens = 0; while(!end) { moveMade = moveToLowestEliminationNumber(board, rows, columns); if(moveMade) { numberOfQueens++; if(numberOfQueens == 8) { end = true; } } else { end = true; } } } bool moveToLowestEliminationNumber(int board[][columns], int rows, int columns) { int lowestValue = 28; int lowestRowIndex = -1; int lowestColumnIndex = -1; for(int i = 0; i < rows; i++) { for(int j = 0; j < columns; j++) { int value = board[i][j]; if(value > 0 && value < lowestValue) { lowestValue = board[i][j]; lowestRowIndex = i; lowestColumnIndex = j; } } } if(lowestRowIndex != -1) { board[lowestRowIndex][lowestColumnIndex] = -1; clearRowColumnAndDiagonal(board, rows, columns, lowestRowIndex, lowestColumnIndex); adjustValues(board, rows, columns); return true; } return false; } void clearRowColumnAndDiagonal(int board[][columns], int rows, int columns, int currentRow, int currentColumn) { // clear row for(int i = 0; i < columns; i++) { if(i != currentColumn) { board[currentRow][i] = 0; } } // clear column for(int i = 0; i < rows; i++) { if(i != currentRow) { board[i][currentColumn] = 0; } } // diagonal left and up for(int i = currentRow - 1, j = currentColumn - 1; i >= 0 && j >= 0; i--, j--) { board[i][j] = 0; } // diagonal right and up for(int i = currentRow - 1, j = currentColumn + 1; i >= 0 && j < columns; i--, j++) { board[i][j] = 0; } // diagonal left and down for(int i = currentRow + 1, j = currentColumn - 1; i < rows && j >= 0; i++, j--) { board[i][j] = 0; } // diagonal right and down for(int i = currentRow + 1, j = currentColumn + 1; i < rows && j < columns; i++, j++) { board[i][j] = 0; } } void adjustValues(int board[][columns], int rows, int columns) { for(int i = 0; i < rows; i++) { for(int j = 0; j < columns; j++) { if(board[i][j] > 0) { adjustValue(board, board[i][j], rows, columns, i, j); } } } } void adjustValue(int board[][columns], int& value, int rows, int columns, int currentRow, int currentColumn) { int newValue = 0; // adjust for row for(int i = 0; i < columns; i++) { if(board[currentRow][i] > 0) { newValue++; } } // adjust for columns for(int i = 0; i < rows; i++) { if(board[i][currentColumn] > 0) { newValue++; } } // diagonal left and up for(int i = currentRow, j = currentColumn; i >= 0 && j >= 0; i--, j--) { if(board[i][j] > 0) { newValue++; } } // diagonal right and up for(int i = currentRow, j = currentColumn; i >= 0 && j < columns; i--, j++) { if(board[i][j] > 0) { newValue++; } } // diagonal left and down for(int i = currentRow, j = currentColumn; i < rows && j >= 0; i++, j--) { if(board[i][j] > 0) { newValue++; } } // diagonal right and down for(int i = currentRow, j = currentColumn; i < rows && j < columns; i++, j++) { if(board[i][j] > 0) { newValue++; } } value = newValue; } void printBoard(int board[][columns], int rows, int columns) { for(int i = 0; i < rows; i++) { for(int j = 0; j < columns; j++) { cout << setw(2) << board[i][j] << ' '; } cout << endl; } } ``````

Thanks for any help!!
Topic archived. No new replies allowed.