/*

 SCSPS Version 2.0

 The Segmented Constraint Satisfaction Problem Generator/Solver

 Brief Description:
 This program generates a CSP with a set of variables and some constraints
 of the form x + y < a. Then some agents are created as independent Java
 threads, and each is assigned some of the variables and constraints. Agents
 get a work (partial solution) from a workpool, try to make their assigned
 constraints consistent, and return the work. This continues until the
 workpool refuses to give them any more work, at which point the agents stop
 executing.

 This program and the IMA (Iterative Multi-Agent) method are explained in the 
 Paper "The Iterative Multi-Agent Method for Solving Complex Search Problems" 
 which is available at http://www.csuregina.ca/~karimi/pubs.html.

 Developed using Sun's Java Development Kit 1.2 under Microsoft Windows 95.
 Compile it by the command  javac SCSPS.java
 Run it by the command  java SCSPS

 The program sends its output to the Standard Output.


 Written by Kamran Karimi
 Copyright (C) Kamran Karimi.

 Freely usable and distributable.
 Please retain the copyright and all the commnets when redistributing.

 @author Kamran Karimi
 Department of Computer Science
 University of Regina
 Regina, Saskatchewan
 Canada S4S 0A2

 karimi@cs.uregina.ca
 http://www.cs.uregina.ca/~karimi


 You can edit the values in the ParamsCSP class to affect the run. Some of
the values in that class can be determined at invocation time. They are:

 *) verbose: Outputs more information about the system as it works.
 *) runs <number>: determines how many runs should be performed on a problem.
 *) vars <number>: The number of variables in the problem.
 *) constraints <number>: The number of constraints in the problem.
 *) agents <# of agents>: The number of agents created for each run.
 *) agentarray <length of array> <# of agents> ... <# of agents>: An
    alternative to "agents." It lets the user run the same problem several
    times, each with a different number of agents.
 *) workrounds <number>: The number of times the workpool will give out work.

 Example:

java SCSPS runs 2 vars 10 constraints 10 agentarray 2 5 10 workrounds 2000>out

*/

import java.util.*;
import java.lang.reflect.*;

// this class contains the constants that control the program behaviour
class ParamsCSP
{
 // should the program be verbose?
 static boolean verbose = false;

 // how many times the program will attempt to find a solution for a set of
 // constraints?
 static int totalRuns = 1;

 // total times the WorkPool will give works away.
 // should be high enough to ensure all agents change a work.
 static int totalWorkRounds = 2000;

 // number of partial solutions in the workpool
 static int totalWork = 101;

 // total number of agent processes. Should be <= totalWork, otherwise some of
 // agents won't be able to find work, and will quit.
 // If this number is 1, then all the variables and constraints will be
 // assigned to that single agent, and it will solve the problem using
 // Backtracking.
 static int totalAgents = 9;

 // if a non-zero value is provided for this field by the user, then differing
 // number of agents will work on the same problem.
 static int agentArray = 0;

 // used to hold the number of agents that will work on the same problem
 // the size is determined by the user as a command line argument.
 static int agents[];

 // total number of variables in the problem
 static int totalVars = 10;

 // total number of constraints in the problem
 static int totalConstraints = 10;

 // the sleep time of the main thread. In ms.
 static int sleepTime = 100;

 // the time limit for a run. In ms.
 static int timeLimit = 120000;

 // minimum value of the range of a variable. Should be <= maxVarVal.
 static int minVarVal = 1;

 // maximum value of the range of a variable. Should be >= 3.
 static int maxVarVal = 20; 

 // minimum limit for the generated constraints
 static int minLim = 10; 

 // maximum limit for the generated constraints.
 // Should be >= minLim and not 0.
 static int maxLim = 20; 

 // each agent sleeps for a maximum of this amount before getting next work.
 // this is meant to give a work to all agents. Shouldn't be 0.
 static int maxAgentWait = 10;

 // maximum number of variables per agent. Should be > 0 and <= totalVars
 static int maxVars_Agent = 8;

 //minimum number of variables per agent. Should be >= 1
 static int minVars_Agent = 2;

 //maximum number of constraints per agent. Should be > 0 and <= totalConstraints
 static int maxCrts_Agent = 8; 

 //minimum number of constraints per agent. Should be >= 1
 static int minCrts_Agent = 2; 
}


