[skg.sanket]

Question:
question was to solve n queen's problem using backtracking. Using recursion its easy but i am trying to explore it using without recursion.

Errors :
there is no error but some bugs are there. It is giving correct answer for some steps but when backtracking goes to last element it is not giving me correct answer.

What i am trying to do:
i am trying to solve the n queen's problem using backtracking and without recursion. In which i am first blocking the positions and then if not getting positions for next queen backtracking it by unblocking the position of previous queen. here is my code.

/*blocked= queen number
unblocked=14
queen placed=16*/

#include<iostream.h>
#include<conio.h>
#include<math.h>
#define MAX 20

void init(int);
void place(int*,int);
void block_path(int ,int ,int);
void unblock(int,int,int);
void display(int);

int board[MAX][MAX];

int main()
{
	//clrscr();
	int n;
	cout<<"\nEnter number of queens: ";
	cin>>n;
	
        init(n);
	for(int i=0;i<n;i++)
        {
            cout<<"\n"<<i<<"\n";
            place(&i,n);
            cout<<"\n"<<i<<"\n";
            display(n);
            
        }

	getch();
	return 0;
}

void init(int n)
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			board[i][j]=14;
}

void place(int *i,int n)
{
     int k,j;
     for(j=0;j<n;j++)
     {         
               if(board[(*i)][j]==14)
	       {
			board[(*i)][j]=16;
		        cout<<"\n("<<*i<<","<<j<<")";
		        block_path(*i,j,n);
			return;
	       }
	       else if(j==n-1)
               {
                        if(*i!=0)
                           *i=*i-1;
                   	for(k=0;k<n;k++)
                       	{
                        	if(board[*i][k]==16)
                        	{
                        	     unblock(*i,k,n);
                                     board[*i][k]=14;
                                     j=k;
                                     break;
                                }
                        }                
                        if(j==n-1)
                        { 
                          j=-1;
	                       if(*i==1)
                                    (*i)=0;
			
                        }                                
                 }
		
            if(*i==n-1)
                 return;	
        }
}
void block_path(int i,int j,int n)
{
	for(int p=0;p<n;p++)
	{
		if(board[i][p]==14&&board[i][p]!=16)
		{
				board[i][p]=i;
		}
		if(board[p][j]==14&&board[p][j]!=16)
        {
				board[p][j]=i;
		}
	}
	for(int q=0;q<n;q++)
	{
		for(int k=0;k<n;k++)
		{
			if(board[q][k]==14)
			{
				if(board[q][k]!=16&&q+k==i+j)
					board[q][k]=i;

			}
			if(board[q][k]==14){
				if(board[q][k]!=16&&abs(q-k)==abs(i-j))
					board[q][k]=i;
			}
		}
	}
}
void unblock(int i,int j,int n)
{
	for(int p=0;p<n;p++)
	{
		if(board[i][p]==i)
			board[i][p]=14;
		if(board[p][j]==i)
			board[p][j]=14;
	}
	for(int q=0;q<n;q++)
	{
		for(int k=0;k<n;k++)
		{
			if(board[q][k]==i&&q+k==i+j)
				board[q][k]=14;
			if(board[q][k]==i&&abs(q-k)==abs(i-j))
				board[q][k]=14;
		}
	}
		
}
void display(int n)
{
	for(int i=0;i<n;i++)
	{
		cout<<"\n";
		for(int j=0;j<n;j++)
		{
			cout<<"\t"<<board[i][j];
		}
		cout<<"\n";
	}
}

[skg.sanket]

somebody please respond..

[kevindckr]

I had turkey for dinner last night. Give me some time and I will look it over.

[jimblumberg]

