n queen backtracking help...

[mimah1]

#include <iostream>

using namespace std;

char chessboard[100][100] ={' '};
int n;
int savingposition[100][2]={ };


//checking rows....
bool checking (int row, int column){
for(int i = 0; i< n; i++){
    for(int j = 0; j < n; j++) {
        if((j+i== column+row|| column - row == j-i || i== row || j == column) && chessboard[i][j]=='Q')

            return false;
            }}
    return true;
}


void displaytable()
{
    for(int i = 0; i< n; i++){
        for(int j = 0; j < n; j++) {
            if (chessboard[i][j] != 'Q')
                cout << '-'; 
            else

                cout << chessboard[i][j];
        }
        cout << endl;
    }
    for(int i = 0; i< n; i++){
        for(int j = 0; j < 2; j++) {
                //cout << savingposition[i][j];
        }
        cout << endl;
    }


}

int main()
{
    cout << "how many queens? enter from 1 to 1000-->";
    cin >>n;

        for(int row = 0; row < n; row++)
        {
            for(int column = 0; column <n; column++){
                if( checking (row,column)){

                    chessboard[row][column] = 'Q';
                     savingposition[row][0] = row;
                    savingposition[row][1] = column; break;
                    if(row < n)
                    row = row+1;
                    column = 0;
                    }
                else if(chessboard[row][column] != 'Q' && column == n ){
                    row = row-1; 
                    column = savingposition[row][1];        
                    chessboard[row][column] = '-';
                    if(column < n)
                        column = column+1; 

                }
        }
            displaytable();

        }


    return 0;   
    }

[neithan]

Is there anything you need help with?

[WaltP]

What's it do? Why did you post it? Are we supposed to be impressed or something?

[mimah1]

no!! its not working!! my backtracking is not working!!! i hope if you guys could tell me where i am doing wrong!!

[WaltP]

[boilerplate_help_info]
Posting requests for help must be well thought out if you want help quickly and correctly. Your post did not meet the criteria for quality help. You may get some posts, but are they going to be useful? Check your post with these checkpoints - what is it you missed:

1. Ask a question that can be answered. Do not ask
   -What's wrong with my code?
   -Why doesn't this work?
   -Anything else that does not give us useful information.
2. Post your code. If we don't know what you did, how can we possibly help?
   -Use PROPER FORMATTING -- see this
   -Use CODE Tags so your formatting is preserved.
   If we can't follow your code, it's difficult to help. We don't care that you're still working on it. If you want us to read it, it must be readable.
3. Explain what the code is supposed to do. If we don't know where the target is, how can we help you hit it?
4. Explain what actually happened! If we don't know where the arrow went when you shot it, how can we tell what went wrong and how far from the target you are?
5. If you have errors, post them! We can't see your screen. We can't read your mind. You need to tell us what happened.
6. Do not ask for code. We are not a coding service. We will help you fix your code.
   -If anyone posts working code for you, they are a cheater.
   -If you use that code you are a cheater.
7. Do not bore us with how new you are. We can tell by your code.
   -Do not apologize. We were all new, and unless you are completely brain dead you will get better.
   -Do not ask us to "take it easy on you."
   -Do not say "I don't know what's going on." That's obvious since you posted for help. Use that time wisely by explaining as best you can so we can help.
8. Do not apologize for posting 'late'. We don't have any expectations on when you should be posting - 10 minutes or 10 days. We aren't timing your responses.
9. Do not post your requirements and nothing else. We view that as a lazy do-nothing student that wants us to do their work for them. That's cheating and we will be hard on you.
10. Do not attach files except when absolutely necessary. Most of us are not going to download files. Add the information to your post.
11. Do not tell us how urgent it is. Seriously, for us there is no urgency at all. Many that can help will ignore any URGENT or ASAP requests.
12. Create a good title for your post. The title C++ in the C++ forum is bloody redundant and worthless! What's wrong? equally so. Specifically what are you having trouble with? There is your title. (note: my program is not the answer.)

Think more about your next post so we don't have to play 20 questions to get the info we need to help you.
[/boilerplate_help_info]

[mimah1]

else if(chessboard[row][column] != 'Q' && column == n ){
                    row = row-1; 
                    column = savingposition[row][1];        
                    chessboard[row][column] = '-';   // go back and put '-' in place of 'Q'
                    if(column < n)
                        column = column+1;   //try to check next column for 'Q'..

i am having problem at this part... the program does not go back instead moves to the next row and places Q on the next row available...leaving the whole row empty...what am i doing wrong ?

[TrustyTony]

What are you trying to do7 Can you state your logic? i think writing some functions would help to clean the code and make it readable.

[mimah1]

i am trying to show the solution for the n size chess board. however the program is not backtracking at all. i am confused on where i should be fixing ...this is what i got so far

else if(chessboard[row][column] != 'Q' && column == n ){  //if there is no place to put 'Q in the row' and the loop has reached at the end of the column
                    row = row-1;            // go back one row 
                    column = savingposition[row][1];    // the position of the last 'Q'    
                    chessboard[row][column] = '-';  // replace it with '-' in place of 'Q'
                    if(column < n)           
                        column = column+1;   // try to put 'Q'the next column if available

the problem i am having is ... instead of going back and replacing it moves to the next row available and places Q in there while leaving the row above empty

[neithan]

Hi mimah1,

First of all let me give you a couple advices so that your code is more readable and it makes it easier to detect mistakes:
1) The 'n' variable should be named something meaningful, like 'queens'
2) Avoid using magic numbers. That means that inside your functions you should not have numbers like 100 or 2 because they don't easily tell you (or the people reading your code) what they are. Instead use const variables, for example where you have:

char chessboard[100][100] ={' '};

You should have something like:

const int rows = 100, columns = 100;
char chessboard[rows][columns] ={' '};

In this subject, I would suggest changing row = row-1; for row--; and any other magic number appereance.

3) Also i would suggest initialize the chessboard to 0 (char chessboard[rows][columns] ={0};). It will help with the output format and with the checking, but maybe that's just me.

Please adapt your code and we'll see why it's not working the way you intend to. Right now i don't know why you use column = savingposition[row][1] or for(int j = 0; j < 2; j++ or int savingposition[100][2]={ };

Also why in checking() you have two nested fors checking up to 'n' which is the number of queens?

[TrustyTony]

I would use array of n with index of queen on that row, as the nature of problem states that there is only one queen per line, so every solution would be one permutation of 0..n-1.

[mimah1]

thank you for the input... i will try to fix that ..i was using the code
1. column = savingposition[row][1] or for(int j = 0; j < 2; j++ or
2. int savingposition[100][2]={ };
number 1--> to know the place of the last placed queen so that i would be able to backtrack to the last placed queen...
number 2 --> to store the location of the queen placed..
i will look at that...
can you suggest me how should i backtrack to the last queen and place Queen in the next column if there is no place in the current row?