chaves.ca

//
// @(#) 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
//    language, available at http://www.stackless.com -- please read the paper
//    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;
 
        // display nice headers
        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()
    {
        // don't ask if the user already said "please gimme all solutions"
        if (generate_all_solutions)
        {
            return true;
        }
 
        for (std::cout << std::endl;;)
        {
            std::cout << "  Continue? (no/yes/all) " << std::flush;
 
            std::string answer;
            std::cin >> answer;
 
            if (answer == "no" || answer == "n")
            {
                return false;
            }
            if (answer == "yes" || answer == "y")
            {
                return true;
            }
            if (answer == "all" || answer == "a")
            {
                // won't ask anymore...
                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