// This class is used by the agents to signal the main thread when they are
// done
class Synch
{
 static int counter;

 static synchronized void init(int initVal)
 {
  counter = initVal;
 }

 static synchronized void dec()
 {
  counter--;
 }

 static synchronized boolean isZero()
 {
  return (counter == 0);
 }
}

// Each "variable" has a value, a "change" flag, and domain information in
// the form of a minimum and maximum limits
class Variable
{
 int val;

 // set to false by variable instantiation, to true by check routines.
 boolean shouldChange = false;
 int minVal, maxVal;

 // use rand to create an initial random value for this variable
 Variable(int min, int max, Random rand)
 {
  minVal = min;
  maxVal = max;

  if(max == 0)
   val = 0;
  else
  {
   val = Math.abs(rand.nextInt()) % max;
   if(val < min)
    val = min;
  }
 }

 void print()
 {
  System.out.print("Val: " + val);
  System.out.println("  Range: [" + minVal + " ... " + maxVal + "]");
 }
}

// each "work" is a parttial solution. It contains an array of variables,
// a "free" flag to show if that work is available for processing in the
// workpool, and a set data structure for recording the agents who have
// worked on it.
class Work
{
 Variable vars[];
 boolean free = true;
 TreeSet agents = new TreeSet();

 Work(Random rand)
 {
  vars = new Variable[ParamsCSP.totalVars];

  for(int count = 0; count < ParamsCSP.totalVars; count++)
  {
   vars[count] = new Variable(VarRange.minmax[count][0],
                              VarRange.minmax[count][1], rand);
  }
 }

 void print()
 {
  for(int count = 0; count < ParamsCSP.totalVars; count++)
  {
   System.out.println("x" + count + " contains:");
   vars[count].print();
  }
  System.out.println("---- Agents that worked on this:");
  Iterator i = agents.iterator();
  while(i.hasNext())
  {
   System.out.print("a" + (Integer)i.next());
   if(i.hasNext())
    System.out.print(", ");
   else
    System.out.println();
  }
  if(free)
   System.out.println("This work is free");
  else
   System.out.println("This work is NOT free");

  System.out.println();
 }
}


// This is the workpool. It creates the partial solutions (works), and
// manages them.
class WorkPool
{
 static Work works[];
 static int workRounds;

 WorkPool(Random rand)
 {
  workRounds = 0;

  works = new Work[ParamsCSP.totalWork];

  // Now create the solutions
  for(int count = 0; count < ParamsCSP.totalWork; count++)
  {
   works[count] = new Work(rand);
  }
 }

 static void print()
 {
  for(int count = 0; count < ParamsCSP.totalWork; count++)
  {
   System.out.println("Work No." + count + " contains:");
   works[count].print();
  }
  System.out.println();
 }


 static synchronized int getWork(int seed)
 {
  int retVal = -1;
  int tried = 0;

  if(workRounds < ParamsCSP.totalWorkRounds)
  {
   // when there is only one agent, find only one solution 
   if(ParamsCSP.totalAgents == 1 && workRounds > 0)
    return -1;

   // round robin
   do
   {
    if(seed >= ParamsCSP.totalWork)
     seed = 0;
    if(works[seed].free)
    {
     works[seed].free = false;
     retVal = seed;

     workRounds++;
     break;
    }
    tried++;
    seed++;
   } while (tried < ParamsCSP.totalWork);
  }
  return retVal;
 }

 static synchronized void putWork(int i)
 {
  works[i].free = true;
 }

}

class VarRange
{
 static int minmax[][];

 VarRange(Random rand)
 {
  minmax = new int[ParamsCSP.totalVars][2];

  for(int count = 0; count < ParamsCSP.totalVars; count++)
  {
   int max = Math.abs(rand.nextInt()) % ParamsCSP.maxVarVal;

   int min = Math.abs(rand.nextInt()) % (ParamsCSP.maxVarVal / 3);

   if(min < ParamsCSP.minVarVal)
    min = ParamsCSP.minVarVal;

   if(min > max)
    min = max;

   minmax[count][0] = min;
   minmax[count][1] = max;
  }
 }

 static void print()
 {
  for(int count = 0; count < ParamsCSP.totalVars; count++)
  {
   System.out.println("x" + count + ": [" + minmax[count][0] + "..." +
                      minmax[count][1] + "]");
  }
 }
}


