I was checking one of my old books and I see this problem is solved in the book but I don't trust this books too much, you don't get to see the output just the code and you can tell there's alot wrong with it. This is what I have:
Constructor:
Code:
Board :: Board()
: BOARDSIZE( 8 ),
AVAIBLE( true )
{
column = new bool[ BOARDSIZE ];
leftDiagonal = new bool[ (BOARDSIZE * 2) - 1 ];
rightDiagonal = new bool[ (BOARDSIZE * 2) - 1 ];
for ( int i = 0; i < BOARDSIZE; i++ )
column[ i ] = AVAIBLE;
for ( int i = 0; i < (BOARDSIZE * 2) - 1; i++ )
leftDiagonal[ i ] = rightDiagonal[ i ] = AVAIBLE;
} // end Board Constructor
Function to insert queen
Code:
void Board :: insertQueen( const int row )
{
for ( int col = 0; col < BOARDSIZE; col++ )
if ( column[ col ] == AVAIBLE &&
leftDiagonal[ row + col ] == AVAIBLE &&
rightDiagonal[ row - col + (BOARDSIZE - 1) ] == AVAIBLE )
{
column[ col ] = !AVAIBLE;
leftDiagonal[ row + col ] = !AVAIBLE;
rightDiagonal[ row - col + (BOARDSIZE - 1) ] = !AVAIBLE;
a[ row ] [ col ] = 'Q';
insertQueen( row + 1 );
break;
}
}
The oputput I'm getting with break; after insertQueen( row + 1 ); is of five queens well placed, the sixth one cannot be placed, it's supposed to backtrack and place the fith in another column but it doesn't. Without the break statement it inserts two queens in the first four rows, which is obviously ilegal because it's suppoused to be one queen per row and column. I'm sure I'm close to something here but I can't get it to work, any ideas? I went trought the function with pen and pencil, row by row, column by column it seems obvious and easy but I cannot figure it out.