ac3.co

programming par contraint

/*Constraint aX + bY = c*/
import cotfd;
class Eq extends UserConstraint<CP>{
	var<CP>{int} _x;
	var<CP>{int} _y;
	int _a;
	int _b;
	int _c;
	var<CP>{int}[] _vars; //variables of the constraints
	
	/*Constructor*/
	Eq(int a, var<CP>{int} X, int b, var<CP>{int} Y, int c):UserConstraint<CP>(){
		_a = a;
		_b = b;
		_c = c;
		_x = X;
		_y = Y;
		_vars = new var<CP>{int}[0..1];
		_vars[0] = _x;
		_vars[1] = _y;
	}
	
	var<CP>{int}[] getintVariables(){ return _vars; }
	
	Outcome<CP> post(Consistency<CP> cl){
		//do a first propagation
		Outcome<CP> resPropag = propagate();
		
		_x.addDomain(this);
		_y.addDomain(this);
		
		return resPropag;
	}
	
	/* Propage method */
	Outcome<CP> propagate(){
		if(_b != 0)
			forall(vx in _x.getMin().._x.getMax() : _x.memberOf(vx)){
				//check if (_c - _a*vx) is divisible by _b.
				if((_c - _a*vx) % _b == 0){
					int vy = (_c - _a*vx) / _b;
					if(!_y.memberOf(vy))
						if(_x.removeValue(vx) == Failure) return Failure;
				}
				else{
					if(_x.removeValue(vx) == Failure) return Failure;
				}
			}

		if(_a != 0)
			forall(vy in _y.getMin().._y.getMax() : _y.memberOf(vy)){
				//check if (_c - _b*vy) is divisible by _a.
				if((_c - _b*vy) % _a == 0){				
					int vx = (_c - _b*vy ) / _a;
					if(!_x.memberOf(vx))
						if(_y.removeValue(vy) == Failure) return Failure;		
				}
				else{
					if(_y.removeValue(vy) == Failure) return Failure;
				}
			}
		if(_a == 0 && _b == 0 && _c != 0) return Failure;
		return Suspend;
	}
}


/*Constraint aX + bY <= c*/
class Leq extends UserConstraint<CP>{
	var<CP>{int} _x;
	var<CP>{int} _y;
	int _a;
	int _b;
	int _c;
	var<CP>{int}[] _vars; //variables of the constraints
	
	/*Constructor*/
	Leq(int a, var<CP>{int} X, int b, var<CP>{int} Y, int c):UserConstraint<CP>(){
		_a = a;
		_b = b;
		_c = c;
		_x = X;
		_y = Y;
		_vars = new var<CP>{int}[0..1];
		_vars[0] = _x;
		_vars[1] = _y;
	}
	
	var<CP>{int}[] getintVariables(){ return _vars; }
	
	Outcome<CP> post(Consistency<CP> cl){
		//do a first propagation
		Outcome<CP> resPropag = propagate();
		
		_x.addMin(this);
		_x.addMax(this);
		_y.addMin(this);
		_y.addMax(this);
		
		return resPropag;
	}
	
	Outcome<CP> propagate(){
		//update max(x)
		if(_a > 0){
			int newMax = max((int)((_c - _b*_y.getMax()) / _a), (int)((_c - _b*_y.getMin()) / _a));
			if(_x.updateMax(newMax) == Failure) return Failure;
		}
		//update min(x)		
		if(_a < 0){		
			int newMinX = min((int)((_c - _b*_y.getMax()) / _a), (int)((_c - _b*_y.getMin()) / _a));
			if(_x.updateMin(newMinX) == Failure) return Failure;
		}	
					
		//update min(y)
		if(_b < 0){
			int newMin = min((int)((_c - _a*_x.getMax()) / _b), (int)((_c - _a*_x.getMin())/_b));
			if(_y.updateMin(newMin) == Failure) return Failure;
		}
		if(_b > 0){
		//update max(y)				
			int newMaxY = max((int)((_c - _a*_x.getMax()) / _b), (int)((_c - _a*_x.getMin())/_b));
			if(_y.updateMax(newMaxY) == Failure) return Failure;
		}
		//is the constraint always satisfied?
		if(_a >= 0 && _b >= 0)			  
			if(_a*_x.getMax() + _b*_y.getMax() <= _c) return Success;
		if(_a >= 0 && _b <= 0)				
			if(_a*_x.getMax() + _b*_y.getMin() <= _c) return Success;
		if(_a <= 0 && _b => 0)				
			if(_a*_x.getMin() + _b*_y.getMax() <= _c) return Success;
		if(_a <= 0 && _b <= 0)				
			if(_a*_x.getMin() + _b*_y.getMin() <= _c) return Success;
		if(_a == 0 && _b == 0 && _c >= 0) return Success;
		else if(_a == 0 && _b == 0 && _c < 0) return Failure;		
		return Suspend;

	}
}

Solver<CP> m();

int _a1 = -1;
int _b1 = 2;
int _c1 = 500;

int _a2 = 3;
int _b2 = 2;
int _c2 = 200;

int _a3 = 5;
int _b3 = -1;
int _c3 = 400;

var<CP>{int} p[0..1](m,1..100);
Integer nb(0);

solveall<m>{
	m.post(Leq(_a1, p[0], _b1, p[1], _c1));
	m.post(Eq(_a2, p[0], _b2, p[1], _c2));
	m.post(Leq(_a3, p[0], _b3, p[1], _c3));
}
using{
	label(m);
	nb := nb + 1;
	cout << p << endl;
}

cout << "Nombre de solutions: " << nb <<endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;