440,077 Members | 1,237 Online
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