Deciding the base condition in backtracking recursive algorithm

Question

I was solving the N Queen problem where we need to place 4 queens on a 4 X 4 chess board such that no two queens can attack each other. I tried this earlier but my approach did not involve backtracking, so I was trying again. The code snippets are

int size=4,i,j;
int arr[4][4];
int lastjindex[4]; // to store the last location which we may need to backtrack



void placeQueen(int i,int j)
{
    int availableornot=0;

    for(j=0;j<size;j++)
    {
        if(isAvailable(i,j)==1)
        {
            availableornot=1;
            break;
        }
    }

    if(availableornot==1)
    {
        arr[i][j]=1;
        lastjindex[i]=j;

        if((i+1)!=size)
        {
            placeQueen(i+1,0);
        }
    }

    else
    {
        // no column was availabe so we backtrack
        arr[i-1][lastjindex[i-1]]=0;
        placeQueen(i-1,lastjindex[i-1]+1);
    }
}

The isAvailable() method returns 1 if arr[i][j] is not under attack, else it returns 0.

int isAvailable(int i,int j)
{
    int m,n,flag=0;

    for(m=0;m<i;m++)
    {
        for(n=0;n<size;n++)
        {
            int k=abs(i-m);
            int l=abs(j-n);

            if(arr[m][j]==0 || arr[k][l]==0)
            {
                flag=1;
                break;
                // means that spot is available
            }
        }
    }
    return flag;
}

I call the above method from main as

placeQueen(0,0);

My program compiles successfully but it prints all zeroes.

Is there any problem with my recursion? Please help me correct my code as I am trying to learn how to implement backtracking algorithms!

Also I am not able to decide the base condition to end recursion. How do I choose it here?

Well, that wasn't what you were asking. You asked for the condition for ending recursion, and that's what I gave. If you understand the code that you wrote, then I'm confident that you can figure out how to test for that condition ... but I gave an explicit answer below anyway. — Jim Balter
– Jim Balter, Commented Jul 14, 2012 at 10:05

Jim Balter · Accepted Answer · 2012-07-14 10:40:17Z

1

There's no printing in the code you posted. If you print after you have backtracked, you will be back to the initial condition of no queens on the board. Print after you have placed N queens, which is also the end condition for recursion. If you only want to print one solution, exit after printing, or set a flag that tells the caller that you're done so you pop all the way out. If you print all solutions, that will include reflections and rotations. You can eliminate one axis of reflection by only placing queens within size/2 in the first level.

Also, there are some clear logic errors in you code, such as

arr[m][j]==0 || arr[k][l]==0

A queen can only be placed if it isn't attacked on the file and it isn't attacked along a diagonal. Use a debugger or add printfs to your code to trace where it is trying to place queens -- that will help you figure out what it is doing wrong.

And aside from being wrong, your isAvailable is very inefficient. You want to know if the [i,j] square is attacked along the file or a diagonal. For that you should have a single loop over the rows of the previous queens for (m = 0; m < i; m++), but you only need three tests, not a loop, to check the file and the diagonals. As soon as you find any previous queen on a file or diagonal, you're done, and the square isn't available -- return false. (And ignore people who tell you that a function should only have one return -- they are wrong, and there are lengthly discussions here at SO and even scientific studies of error rates in code that bear this out.) Only if no previous queen is found is the square available.

Your placeQueen is also wrong. For each available square on a row, you need to place a queen and then recurse, but you're just finding the first available square. And backtracking is achieved simply by removing the queen you placed and then returning ... the previous level of placeQueen will try the next available spot.

Again, trace the code to see what it's doing. And, even more importantly, think through the logic of what is needed. Write your algorithm in words, convince yourself that it will solve the problem, then write the code to carry out the algorithm.

edited Jul 14, 2012 at 10:40

answered Jul 14, 2012 at 9:45

Jim Balter

16.5k3 gold badges46 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

OneMoreError Over a year ago

Yes, I print after i have backtracked. And may be that's why I get all the zeroes. Can you please show me how to end the recursion and when to print ?

Jim Balter Over a year ago

When your if((i+1)!=size) is false, you have filled the board and it's time to print rather than trying to place another queen. However, I don't think placeQueen(i-1, ...) is right, but I haven't fully studied your code.

OneMoreError Over a year ago

I tried to print it when i+1==size. However it still does not work.

OneMoreError Over a year ago

I have been trying to fix my code for two days now. Please help me find the bug !

Jim Balter Over a year ago

I have helped. I told you how to end your recursion and when to print. I also pointed out code that looks suspicious ... since i (which should have a better name) is the number of queens placed so far, it should never decrease. The rest is up to you ... regardless of how long it takes.

|

BLUEPIXY · Accepted Answer · 2012-07-15 16:19:24Z

#include <stdio.h>

#define SIZE 4
int size=SIZE;
int arr[SIZE][SIZE] = { 0 };

void placeQueen(int col){
    int r,c;
    if(col == size){//all queen put!
        //print out
        for(r = 0;r<size;++r){
            for(c = 0;c<size;++c)
                printf("%d", arr[c][r]);
            printf("\n");
        }
        printf("\n");
        return ;
    }
    for(r=0;r<size;++r){
        if(isAvailable(col, r)==1){
            arr[col][r]=1;
            placeQueen(col+1);
            arr[col][r]=0;//reset
        }
    }
}

int isAvailable(int col,int row){
    int c;

    for(c=0;c<col;++c){
        int d = col - c;
        if(arr[c][row]==1)
            return 0;//queen already same row
        if(row+d < size && arr[c][row+d]==1 || row-d >= 0 && arr[c][row-d]==1)
            return 0;//queen already same slanting position
    }
    return 1;
}

int main(){
    placeQueen(0);
    return 0;
}

Collectives™ on Stack Overflow

Deciding the base condition in backtracking recursive algorithm

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related