Backtracking

I'm having trouble trying to figure out how to make the Eight Queens Problem where you have to insert eight queens in a 8 x 8 chess board so none of the queens are attacking each other. I'm sure I'll be using recursion and I doubt cheking the column, row and diagonals for avaibility is going to be hard, the problem is on how to make it go back and try a different row when the next queen can't be inserted in any row....maybe a for loop in the function from column 0 to column < board size...yeah, so when the for reaches the end it will return to the function and the for will try the next column.... ok I kinda have it, but how can I know when it finished? how can I make it continue searching for more solutions? not asking for the whole program here, just a couple of hints, maybe some one can point me to a good backtracking tutorial or something?

> ok I kinda have it, but how can I know when it finished?
That's easy - when 8 nested for loops (in 8 recursive calls) finish.

> how can I make it continue searching for more solutions?
By not exiting when the first one is found.

You seem to be pretty clued into what to do, so the best thing is to give it a go and see what happens.

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.

> but I cannot figure it out.
Yeah, that's called debugging.
Use a debugger to walk through the code as it runs. When the code does something unexpected, you've found a potential bug. Then you sit and think about what you're looking at to decide whether the code is wrong and/or your understanding of the problem is wrong.
Rinse and repeat until the program is working.

Clue:

At some point, you need

Code:

---

column[ col ] = AVAIBLE;
// etc
a[ row ] [ col ] = ' ';

---

to remove one queen from the board, before you place another

Yeah I forgot to remove the queen. It's still not working but I'm getting closer, let's see if I can figure it out today. Thanks for your help.

Finally got it using a counter every succesful insertion and taking one out after inserting another queen, unless the number of insertions is equal to the board size( which means all 8 insertions were succsessful ). Here's the code in case anyone cares( I doesn't look pretty right now but you'll get the idea ):

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';
                       
                        count++;

                        if ( row < BOARDSIZE - 1 )
                                insertQueen( row + 1 );       

                                if ( count == BOARDSIZE )
                                {
                                        cout << endl;
                                        print();
                                        solutions++;
                                }
                                        column[ col ] = AVAIBLE;
                                        leftDiagonal[ row + col ] = AVAIBLE;
                                        rightDiagonal[ row - col + (BOARDSIZE - 1) ] = AVAIBLE;
                                        a[ row ] [ col ] = 'x';
                                        count--;
                }
}

---

count is the counter for successful insertions... should be called success or insertions. Anyway it'll keep printing the succeful insertions of all 8 queens or if count == BOARDSIZE you could just break; from the loop and just get the very first successful insertion of the queens, solutions is just to check how many solutions there are ( which is 92, or so says my program ). Hopefully there are just 92 solutions or my program will be doing something wrong. Thanks for your help Salem.

I swear I was about to answer to someone's post but is gone now :confused: . Anyway to whoever it was, I tested the program before posting the code and it did finish, how? well you probably know by now or your post will still be here :D , after the condition of the 8 queens is met ( count == BOARDSIZE ) it adds to the solutions counter and goes to try another space for the queen, eventually the very first loop would get to the end and just exit..... hopefully you get the idea of what I'm saying cause I don't plan on giving a better explanation :) .