Queens.h

// Queens.h -- The Queens problem represented as a CSP.

/*
 * Copyright (C) 1997,1998,2005 Tudor Hulubei <tudor@hulubei.net>.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2, 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser 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.
 */

// $Id: Queens_8h-source.html,v 1.1 2005/05/25 12:37:18 tudor Exp $

#ifndef _CSP_EXAMPLES_Queens_H
#define _CSP_EXAMPLES_Queens_H


#ifndef __cplusplus
#error Must use C++ for the type Queens.
#endif


#include "values/Int.h"
#include "variables/Int.h"


CSP_NAMESPACE_BEGIN(Queens)


using namespace std;


#ifdef __GNUG__
using namespace __gnu_cxx;
#endif

#if defined(_MSC_VER) && (_MSC_VER == 1310)
using namespace stdext;
#endif


typedef csp::values::Int Value;
typedef csp::Domain Domain;
class Variable;


class Constraint :
    public csp::Constraint
{
  public:
    Constraint(int queens = 0) : csp::Constraint()
    {
        m_queens = queens;
    }

    virtual bool check() const;

  private:
    /* We need this only when eliminating symmetries.  `m_queens'==0
       means that we won't eliminate symmetries.  */
    int m_queens;
};


class VerticalConstraint :
    public csp::Constraint
{
  public:
    VerticalConstraint(int /*queens*/ = 0) : csp::Constraint() {}
    virtual bool check() const;
    virtual wstring name() const { return L"|"; }
    virtual wstring color() const { return L"black"; }
    virtual wstring textColor() const { return L"black"; }
};


class DiagonalConstraint :
    public csp::Constraint
{
  public:
    DiagonalConstraint() : csp::Constraint() {}
    virtual bool check() const;
    virtual wstring name() const { return L"X"; }
    virtual wstring color() const { return L"red"; }
    virtual wstring textColor() const { return L"red"; }
};


class SymmetryConstraint :
    public csp::Constraint
{
  public:
    SymmetryConstraint(int queens) : csp::Constraint()
    {
        m_queens = queens;
    }

    virtual bool check() const;
    virtual wstring name() const { return L"<->"; }
    virtual wstring color() const { return L"blue"; }
    virtual wstring textColor() const { return L"blue"; }

  private:
    /* We need this only when eliminating symmetries.  `m_queens'==0
       means that we won't eliminate symmetries.  */
    int m_queens;
};


class Problem :
    public csp::Problem
{
  public:
    Problem(
        csp::RandomSequence& randomSequence,
        int queens,
        bool compact = false,
        bool symmetry = true);
    Problem(const Problem& problem);

    virtual wstring name() const { return L"Queens"; }

    virtual wostream& printSolution(wostream& wos) const;

    virtual wostream& print(wostream& wos) const
    {
        wos << L"Problem: Queens" << endl;
        return csp::Problem::print(wos);
    }

  protected:
    void addConstraint(
        csp::Variable& variable0,
        csp::Variable& variable1,
        int queens);
    void addVerticalConstraint(
        csp::Variable& variable0,
        csp::Variable& variable1);
    void addDiagonalConstraint(
        csp::Variable& variable0,
        csp::Variable& variable1);
    void addSymmetryConstraint(
        csp::Variable& variable0,
        csp::Variable& variable1,
        int queens);

  private:
    void constructor(int nVariables, bool compact, bool symmetry);

    int m_nVariables;
    bool m_compact;
    bool m_symmetry;
};


class Variable :
    public csp::variables::Int
{
  public:
    Variable(const Problem& problem, int min, int max, int index) :
        csp::variables::Int(problem, min, max),
        m_index(index),
        m_isBackdoor(false),
        m_isBackdoorKey(false),
        m_isBranching(false)
    {}

    int index() const { return m_index; }

    virtual wstring color() const
    {
        // It's important that the isBackdoor test comes last, as both
        // branching variables (those involved in branching
        // assignments) and backdoor keys are in the backdoor.
        if (m_isBranching)
            return L"pink";
        if (m_isBackdoorKey)
            return L"orange";
        if (m_isBackdoor)
            return L"red";
        return L"orange";
    }

    virtual wstring textColor() const { return L"white"; }

    virtual wstring shape() const
    {
        if (m_isBackdoor || m_isBackdoorKey || m_isBranching)
            return L"rectangle";
        return csp::Variable::shape();
    }

    virtual void setBackdoorStatus(bool status) { m_isBackdoor = status; }
    virtual void setBackdoorKeyStatus(bool status) { m_isBackdoorKey = status; }
    virtual void setBranchingStatus(bool status) { m_isBranching = status; }

  private:
    int m_index;
    bool m_isBackdoor;
    bool m_isBackdoorKey;
    bool m_isBranching;
};


class MinimumValueCache
{
  public:
    MinimumValueCache() {}

    size_t minimumValue(const csp::Variable& variable);

    void clear() { m_minimumValues.clear(); }

  private:
    MinimumValueCache(const MinimumValueCache&);

    MinimumValueCache& operator=(const MinimumValueCache&);

    size_t computeMinimumValue(const Variable& variable);

    typedef hash_map<const csp::Variable*, size_t> mv_type;

    mv_type m_minimumValues;
};


class ValueLT :
    public csp::StrictWeakVariableOrdering
{
  public:
    ValueLT(MinimumValueCache& minimumValues) :
        m_minimumValues(minimumValues) {}

    bool operator()(
        const csp::Variable* variable0,
        const csp::Variable* variable1)
    {
        return
            m_minimumValues.minimumValue(*variable0) <
            m_minimumValues.minimumValue(*variable1);
    }

  private:
    MinimumValueCache& m_minimumValues;
};


class ValueEQ :
    public csp::StrictWeakVariableOrdering
{
  public:
    ValueEQ(MinimumValueCache& minimumValues) :
        m_minimumValues(minimumValues) {}

    bool operator()(
        const csp::Variable* variable0,
        const csp::Variable* variable1);

  private:
    MinimumValueCache& m_minimumValues;

    Variable* m_previousVariable0;
    Variable* m_previousVariable1;

    size_t m_previousMinimumValue0;
    size_t m_previousMinimumValue1;
};


class MinValue :
    public csp::VariableOH
{
  public:
    MinValue(
        csp::Decomposition& decomposition,
        const vector<pair<double, double> >& intervals,
        double quality = 1);

    /*
     * This is a very good variable order heuristic for the Queens
     * problem.  It selects the variables that have the smallest number
     * in their domain.
     */
    void select(csp::vlist_type& vlist, csp::vlist_type& selected);

  private:
    MinimumValueCache m_minimumValues;

    ValueLT m_compareLT;

    ValueEQ m_compareEQ;
};


CSP_NAMESPACE_END(Queens)


#endif // _CSP_EXAMPLES_Queens_H

// Local Variables:
// mode: C++
// End:

---