// this is of the form var1 + var2 < limit
class Constraint
{
 int limit;
 int var1;
 int var2;

 Constraint(int l, int v1, int v2)
 {
  limit = l;
  var1 = v1;
  var2 = v2;
 }

 void print()
 {
  System.out.println("x" + var1 + " + x" + var2 + " < " + limit);
 }

 boolean canCheckBoth(int v1, int v2)
 {
  if(((v1 == var1) && (v2 == var2)) ||
     ((v1 == var2) && (v2 == var1)))
   return true;

  return false;
 }

 boolean canCheck(int v)
 {
  if(v == var1 || v == var2)
   return true;

  return false;
 } 

 boolean check(Variable vals[])
 {
   if(vals[var1].val + vals[var2].val < limit)
    return true;

  return false;
 }

 void setBothChange(Variable vals[])
 {
  vals[var1].shouldChange = true;
  vals[var2].shouldChange = true;
 }

 void setOtherChange(Variable vals[], int var)
 {
  if(var == var1)
   vals[var2].shouldChange = true;
  else
   vals[var1].shouldChange = true;
 }

}

// creates the constraints.
class Constraints
{
 static Constraint crts[];
 int cLim, firstVar, secondVar;

 Constraints()
 {
  crts = new Constraint[ParamsCSP.totalConstraints];
  Random rand = new Random();
  for(int count = 0; count < ParamsCSP.totalConstraints; count++)
  {
   cLim = Math.abs(rand.nextInt()) % ParamsCSP.maxLim;
   if(cLim < ParamsCSP.minLim)
    cLim = ParamsCSP.minLim;

   firstVar = Math.abs(rand.nextInt()) % ParamsCSP.totalVars;
   secondVar = Math.abs(rand.nextInt()) % ParamsCSP.totalVars;

   crts[count] = new Constraint(cLim, firstVar, secondVar);
  }
 }

 static void print()
 {
  System.out.println("The generated constraints:");
  for(int count = 0; count < ParamsCSP.totalConstraints; count++)
  {
   System.out.print("c" + count + " : ");
   crts[count].print();
  }
  System.out.println();
 }

}


// This is a utility class. 
class Control
{

 // checks to see f all the constraints and the variables were assigned
 // to at least one agent.
 static void checkVars(Random rand)
 {
  int var, var2, wrkrs;

  for(var = 0; var < ParamsCSP.totalVars; var++)
  {
   agents:
   for(wrkrs = 0; wrkrs < ParamsCSP.totalAgents; wrkrs++)
   {
    for(var2 = 0; var2 < Agents.agents[wrkrs].totalVars; var2++)
    {
     if(Agents.agents[wrkrs].myVars[var2] == var)
      break agents;
    }
   }
   if(wrkrs == ParamsCSP.totalAgents)
   {
    // variable "var" is not assigned to any agent.
    wrkrs = Math.abs(rand.nextInt()) % ParamsCSP.totalAgents;
    Agents.agents[wrkrs].addVar(var);
   }
  }
 }

 static void checkCrts(Random rand)
 {
  int crt, crt2, wrkrs;

  for(crt = 0; crt < ParamsCSP.totalConstraints; crt++)
  {
   agents:
   for(wrkrs = 0; wrkrs < ParamsCSP.totalAgents; wrkrs++)
   {
    for(crt2 = 0; crt2 < Agents.agents[wrkrs].zeroVarCrts; crt2++)
    {
     if(Agents.agents[wrkrs].myZeroCrts[crt2] == crt)
      break agents;
    }
    for(crt2 = 0; crt2 < Agents.agents[wrkrs].oneVarCrts; crt2++)
    {
     if(Agents.agents[wrkrs].myOneCrts[crt2] == crt)
      break agents;
    }
    for(crt2 = 0; crt2 < Agents.agents[wrkrs].twoVarCrts; crt2++)
    {
     if(Agents.agents[wrkrs].myTwoCrts[crt2] == crt)
      break agents;
    }
   }
   if(wrkrs == ParamsCSP.totalAgents)
   {
    // constraints "crt" is not assignedto any agnet
    wrkrs = Math.abs(rand.nextInt()) % ParamsCSP.totalAgents;
    Agents.agents[wrkrs].addCrt(crt);
   }
  }
 }

