Source Code: Queens C++ ```//
// @(#) queens.cpp - solves the eight queens puzzle using coroutines
// Written by David Chaves <[email protected]>, April 2008
//
// USAGE
//
//   g++ -o queens queens.cpp ; ./queens
//
// DESCRIPTION
//
//   This program finds all the solutions to the Eight Queens Puzzle using coroutines,
//   instead of back-tracking or recursivity --
//
//   Coroutines :
//
//     "Coroutines are program components that generalize subroutines to allow
//     multiple entry points and suspending and resuming of execution at certain
//     locations. Coroutines are well-suited for implementing more familiar program
//     components such as cooperative tasks, iterators, infinite lists and pipes."
//
//     "The term "coroutine" was originated by Melvin Conway in 1963."
//
//     -- http://en.wikipedia.org/wiki/Coroutine
//
//   The Eight Queens Puzzle :
//
//     "The eight queens puzzle is the problem of putting eight chess queens on
//      an 8×8 chessboard such that none of them is able to capture any other using
//      the standard chess queen's moves. The queens must be placed in such a way that
//      no two queens would be able to attack each other. Thus, a solution requires
//      that no two queens share the same row, column, or diagonal."
//
//      "Edsger Dijkstra used this problem in 1972 to illustrate the power of what he
//      called Structured programming. He published a highly detailed description of
//      the development of a depth first backtracking algorithm."
//
//      "Finding all solutions to the eight queens puzzle is a good example of a simple
//      but nontrivial problem. For this reason, it is often used as an example problem
//      for various programming techniques, including nontraditional approaches such as
//      constraint programming, logic programming or genetic algorithms. Most often,
//      it is used as an example of a problem which can be solved with a recursive algorithm,
//      by phrasing the n queens problem inductively in terms of adding a single queen to
//      any solution to the problem of placing n−1 queens on an n-by-n chessboard.
//      The induction bottoms out with the solution to the 'problem' of placing 0 queens
//      on an n-by-n chessboard, which is the empty chessboard."
//
//      -- http://en.wikipedia.org/wiki/Eight_queens_puzzle
//
//  SEE TOO
//
//    It is quite easy to implement a solution like this in the Stackless Python
//    http://members.verizon.net/olsongt/stackless/why_stackless.html
//
//    Thomas Guest has written an article describing how to draw beautiful chess boards
//    in Python -- http://wordaligned.org/articles/drawing-chessboards
//
//    It is also posible to implement coroutines in C/C++/C# using the Microsoft Fibers,
//    available at Visual .Net -- see http://msdn2.microsoft.com/en-us/magazine/cc164086.aspx
//

//////////////////////////////////////// simple_coroutine_class.hpp

// This portable implemenation of Knuth's coroutines in based on
// the paper "Coroutines in C" by Simon Tatham, available online
// at http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

typedef int coroutine_id_type;
typedef coroutine_id_type coroutine_body_type;

class simple_coroutine_class
{
private:

coroutine_id_type const coroutine_id;

protected:

int coroutine_state_line_number;

simple_coroutine_class(coroutine_id_type const id) :
coroutine_id(id),
coroutine_state_line_number(0) {}

/// every real-life coroutine must specify
/// their own "body of execution"
virtual coroutine_body_type body() = 0;

public:

virtual ~simple_coroutine_class() {}

/// Adds this coroutine to the simple scheduler
void spawn();

/// Runs the simple scheduler until there is no
/// valid "next coroutine" to run.  The scheduler will
/// start executing the coroutine 'starting_coroutine_id'
static void run(coroutine_id_type const starting_coroutine_id);
};

#define SIMPLE_COROUTINE_BEGIN                                      \
switch (this->coroutine_state_line_number)                      \
{                                                               \
case 0:                                                     \
{

#define SIMPLE_COROUTINE_YIELD(next_coroutine_id)                   \
do                                                  \
{                                                   \
this->coroutine_state_line_number = __LINE__;   \
return next_coroutine_id;                       \
case __LINE__ :                                   \
;                                               \
}                                                   \
while (false)

#define SIMPLE_COROUTINE_END                                        \
}                                                       \
}

//////////////////////////////////////// simple_coroutine_class.cpp

#include <cassert>
#include <map>
#include <iostream>

#include <boost/shared_ptr.hpp>         // smart pointers

typedef boost::shared_ptr<simple_coroutine_class> coroutine_ptr_t;
typedef std::map<coroutine_id_type, coroutine_ptr_t> active_coroutines_t;

/// the "active_coroutines" contains the registry of
/// coroutines available for the simple scheduler
static active_coroutines_t active_coroutines;

void simple_coroutine_class::spawn()
{
active_coroutines[coroutine_id].reset(this);
}

void simple_coroutine_class::run(
coroutine_id_type const starting_coroutine_id)
{
coroutine_id_type next_coroutine_id = starting_coroutine_id;

for (;;)
{
const active_coroutines_t::iterator current =
active_coroutines.find(next_coroutine_id);

if (current == active_coroutines.end())
{
// no "next coroutine" found to execute
return;
}

coroutine_ptr_t const & coroutine_p = current->second;
assert(coroutine_p);

next_coroutine_id = coroutine_p->body();
}
}

//////////////////////////////////////// chess.hpp

#include <cstring>
#include <iostream>

int const CHESS_BOARD_SIZE = 8;

class chess_board_type
{
private:

// row 0 and column 0 are not used, but they are allocated in order
// to use row and column numbers between 1 and CHESS_BOARD_SIZE
bool board[CHESS_BOARD_SIZE + 1][CHESS_BOARD_SIZE + 1];

public:

chess_board_type()
{
memset(board, false, sizeof board);
}

static bool good_row_column(int const row, int const column)
{
return (1 <= row && row <= CHESS_BOARD_SIZE &&
1 <= column && column <= CHESS_BOARD_SIZE);
}

void place_queen_at(int const row, int const column)
{
if (good_row_column(row, column))
{
board[row][column] = true;
}
}

void remove_queen_at(int const row, int const column)
{
if (good_row_column(row, column))
{
board[row][column] = false;
}
}

bool has_queen_at(int const row, int const column) const
{
return good_row_column(row, column) && board[row][column];
}

bool can_place_queen_at(int const row, int const column) const
{
if (!good_row_column(row, column))
{
return false;
}

for (int r = 1; r <= CHESS_BOARD_SIZE; ++r)
{
for (int c = 1; c <= CHESS_BOARD_SIZE; ++c)
{
if (!has_queen_at(r, c))
{
continue;
}

// no two queens share the same row, column, or diagonal
if (row == r || column == c || abs(row - r) == abs(column - c))
{
// sorry, a queen at position (row, column) would
// be attacked by the queen at position (r, c)
return false;
}
}
}
return true;
}
};

class column_generator : public simple_coroutine_class
{
protected:
chess_board_type & chess_board;
int const column_number;
int row_number;

public:
column_generator(chess_board_type & board, int const column) :
simple_coroutine_class(column), chess_board(board),
column_number(column), row_number(0) {}

coroutine_body_type body()
{
SIMPLE_COROUTINE_BEGIN;
for (;;)
{
for (row_number = 1; row_number <= CHESS_BOARD_SIZE; ++row_number)
{
assert(chess_board.good_row_column(row_number, column_number));

if (chess_board.can_place_queen_at(row_number, column_number))
{
// put a new queen at this position
chess_board.place_queen_at(row_number, column_number);

// once we have found a successful solution at
// this column, we proceed to find another solution
// for the column next at the right
SIMPLE_COROUTINE_YIELD(column_number + 1);

// remove the queen that we just put here
chess_board.remove_queen_at(row_number, column_number);
}
}

// when all solutions have been exhausted for column_number, then
// we need to go back to the left column to find another solution
// there and then start over again at this column
SIMPLE_COROUTINE_YIELD(column_number - 1);
}
SIMPLE_COROUTINE_END;
}
};

class print_solution : public column_generator
{
protected:
int solution_number;
bool generate_all_solutions;

public:
print_solution(chess_board_type & board) :
column_generator(board, CHESS_BOARD_SIZE),
solution_number(0), generate_all_solutions(false) {}

void print_current_solution(int const solution_no)
{
// this is a simplistic chess board drawing -- if you want to be
// more sophisticated, then try the techniques described at
// http://wordaligned.org/articles/drawing-chessboards

std::cout << std::endl;
std::cout << "Solution #" << solution_no << std::endl;

std::cout << "     ";
for (int column = 1; column <= CHESS_BOARD_SIZE; ++column)
{
std::cout << ' ' << column << ' ';
}
std::cout << std::endl;

// display the chess board
for (int row = 1; row <= CHESS_BOARD_SIZE; ++row)
{
std::cout << "    " << row;
for (int column = 1; column <= CHESS_BOARD_SIZE; ++column)
{
const bool has_queen = chess_board.has_queen_at(row, column);
std::cout << ' ' << (has_queen ? 'X' : ' ') << ' ';
}
std::cout << std::endl;
}
}

bool shall_we_continue()
{
if (generate_all_solutions)
{
return true;
}

for (std::cout << std::endl;;)
{
std::cout << "  Continue? (no/yes/all) " << std::flush;

{
return false;
}
{
return true;
}
{
generate_all_solutions = true;
return true;
}
}
}

coroutine_body_type body()
{
SIMPLE_COROUTINE_BEGIN;
for (;;)
{
// we are at a imaginary column at the right of the
// board -- when we reach this point, then we have
// successfully found a solution for all the previous
// column, in which case we have to show it
print_current_solution(++solution_number);

if (shall_we_continue())
{
// go back to generate another solution...
SIMPLE_COROUTINE_YIELD(column_number - 1);
}
else
{
// the end-user does not want to see more solutions
SIMPLE_COROUTINE_YIELD(-1);
}
}
SIMPLE_COROUTINE_END;
}
};

class no_more_solutions : public column_generator
{
public:
no_more_solutions(chess_board_type & board) :
column_generator(board, 0) {}

coroutine_body_type body()
{
SIMPLE_COROUTINE_BEGIN;
{
// we are at a imaginary column at the right of the
// board -- when we reach this point, then we have
// successfully found a solution for all the previous
// column, in which case we have to show it

std::cout << std::endl;
std::cout << "No more solutions found!" << std::endl;

// stops running the simple scheduler
SIMPLE_COROUTINE_YIELD(-1);
}
SIMPLE_COROUTINE_END;
}
};

//////////////////////////////////////// main.cpp

#include <cstdlib>

// chess_board is global because it needs
// to be accessible from all coroutines
static chess_board_type chess_board;

int main()
{
// create one coroutine per column 1 .. CHESS_BOARD_SIZE,
// and we use the column# as the coroutine id

for (int column = 1; column <= CHESS_BOARD_SIZE; ++column)
{
(new column_generator(chess_board, column))->spawn();
}

// create two additional coroutines: one to print each
// solution found, and other to receive control when there
// are no more solutions available

(new print_solution(chess_board))->spawn();
(new no_more_solutions(chess_board))->spawn();

// let's start at column 1...

simple_coroutine_class::run(1);
return EXIT_SUCCESS;
}

//////////////////////////////////////// The End
```