Eight Queens Fun

[jshafferman]

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:

// 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 <iostream>

using std::cout;
using std::endl;

#include <iomanip>

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