 // check to see if it is possible at all to find a solution. This
 // is done by substituting the least value of each variable in
 // the constraints.
 static void checkPossible()
 {
  TreeSet impossibles = new TreeSet();

  for(int count = 0; count < ParamsCSP.totalConstraints; count++)
  {
   int limit =  Constraints.crts[count].limit;
   int var1 = Constraints.crts[count].var1;
   int var2 = Constraints.crts[count].var2;

    if(VarRange.minmax[var1][0] + VarRange.minmax[var2][0] >= limit)
    impossibles.add(new Integer(count));
  }
  if(impossibles.size() > 0)
  {
   Iterator i = impossibles.iterator();

   System.out.print("*****Satisfying ");
   while(i.hasNext())
   {
    System.out.print("c" + (Integer)i.next());
    if(i.hasNext())
     System.out.print(", ");
    else
     System.out.println(" is impossible");
   }
   System.out.println("Terminating the run");
   System.exit(1);
  }
 }
 
 // finds out if there are any inconsistencies in the solutions.
 static void checkPool()
 {
  int count, crt, index, prevIndex;
  Variable vals[];
  boolean consistent;
  TreeSet violators = new TreeSet();

  for(count = 0; count < ParamsCSP.totalWork; count++)
  {
   if(ParamsCSP.verbose)
    System.out.println("Checking Work no. " + count);
   if(WorkPool.works[count].agents.size() < ParamsCSP.totalAgents)
    System.out.println("Warning: Not all agents worked on Solution " + count);

   vals = WorkPool.works[count].vars;

   // Sanity check: the domain
   for(index = 0; index < ParamsCSP.totalVars; index++)
   {
    if(vals[index].val > vals[index].maxVal ||
       vals[index].val < vals[index].minVal)
    {
     System.out.println("== x" + index + " ==");
     vals[index].print();
    }
   }

   // check the constraints
   for(index = 0; index < ParamsCSP.totalVars; index++)
   {
    for(prevIndex = 0; prevIndex < index; prevIndex++)
    {
     for(crt = 0; crt < ParamsCSP.totalConstraints; crt++)
     {
      consistent = true;
      if(Constraints.crts[crt].canCheckBoth(index, prevIndex))
      {
       consistent = Constraints.crts[crt].check(vals);
      }
      if(!consistent)
      {
       if(ParamsCSP.verbose)
       {
        System.out.println("-------");
        System.out.println("violates c" + crt);
        System.out.println("x" + index);
        vals[index].print();
        System.out.println("x" + prevIndex);
        vals[prevIndex].print();
        Constraints.crts[crt].print();
       }
       violators.add(new Integer(count));
      }
     }
    }
   }
  }
  if(violators.size() == 0)
   System.out.println("All solutions in the work pool are valid");
  else
  {
   Iterator i = violators.iterator();

   System.out.print("Partial solution(s) number ");
   while(i.hasNext())
   {
    System.out.print((Integer)i.next());
    if(i.hasNext())
     System.out.print(", ");
    else
     System.out.println(" are not valid");
   }
  } 
  System.out.println("*****Solutions: " + (ParamsCSP.totalWork - violators.size()) + " out of " +
                      ParamsCSP.totalWork);
  System.out.println();
 }
}


// The agent code. The same code is used for all of them.
class Agent implements Runnable
{
 int myNumber;
 int myVars[];

  boolean finish;

 // The constraints are categorized into three types.
 // Type 1: Those that have both their variables present in this agent 
 int myTwoCrts[];
 // Type 2: Those that have only one variable present
 int myOneCrts[];
 // Type 3: Those that have none of their variables present
 int myZeroCrts[];

 int twoVarCrts, oneVarCrts, zeroVarCrts;

 int totalVars;
 int totalCrts;

 Agent(int Number)
 {
  myNumber = Number;

  finish = false;

  twoVarCrts = 0;
  oneVarCrts = 0;
  zeroVarCrts = 0;
  totalVars = 0;
  totalCrts = 0;

  // allocate memory for the worst case. Later, this makes it easier to
  // handle the varibales and constraintes that end up as not assigned to
  // anything
  myVars = new int[ParamsCSP.totalVars];
  myTwoCrts = new int[ParamsCSP.totalConstraints];
  myOneCrts = new int[ParamsCSP.totalConstraints];
  myZeroCrts = new int[ParamsCSP.totalConstraints];
 }

