---

eight_queens.cc

/*
*  Name:      eight_queens.cc
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   Test for base algorithm
*  Date:      $Date: 2003/04/14 00:18:36 $
*  Revision:  $Revision: 1.1 $
*
*  Copyright (C) 1994-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
*  MA 02111-1307, USA.
*/

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <mpcl/test.h>
#include <vector>


#define MAX_QUEENS   (8)
#define MAX_ROWS     (8)
#define MAX_COLUMNS  (8)


class TQueen
{

  public:

    int   iX;
    int   iY;


  public:

    TQueen (void) :
      iX (0)      ,
      iY (0)      {}

    bool isKillingTo (const TQueen& rktSOURCE_QUEEN) const;
    bool operator == (const TQueen& rktSOURCE_QUEEN) const;

    //
    //  S T R E A M   F U N C T I O N S
    //
    friend std::basic_ostream<char>& operator << (std::basic_ostream<char>& rtOUTPUT_OSTREAM, const TQueen& rktSOURCE_QUEEN);

};  // class TQueen

typedef std::vector<TQueen>        TArrayQueen;
typedef std::vector<TArrayQueen>   TArrayArrayQueen;


class TRecursiveApproachAlgorithm
{

  public:

    TArrayArrayQueen*   ptSolutionsArray;


  public:

    void execute (TArrayArrayQueen& rtSOLUTIONS_ARRAY);


  private:

    bool areKillingEachOther ( const TQueen&      rktQUEEN              ,
                               const TArrayQueen& rktSOURCE_QUEEN_ARRAY ) const;
    bool tryFor (int iROW, TArrayQueen& rtQUEEN_ARRAY);

};  // class TRecursiveApproachAlgorithm


bool TQueen::isKillingTo (const TQueen& rktSOURCE_QUEEN) const
{

  return ( ( abs (iX - rktSOURCE_QUEEN.iX) == abs (iY - rktSOURCE_QUEEN.iY) ) ||
           ( iX == rktSOURCE_QUEEN.iX )                                       ||
           ( iY == rktSOURCE_QUEEN.iY )                                        );

}  // TQueen::isKillingTo()


bool TQueen::operator == (const TQueen& rktSOURCE_QUEEN) const
{

  return ( ( iX == rktSOURCE_QUEEN.iX ) && ( iY == rktSOURCE_QUEEN.iY ) );

}  // TQueen::operator ==()


std::basic_ostream<char>& operator << (std::basic_ostream<char>& rtOUTPUT_OSTREAM, const TQueen& rktSOURCE_QUEEN)
{

  rtOUTPUT_OSTREAM << rktSOURCE_QUEEN.iX;
  rtOUTPUT_OSTREAM << ",";
  rtOUTPUT_OSTREAM << rktSOURCE_QUEEN.iY;
  return rtOUTPUT_OSTREAM;

}  // friend operator << ()


void TRecursiveApproachAlgorithm::execute (TArrayArrayQueen& rtSOLUTIONS_ARRAY)
{

  TArrayQueen   tTemporalQueenArray;

  //
  //  Warning:  We know that there are solutions. If we shouldn't know that, 
  //            this wouldn't be an algorithm, because it could not find a
  //            solution.
  //
  ptSolutionsArray = &rtSOLUTIONS_ARRAY;

  tryFor (0, tTemporalQueenArray);

}  // TRecursiveApproachAlgorithm::execute()


bool TRecursiveApproachAlgorithm::areKillingEachOther ( const TQueen&      rktQUEEN       ,
                                                        const TArrayQueen& rktQUEEN_ARRAY ) const
{

  bool   gKills = false;

  for (size_t J = 0; ( J < rktQUEEN_ARRAY.size() ) ;++J)
  {
    if ( rktQUEEN_ARRAY [J].isKillingTo (rktQUEEN) )
    {
      gKills = true;
      break;
    }
  }
  return gKills;

}  // TRecursiveApproachAlgorithm::areKillingEachOther()


