Eight queens using stacks instead of recursion

[cfanatic]

Hey all, I been reading through these forums for a long time but have
never posted. Well, I got a dillema. I have a program of the Eight
Queen's program and I have to make it work without recursion. I have to
use a stack instead. It's been buggin me for a week and I have no clue
how to start it. Do you guy think you can help me out?



Here is the recursive part of the program:

size_t continue_placement(Board &board, size_t num_queens, long
int &steps)

// Assumes that bd contains num_queens queens, and is shadowed

// accordingly.

// Returns the number of queens it could place.

// A -1 in a board position q will show that there is a queen on q.

{

// Entry 1: start

size_t n = board.size;

if (n == num_queens) return num_queens;



// Display the board after every 10000 recursive calls.

steps++;

if (0 == steps % 10000) {

cerr << steps << endl;

board.display(cerr);

}



size_t max_num_queens = num_queens;

Board:osition q(n); // = (0, 0)

// Entry 2: start the loop with a loop test.

while(q.is_legal()){

if (0 == board.get(q)) {

// add new queen

board.set(q, -1);

board.queen_shadow(q, 1);



size_t new_max =
continue_placement(board,num_queens+1, steps);

// Entry 3: return from recursive call

if (new_max > max_num_queens)

max_num_queens = new_max;

if (n == max_num_queens)

return max_num_queens;

else{

// remove the new queen

board.queen_shadow(q, -1);

board.set(q, 0);

}

}

// Entry 4: we jumped here if 0 != board.get(q).

q = q.next();

}

// Entry 5: get here if the loop test fails.

return max_num_queens;

}

 

[Victor Bazarov]

Hey all, I been reading through these forums for a long time but have
never posted. Well, I got a dillema. I have a program of the Eight
Queen's program and I have to make it work without recursion. I have to
use a stack instead. It's been buggin me for a week and I have no clue
how to start it. Do you guy think you can help me out?

Instead of calling your function recursively, push the state of the
data onto the stack and do another iteration. On every iteration
use the top of the stack as your current state. When the iteration
is complete, pop the stack. Do so until done.

BTW, this is not a C++ language issue.

Victor

 

[Ron Natalie]

Hey all, I been reading through these forums for a long time but have
never posted. Well, I got a dillema. I have a program of the Eight
Queen's program and I have to make it work without recursion. I have to
use a stack instead. It's been buggin me for a week and I have no clue
how to start it. Do you guy think you can help me out?

Take every variable that you would get a new copy of if you recursed and
put that in a class or struct. Every place you would have called the recursive
function, push that struct on your stack. Pop where you would have returned.


For example:

void recurse(int i, int j) {
--i; ++j;
if(i)
recurse(i, j);
}

recurse(100, 0);

becomes

struct RV {
int i;
int j;
};

vector <RV> rstack;

RV v;
v.i = 100;
v.j = 0;

rstack.push_back(v);
while(!rstack.empty()) {
---v.i;
++v.j;
if(v.i) {
rstack.push_back(v);
continue;
}
v = rstack.back();
rstack.pop_back()
}

 

[cfanatic]

Thanks guys for the help. I didn't expect that quick of a response. I
going to give it a shot right now. Also sorry victor, I didn't know but
thanks for helping me anyway.