 void allocRandomCrts(int crts, Random rand)
 {
  int count, count2;

  // get the constraints and categorize them according to the number of vars
  nextCrt:
  for(count = 0; count < crts; count++)
  {
   int var1;

   int crt = Math.abs(rand.nextInt()) % ParamsCSP.totalConstraints;

   // make sure there are no duplicate constraints
   allOver:
   do
   {
    for(count2 = 0; count2 < twoVarCrts; count2++)
    {
     if(crt == myTwoCrts[count2])
     {
      crt++;
      if(crt >= ParamsCSP.totalConstraints)
       crt = 0;
      break;
     }
    }
    if(count2 < twoVarCrts)
     continue allOver;

    for(count2 = 0; count2 < oneVarCrts; count2++)
    {
     if(crt == myOneCrts[count2])
     {
      crt++;
      if(crt >= ParamsCSP.totalConstraints)
       crt = 0;
      break;
     }
    }
    if(count2 < oneVarCrts)
     continue allOver;

    for(count2 = 0; count2 < zeroVarCrts; count2++)
    {
     if(crt == myZeroCrts[count2])
     {
      crt++;
      if(crt >= ParamsCSP.totalConstraints)
       crt = 0;
      break;
     }
    }
    if(count2 < zeroVarCrts)
     continue allOver;

    break;
   }while(true);

   addCrt(crt);
  }
 }

 void addCrt(int crt)
 {
  boolean twoVar = false, oneVar = false;

  int var1;

  nextCrt1:
  for(var1 = 0; var1 < totalVars; var1++)
  {
   int realIndex = myVars[var1];
   for(int var2 = 0; var2 <= var1; var2++)
   {
    int realPrevIndex = myVars[var2];
    if(Constraints.crts[crt].canCheckBoth(realIndex, realPrevIndex))
    {
     twoVar = true;
     break nextCrt1;
    }
   }
  }
  if(twoVar)
  {
   myTwoCrts[twoVarCrts] = crt;
   twoVarCrts++;
  }

  if(twoVar)
  {
   totalCrts++;
   return;
  }

  nextCrt2:
  for(var1 = 0; var1 < totalVars; var1++)
  {
   int realIndex = myVars[var1];
   for(int var2 = 0; var2 <= var1; var2++)
   {
    int realPrevIndex = myVars[var2];
    if(!Constraints.crts[crt].canCheckBoth(realIndex, realPrevIndex) &&
      (Constraints.crts[crt].canCheck(realIndex) ||
      Constraints.crts[crt].canCheck(realPrevIndex)))
    {
     oneVar = true;
     break nextCrt2;
    }
   }
  }
  if(oneVar)
  {
   myOneCrts[oneVarCrts] = crt;
   oneVarCrts++;
  }

  if(oneVar)
  {
   totalCrts++;
   return;
  }

  nextCrt3:
  for(var1 = 0; var1 < totalVars; var1++)
  {
   int realIndex = myVars[var1];
   for(int var2 = 0; var2 <= var1; var2++)
   {
    int realPrevIndex = myVars[var2];
    if(Constraints.crts[crt].canCheck(realIndex) ||
       Constraints.crts[crt].canCheck(realPrevIndex))
    {
     break nextCrt3;
    }
   }
  }

  if(var1 == totalVars)
  {
   myZeroCrts[zeroVarCrts] = crt;
   zeroVarCrts++;
  }

  totalCrts++;
 }

 void allocRandomVars(int vars, Random rand)
 {
  int count, count2;

  for(count = 0; count < vars; count++)
  {
   int varNum = Math.abs(rand.nextInt()) % ParamsCSP.totalVars;

   // make sure there are no duplicate variables in the same agent
   do
   {
    for(count2 = 0; count2 < count; count2++)
    {
     if(varNum == myVars[count2])
     {
      varNum++;
      if(varNum >= ParamsCSP.totalVars)
       varNum = 0;
      break;
     }
    }
    if(count2 == count)
     break;
   } while(true);

   addVar(varNum);
  }
 }

 void addVar(int varNum)
 {
  myVars[totalVars] = varNum;
  totalVars++;
 }

