Eight queens using stacks instead of recursion

Discussion in 'C++' started by cfanatic, Oct 16, 2003.

  1. cfanatic

    cfanatic Guest

    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
     
    cfanatic, Oct 16, 2003
    #1
    1. Advertising

  2. "cfanatic" <> 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
     
    Victor Bazarov, Oct 16, 2003
    #2
    1. Advertising

  3. cfanatic

    Ron Natalie Guest

    "cfanatic" <> wrote in message news:...
    >
    > 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()
    }
     
    Ron Natalie, Oct 16, 2003
    #3
  4. cfanatic

    cfanatic Guest

    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
     
    cfanatic, Oct 16, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jblazi

    The eight queens problem

    jblazi, Aug 30, 2004, in forum: C++
    Replies:
    9
    Views:
    2,557
    Karl Heinz Buchegger
    Aug 30, 2004
  2. Jeff Epler
    Replies:
    10
    Views:
    669
    Anton Vredegoor
    Aug 20, 2003
  3. Matt

    "Eight Queens" program

    Matt, Aug 18, 2004, in forum: C Programming
    Replies:
    5
    Views:
    464
    -berlin.de
    Aug 21, 2004
  4. sathya_me

    Is this OT(was:Re: "Eight Queens" program)

    sathya_me, Aug 20, 2004, in forum: C Programming
    Replies:
    5
    Views:
    314
    sathya_me
    Aug 20, 2004
  5. SM Ryan

    Re: "Eight Queens" program

    SM Ryan, Aug 21, 2004, in forum: C Programming
    Replies:
    0
    Views:
    370
    SM Ryan
    Aug 21, 2004
Loading...

Share This Page