By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,077 Members | 1,237 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,077 IT Pros & Developers. It's quick & easy.

Eight queens using stacks instead of recursion

P: n/a

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::Position 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;

}
--
Posted via http://dbforums.com
Jul 19 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
"cfanatic" <me*********@dbforums.com> wrote...

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

Jul 19 '05 #2

P: n/a

"cfanatic" <me*********@dbforums.com> wrote in message news:34****************@dbforums.com...

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()
}

Jul 19 '05 #3

P: n/a

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.
--
Posted via http://dbforums.com
Jul 19 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.