 void print()
 {
  System.out.println("Agent No. " + myNumber + ":");
  System.out.println("My Variables:");
  for(int count = 0; count < totalVars; count++)
  {
   System.out.println("x" + myVars[count]);
  }

  System.out.println("My Constraints:");

  for(int count = 0; count < zeroVarCrts; count++)
  {
   System.out.println("Zero var: c" + myZeroCrts[count]);
  }

  for(int count = 0; count < oneVarCrts; count++)
  {
   System.out.println("One var: c" + myOneCrts[count]);
  }

  for(int count = 0; count < twoVarCrts; count++)
  {
   System.out.println("Two var: c" + myTwoCrts[count]);
  }
 }

 // This is where the agents' processing is done
 public void run()
 {
  int workNum;
  int node, prevNode;
  Random rand = new Random(myNumber);

  workNum = myNumber - 1;
  while(true)
  {
   if(finish)
    break;
   workNum++;

   workNum = WorkPool.getWork(workNum);

   //end it
   if(workNum == -1)
    break;

   // note that this agent has worked on this.
   WorkPool.works[workNum].agents.add(new Integer(myNumber));
   
   Variable vals[];
   vals = WorkPool.works[workNum].vars;

   { // This is the main processing loop
     // change the values that have their change flag set to true.
    checkVars(vals);

    // Try to satisfy type 2 constraints first.
    t2Constraints(vals);

    // Then go for type 1 constraints
    // do this after type 2, because binaries are more important
    t1Constraints(0, vals);

    // check for inconsistency in type 2 and type 3 constraints
    checkT23Constraints(vals);

   }

   WorkPool.putWork(workNum);

   // sleep for a while, and let other agents get ahead of you. This hopefully
   // shuffles the the agent's execution order.
   try
   {
    Thread.currentThread().sleep((Math.abs(rand.nextInt()) % ParamsCSP.maxAgentWait) + 1);
   }    
   catch(InterruptedException e)
   {
   }

  }

  Synch.dec();
  if(ParamsCSP.verbose)
   System.out.println("Agent " + myNumber + " Done");
 }


 /* see if we still have inconsistencies. This should be called last,
    so there will be some work for other rounds */
 void checkT23Constraints(Variable vals[])
 {
  int crt;
  boolean consistent;

  for(crt = 0; crt < zeroVarCrts; crt++)
  {
   if(!Constraints.crts[myZeroCrts[crt]].check(vals))
    Constraints.crts[myZeroCrts[crt]].setBothChange(vals);
  }

  for(int node = 0; node < totalVars; node++)
  {
   int realIndex = myVars[node];

   if(finish)
    break;
   for(crt = 0; crt < oneVarCrts; crt++)
   {
    if(Constraints.crts[myOneCrts[crt]].canCheck(realIndex))
    {
     if(!Constraints.crts[myOneCrts[crt]].check(vals))
      Constraints.crts[myOneCrts[crt]].setOtherChange(vals, realIndex);
    }
   }
  }
 }

 // change the variables that have caused inconsistencies.
 void checkVars(Variable vals[])
 {
  for(int node = 0; node < totalVars; node++)
  {
   int realIndex = myVars[node];

   if(finish)
    break;
   if(vals[realIndex].shouldChange)
   {
    // with no other info, just increment it;
    vals[realIndex].val++;
    if(vals[realIndex].val > vals[realIndex].maxVal)
     vals[realIndex].val = vals[realIndex].minVal;
    vals[realIndex].shouldChange = false;
   }
  }
 }


 /* Should go over its own variables and assign a value to each and check
    their consistency as much as it can */
 boolean t1Constraints(int node, Variable vals[])
 {
  boolean consistent;
  int maxIteration;
  int prevNode, crt;
  int realPrevIndex;

  int realIndex = myVars[node];

  int min = vals[realIndex].minVal;
  int max = vals[realIndex].maxVal;

  maxIteration =  max - min + 1;

  // a do istead of for, so all the domain will be explored during
  // different iterations.
  do
  {
   if(finish)
    break;
   consistent = true;

   for(prevNode = 0; prevNode <= node && consistent; prevNode++)
   {
    realPrevIndex = myVars[prevNode];

    for(crt = 0; crt < twoVarCrts && consistent; crt++)
     if(Constraints.crts[myTwoCrts[crt]].canCheckBoth(realIndex, realPrevIndex))
      consistent = Constraints.crts[myTwoCrts[crt]].check(vals);
   }

   if(consistent)
   {
    if(node == totalVars - 1)
     return true;
    else
    {
     if(t1Constraints(node + 1, vals) == true)
     return true;
    }
   }

   maxIteration--;
   if(maxIteration < 0)
    break;

   // do the increment at the end, so as to disturb the vars as little AP
   vals[realIndex].val++;

   if(vals[realIndex].val > max)
    vals[realIndex].val = min;

  }while(true);
  return false;
 }