bool TRecursiveApproachAlgorithm::tryFor (int iROW, TArrayQueen& rtQUEEN_ARRAY)
{

  bool   gSuccess = true;

  if ( ( rtQUEEN_ARRAY.size() < MAX_QUEENS ) && ( iROW < MAX_ROWS ) )
  {

    TQueen   tNewQueen;

    gSuccess     = false;
    tNewQueen.iY = iROW;
    for (size_t J = 0; ( J < MAX_COLUMNS ) ;++J)
    {
      tNewQueen.iX = J;
      if ( !areKillingEachOther (tNewQueen, rtQUEEN_ARRAY) )
      {
        rtQUEEN_ARRAY.push_back (tNewQueen);
        if ( tryFor (iROW + 1, rtQUEEN_ARRAY) )
        {
          gSuccess |= true;
          if ( rtQUEEN_ARRAY.size() == MAX_QUEENS )
          {
            ptSolutionsArray->push_back (rtQUEEN_ARRAY);
          }
        }
        //
        //  Back-tracking.
        //
        rtQUEEN_ARRAY.erase (rtQUEEN_ARRAY.end() - 1);
      }
    }
  }
  return gSuccess;

}  // TRecursiveApproachAlgorithm::tryFor()


//
//  L O C A L   F U N C T I O N S
//

static void _DisplaySolutionsGraphicly (const TArrayArrayQueen& rktSOLUTIONS_ARRAY)
{

  using std::cout;
  using std::endl;

  //
  //  Warning:  This function supposes that queens are sorted, and
  //            the table is dimension 8x8.
  //
  for (size_t J = 0; ( J < rktSOLUTIONS_ARRAY.size() ) ;++J)
  {
    cout << "Queens Solution [" << J << "]" << endl;
    cout << "+---+---+---+---+---+---+---+---+" << endl;
    for (long int K = rktSOLUTIONS_ARRAY[J].size() - 1; ( K >= 0 ) ;K--)
    {
      for (int L = 0; ( L < rktSOLUTIONS_ARRAY [J][K].iX ) ;++L)
      {
        cout << "|   ";
      }
      cout << "| Q ";
      for (size_t M = rktSOLUTIONS_ARRAY [J][K].iX + 1; ( M < MAX_COLUMNS ) ;++M)
      {
        cout << "|   ";
      }
      cout << "|" << endl;
      cout << "+---+---+---+---+---+---+---+---+" << endl;
    }
  }

}  // _DisplaySolutionsGraphicly()


int main (int argc, char** argv)
{

  using std::strcmp;

  TEST_INIT ("tests for TBaseAlgorithm (implements eight queens solution)");

  TArrayArrayQueen              tSolutionsArray;
  TRecursiveApproachAlgorithm   tRecursiveApproachAlgorithm;

  if ( argc > 1 )
  {
    if ( !strcmp (argv[1], "-g") || !strcmp (argv[1], "--graphic") )
    {
      _DisplaySolutionsGraphicly (tSolutionsArray);
    }
    else
    {
      TEST_WRITE_INFO ("%s", "eight_queens: unrecognized option(s)");
      TEST_WRITE_INFO ("%s", "Usage: eight_queens [{-g|--graphic}]");
      TEST_FAIL;
    }
  }
  else
  {
    tRecursiveApproachAlgorithm.execute (tSolutionsArray);
    TEST_NUMBERS (92, tSolutionsArray.size());
    if ( !TEST_IN_SILENT_MODE )
    {
      for (size_t J = 0; ( J < tSolutionsArray.size() ) ;++J)
      {
        for (size_t K = 0; ( K < tSolutionsArray[J].size() ) ;++K)
        {
          fprintf ( hptTestTargetFile           ,
                    "#Queen [%d][%d]: %d, %d\n" ,
                    J                           ,
                    K                           ,
                    tSolutionsArray [J][K].iX   ,
                    tSolutionsArray [J][K].iY   );
        }
      }
    }
  }

  TEST_MEMORY_STATUS;
  TEST_RETURN_CODE;

}  // main()

---