QuasiGroup.h

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

/*
 * Copyright (C) 1998,2004-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: QuasiGroup_8h-source.html,v 1.1 2005/05/25 12:37:18 tudor Exp $

#ifndef _CSP_EXAMPLES_QuasiGroup_H
#define _CSP_EXAMPLES_QuasiGroup_H


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


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


CSP_NAMESPACE_BEGIN(QuasiGroup)


using namespace std;


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


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

    /*
     * FIXME: Document.
     */
    void select(csp::vlist_type& vlist, csp::vlist_type& selected);
};


class Problem :
    public csp::Problem
{
  public:
    Problem(
        csp::RandomSequence& randomSequence,
        int order,
        bool idempotency = false,
        bool symmetry = true,
        int holes = 0,
        bool balanced = true);

    Problem(const Problem& problem);
    Problem(csp::RandomSequence& randomSequence, wifstream& wifs);

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

    Variable& variable(int row, int column) const
    {
        return *m_variables[row][column];
    }

    int order() const { return m_order; }

    virtual bool isSolution() const;

    virtual void save(wofstream& wofs) const;

    virtual wostream& printSolution(wostream& wos) const;
    virtual wostream& print(wostream& wos) const;

  private:
    void constructor(
        int order,
        bool idempotency,
        bool symmetry,
        int holes,
        bool balanced);

    void createVariables();
    void createConstraints();
    void createHoles();
    void resetIds(csp::Variable& variable);

    void newLatinSquare();
    void initIncidence();
    void shuffle(int times);

    int findColumn(int row, int value, int column);
    int findRow(int value, int column);
    int findValue(int row, int column);
    void generateRandomHoles(int holes);
    void generateBalancedHoles(int holes);

    // The order of the quasigroup.
    int m_order;

    // `true' if we want idempotent quasigroups.
    bool m_idempotency;

    // `true' if we allow symmetries.
    bool m_symmetry;

    // The number of holes when configured as quasi-groups with holes.
    int m_holes;

    // `true' if balanced holes should be generated, `false' for random.
    bool m_balanced;

    // The problem's MD5 signature-based checksum.
    wstring m_checksum;
    
    // The variables involved in the problem.
    vector<vector<Variable*> > m_variables;

    // These are for building quasigroups with holes.
    vector<vector<int> > m_values;
    vector<vector<int> > m_fixed;
    vector<vector<vector<int> > > m_incidence;
};


class Variable :
    public csp::variables::Int
{
  public:
    Variable(
        const Problem& problem,
        int min, int max,
        int row, int column) :
        csp::variables::Int(problem, min, max),
        m_row(row),
        m_column(column),
        m_isBackdoor(false),
        m_isBackdoorKey(false),
        m_isBranching(false)
    {
    }

    Variable(
        const Problem& problem,
        const vector<csp::values::Int>& values,
        int row, int column) :
        csp::variables::Int(problem, values),
        m_row(row),
        m_column(column),
        m_isBackdoor(false),
        m_isBackdoorKey(false),
        m_isBranching(false)
    {
    }

    int row() const { return m_row; }
    int column() const { return m_column; }

    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 csp::Variable::color();
    }

    virtual wstring textColor() const { return csp::Variable::textColor(); }

    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_row;
    int m_column;
    bool m_isBackdoor;
    bool m_isBackdoorKey;
    bool m_isBranching;
};


class Different :
    public csp::Constraint
{
  public:
    Different(Problem& problem) :
        csp::Constraint(), m_problem(problem) {}

    virtual bool check() const;
    virtual wstring name() const { return L"!="; }
    virtual wstring color() const { return L"red"; }
    virtual wstring textColor() const { return L"red"; }

  private:
    /* We need this here in order to be able to access the table of
       variables.  */
    Problem& m_problem;
};


CSP_NAMESPACE_END(QuasiGroup)


#endif // _CSP_EXAMPLES_QuasiGroup_H

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

---