 void t2Constraints(Variable vals[])
 {
  int node, crt;
  int maxIteration;
  boolean consistent;

  for(node = 0; node < totalVars; node++)
  {
   int realIndex = myVars[node];

   if(finish)
    break;
   int min = vals[realIndex].minVal;
   int max = vals[realIndex].maxVal;

   maxIteration =  max - min + 1;

   // a do istead of for, so all the domain will be explored during
   // different iterations.
   do
   {
    consistent = true;

    for(crt = 0; crt < oneVarCrts && consistent; crt++)
     if(Constraints.crts[myOneCrts[crt]].canCheck(realIndex))
      consistent = Constraints.crts[myOneCrts[crt]].check(vals);
 
    maxIteration--;

    if(consistent || maxIteration < 0)
     break;

    vals[realIndex].val++;

    if(vals[realIndex].val > max)
     vals[realIndex].val = min;

   }while (true);
  }
 }

}


// This class holds the array of agents
class Agents
{
 static Agent agents[];
 int numVars, numCrts;
 Random rand;


 Agents(Random rand)
 {
  this.rand = rand;

  agents = new Agent[ParamsCSP.totalAgents];
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
   agents[count] = new Agent(count);
 }

 void finish()
 {
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
   agents[count].finish = true;
 }  

 void assignVars()
 {
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
  {
   //make sure they have at least one variable and one constraint.
   // If only one agent, give it everything
   if(ParamsCSP.totalAgents == 1)
    numVars = ParamsCSP.maxVars_Agent;
   else
   {
    numVars = Math.abs(rand.nextInt()) % ParamsCSP.maxVars_Agent;
    if(numVars < ParamsCSP.minVars_Agent)
     numVars = ParamsCSP.minVars_Agent;
   }
   
   agents[count].allocRandomVars(numVars, rand);
  }
 }

 void assignCrts()
 {
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
  {
   if(ParamsCSP.totalAgents == 1)
    numCrts = ParamsCSP.maxCrts_Agent;
   else
   {                                       
    numCrts = Math.abs(rand.nextInt()) % ParamsCSP.maxCrts_Agent;
    if(numCrts < ParamsCSP.minCrts_Agent)
     numCrts = ParamsCSP.minCrts_Agent;
   }
   agents[count].allocRandomCrts(numCrts, rand);
  }
 }

 void startAll()
 {
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
  {
   Thread tw;
   tw = new Thread(agents[count]);
   tw.start();
  }
 }

 void print()
 {
  for(int count = 0; count < ParamsCSP.totalAgents; count++)
  {
   agents[count].print();
   System.out.println();
  }
 }
}