In the following snippet:

   for(int i=0; i<n; i++)
   {
      cout << "\n" << i << "\n";
      place(&i,n);

Why are you passing a pointer to i into your function place()? Modifying the condition variable of a for loop in multiple places is usually not a good idea.


Please show a sample of what you input into the program and what output the program produces with this input. Also show what the program should output with the provided input.

Jim

[skg.sanket]

i am giving number of queens as input. what i am trying to do here is i am placing n queens on n X n check board such that no two queens should share same row and column and diagonal as well. so first i am initializing the board with some value that is 14 here in this code. and then trying to place queens one by one. after placing one queen i am blocking the positions for it. one more condition is there that if i am placing nth queen then it should be placed in nth row if i am not getting any position for that then i am backtracking to the previous queen and trying to change its position by placing it to the next possible position and if no position is empty then going back again and trying same till i would reach first queen. but in my code pointer is not reaching to first queen.
and i want the value of i to be changed each time i am going back so i am using pointer to i which is the only way i can reflect change to i.

after first pass(initialization):
14 14 14 14
14 14 14 14
14 14 14 14
14 14 14 14
after second pass(placing first queen): i am blocking the position of first queen that is replacing all same row and column and diagonal as well with value of the number of queen
16 0 0 0
0 0 14 14
0 14 0 14
0 14 14 0
after third pass(placing second queen):
16 0 0 0
0 0 16 1
0 1 0 1
0 14 1 0

now i am not getting any position for third queen so i am backtracking to second queen and unblocking the position for it and then placing it to next possible position which is next to previous one in this case and then trying for it.

[baavgai]

Why 16 and 14? Anyway, magic numbers are bad; start with:

const int CELL_QUEEN = 16;
const int CELL_EMPTY = 14;

It looks like you're writing C, but with some C++ mess. Get rid of Turbo C, it was probably defunct before you were born. If you have a copy of "Let Us C", burn it.

The unblock thing is tricky and error prone and I wouldn't bother. Just place the queens on your grid. Each time you attempt place another queen, do a check. Do not flag spaces as blocked, it just makes things that much more difficult for you. Just empty or queen, then check.

If you want to keep track of order of queen placement, for back track, number those. 0 for empty, first queen is 1, and so on.

Hope this helps.

[skg.sanket]

how to check that the place that we can place the next queen. is there any undo kind of thing in C++ so that we can undo to previous state. and i am using 16 and 14 because i cant use 1-9 i am placing the number of queen in there blocked positions. so 1-8 is reserved.

[baavgai]

skg.sanket, on 20 January 2012 - 09:09 AM, said:

how to check that the place that we can place the next queen.

You follow the rules. If there already a queen in the row or col or diagonal, you can't place, otherwise you can. You already have those rules, you're just marking up your board with them, which is making your job harder.

If you run over the entire board and can't place a queen, you have to back up. You then continue placing the prior queen. If you have to back up all the way to the beginning, you do so.

skg.sanket, on 20 January 2012 - 09:09 AM, said:

is there any undo kind of thing in C++ so that we can undo to previous state.

You write it.

Given your example:

initialization:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

first pass(placing first queen):
can place 0,0: true
place

after first pass:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

second pass(placing second queen):
can place 0,0: false
can place 0,1: false
can place 0,2: false
can place 0,3: false
can place 1,0: false
can place 1,1: false
can place 1,2: true
place

after second pass:
1 0 0 0
0 0 2 0
0 0 0 0
0 0 0 0

after third pass:
1 0 0 0
0 0 2 0
0 3 0 0
0 0 0 0

fouth pass:
can't place, back track
continue moving prior piece

after fouth pass:
1 0 0 0
0 0 2 0
0 0 0 0
0 3 0 0

...

Hope this helps.

[skg.sanket]

i mean is there any library function which can be used to undo things in C++

[jimblumberg]

No, there is no undo in C or C++. If you want to be able to undo something you the programmer must create data structures that remember the steps taken to get to their present state in order to return to a previous state.

Jim

[baavgai]

Short answer: No.

Long answer: How?

What I mean is, how would you set up an undo mechanism? You'd need to setup mechanism which represents the current state, save it, then repeat. The undo would be going backwards. In short, you'd pretty much have to set up everything yourself, at which point you've done the work.

For undo in a general context, you're thinking of a stack. You push items onto a stack, like state. An undo would be popping items off. Recursion actually implements this automatically using the call stack, saving the programmer the effort of implementing a data type to deal with it.

You can do what you need easily enough by making an array of placed queens, with their positions. When you hit a dead end, you pop the last pushed queen, can continue testing from the next position. If you run through all positions, pop the next queen and repeat. When you're managed to push all queens, you've found a solution.

[skg.sanket]

yes but I'll have to check it for queens already placed. how can i do that, top element will have the queen recently placed and then there is no point of popping and pushing elements from stack just for checking the positions.
it is easy to check where to place but i am checking where not to place and if any place left then placing the queen..

[baavgai]

skg.sanket, on 22 January 2012 - 12:48 AM, said:

then there is no point of popping and pushing elements

No sense in being draconian about it. The concept is important, not the structure. It's a stack, it's an array, it's both...

You do checks for the ones you've placed with a simple loop. If the you can't place another other, you remove the last one.

A framework I might use, which I believe covers all the bases, would look like:

#include <iostream>
#include <string>

struct Pos {
	int row, col;
	Pos() : row(0), col(0) { }
	Pos(int r, int c) : row(r), col(c) { }
};

class Queens {
public:
	const int N_QUEENS, ROWS, COLS;
	Queens(int n);
	~Queens();
	bool isSolved() const;
	bool solve();
	void print() const;

private:
	int placed;
	Pos *places;
	
	bool push(const Pos &);
	bool pop(Pos &);
	int getQueenAt(const Pos &) const; // 0 means none
	bool inc(Pos &) const; // moves to next pos, return false if no pos left
	bool isAvailable(const Pos &queen, const Pos &p) const; // checks if a given queen blocs a position
	bool isAvailable(const Pos &) const; // checks if any queen blocks position
};


using namespace std;

int main(){
	Queens queens(4);
	
	queens.solve();
	queens.print();
	return 0;
}


Queens::Queens(int n) : N_QUEENS(n), ROWS(n), COLS(n), placed(0), places(new Pos[n]) { }

Queens::~Queens() { delete [] places; }

bool Queens::isSolved() const { return N_QUEENS==placed; }

bool Queens::isAvailable(const Pos &p) const {
	for(int i=0; i<placed; i++) {
		if (!isAvailable(places[i], p)) { return false; }
	}
	return true;
}

// to do
bool Queens::push(const Pos &p) { return false; }
bool Queens::pop(Pos & p)  { return false; }
bool Queens::isAvailable(const Pos &queen, const Pos &p) const { return false; }
int Queens::getQueenAt(const Pos &p) const { return 0; }

bool Queens::inc(Pos &p) const { return false; }
bool Queens::solve() { return false; }
void Queens::print() const { }

Hope this helps.