public class SCSPS implements Runnable
{
 public static void main(String args[])
 {
  int curArg = 0;
  SCSPS me = new SCSPS();
  Integer intval;

  while(curArg < Array.getLength(args))
  {
   if(args[curArg].toLowerCase().equals("verbose"))
    ParamsCSP.verbose = true;
   else if(args[curArg].toLowerCase().equals("runs"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.totalRuns = intval.intValue();
   }
   else if(args[curArg].toLowerCase().equals("vars"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.totalVars = intval.intValue();
   }
   else if(args[curArg].toLowerCase().equals("constraints"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.totalConstraints = intval.intValue();;
   }
   else if(args[curArg].toLowerCase().equals("agents"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.totalAgents = intval.intValue();
   }
   else if(args[curArg].toLowerCase().equals("agentarray"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.agentArray = intval.intValue();
    ParamsCSP.agents = new int[ParamsCSP.agentArray];

    for(int count = 0; count < ParamsCSP.agentArray; count++)
    {
     curArg++;
     intval = new Integer(args[curArg]);
     ParamsCSP.agents[count] = intval.intValue();
    }
   }
   else if(args[curArg].toLowerCase().equals("workrounds"))
   {
    curArg++;
    intval = new Integer(args[curArg]);
    ParamsCSP.totalWorkRounds = intval.intValue();
   }
   curArg++;
  }

  Thread tme = new Thread(me);
  tme.start();
 }

 public void run()
 {
  long elapsedTime;
  long startTime, endTime;
  int runs;
  Random rand = new Random();
  Agents agents;
  long runTimes[];

  System.out.println("AgentArray: " + ParamsCSP.agentArray);
  for(int count = 0; count < ParamsCSP.agentArray; count++)
   System.out.println(" # of Agents: " + ParamsCSP.agents[count]);

  new Constraints();
  // print the generated constarints
  Constraints.print();

  new VarRange(rand);
  // print the range of variables
  VarRange.print();

  Control.checkPossible();

  runTimes = new long[ParamsCSP.totalRuns];

  for(int acount = 0; acount < Math.max(ParamsCSP.agentArray, 1); acount++)
  {
   if(ParamsCSP.agentArray > 0)
    ParamsCSP.totalAgents = ParamsCSP.agents[acount];

   System.out.println("*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*");
   System.out.println("Started");
   System.out.println("Runs: " + ParamsCSP.totalRuns);
   System.out.println("Vars: " + ParamsCSP.totalVars);
   System.out.println("Crts: " + ParamsCSP.totalConstraints);
   System.out.println("Agts: " + ParamsCSP.totalAgents);
   System.out.println("Rnds: " + ParamsCSP.totalWorkRounds);

   System.out.println();
   runs = 1;
   // use the constraints generated before in a number of runs.
   do
   {
    elapsedTime = 0;
    System.out.println();
    System.out.println("*****Run number " + runs);
    System.out.println("----------");

    Synch.init(ParamsCSP.totalAgents);

    new WorkPool(rand);
    // Print the initial workpool
    if(ParamsCSP.verbose)
     WorkPool.print();

    // Check the consistency of the work pool before the agents have started
    //if(ParamsCSP.verbose)
     Control.checkPool();

    agents = new Agents(rand);

    agents.assignVars();
    // make sure all the variables are assigned to at least one agent
    Control.checkVars(rand);

    agents.assignCrts();
    // make sure all constraints are assigned to at least one agent
    Control.checkCrts(rand);

    // Now display each agent's assigned variables and constraints
    if(ParamsCSP.verbose)
     agents.print();

    startTime = System.currentTimeMillis();

    agents.startAll();

    do
    { 
     // Periodically check to see if the agents are done
     if(Synch.isZero())
      break;
     try
     {
      Thread.currentThread().sleep(ParamsCSP.sleepTime);
     }    
     catch(InterruptedException e)
     {
     }
     elapsedTime += ParamsCSP.sleepTime;
     if(elapsedTime >= ParamsCSP.timeLimit)
     {
      System.out.println("Time Limit exceeded!. Terminating the run");
      agents.finish();
     }
    } while(true);
    endTime = System.currentTimeMillis();

    // Print the resulting workpool 
    if(ParamsCSP.verbose)
     WorkPool.print();

    // check the consistency of the solutions after the agents are done
    Control.checkPool();

    runTimes[runs - 1] = endTime - startTime;
    runs++;
   } while(runs <= ParamsCSP.totalRuns);
   printRunTimes(runTimes);
  }

  System.out.println("Done.");
 }

 void printRunTimes(long runTimes[])
 {
  long average, sum = 0;
  long minimum, maximum;
  long variance = 0;

  minimum = maximum = runTimes[0];

  for(int count = 0; count < ParamsCSP.totalRuns; count++)
  {
   sum += runTimes[count];

   if(minimum > runTimes[count])
    minimum = runTimes[count];

   if(maximum < runTimes[count])
    maximum = runTimes[count];
  }
  average = sum / ParamsCSP.totalRuns;

  System.out.println("Run Times:");
  System.out.println("Minimum: " + minimum);
  System.out.println("Maximum: " + maximum);
  System.out.println("Average: " + average);

  if(ParamsCSP.totalRuns > 1)
  {
   for(int count = 0; count < ParamsCSP.totalRuns; count++)
    variance += (runTimes[count] - average) * (runTimes[count] - average);

   variance /= (ParamsCSP.totalRuns - 1);
   System.out.println("Variance: " + variance);
   System.out.println("Standard Deviation: " + (long)Math.sqrt(variance));
  }
 }
}