public void should_have_correct_number_of_unique_solutions(int n, int numSolutions)
        {
            var solver = new Solver(n);
              var results = solver.Solve();

              Assert.AreEqual(numSolutions, results.Count);
        }

        public ActionResult Index(int k = 0)
        {
            int?[,] numbers = new int?[9, 9];

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    string key = string.Format("f{0}{1}", i, j);
                    int number;
                    if (int.TryParse(Request[key], out number))
                        numbers[i, j] = number;
                }
            }

            Game game = new Game(numbers);
            Solver solver = new Solver();

            try
            {
                DateTime start = DateTime.Now;
                solver.Solve(game);
                DateTime end = DateTime.Now;

                ViewBag.Interval = string.Format("Solved in {0} ms.", end.Subtract(start).Milliseconds);
            }
            catch (InvalidGameException)
            {
                ViewBag.Message = "Invalid entry.  There is no solution for the game!";
            }

            ViewBag.Numbers = game.Numbers;
            return View();
        }

  /**
   *
   * A simple propagator for modulo constraint.
   *
   * This implementation is based on the ECLiPSe version
   * mentioned in "A Modulo propagator for ECLiPSE"
   * http://www.hakank.org/constraint_programming_blog/2010/05/a_modulo_propagator_for_eclips.html
   * The ECLiPSe Prolog source code:
   * http://www.hakank.org/eclipse/modulo_propagator.ecl
   *
   */
  public static void MyMod(Solver solver, IntVar x, IntVar y, IntVar r) {

    long lbx = x.Min();
    long ubx = x.Max();
    long ubx_neg = -ubx;
    long lbx_neg = -lbx;
    int min_x = (int)Math.Min(lbx, ubx_neg);
    int max_x = (int)Math.Max(ubx, lbx_neg);

    IntVar d = solver.MakeIntVar(min_x, max_x, "d");

    // r >= 0
    solver.Add(r >= 0);

    // x*r >= 0
    solver.Add( x*r >= 0);

    // -abs(y) < r
    solver.Add(-y.Abs() < r);

    // r < abs(y)
    solver.Add(r < y.Abs());

    // min_x <= d, i.e. d > min_x
    solver.Add(d > min_x);

    // d <= max_x
    solver.Add(d <= max_x);

    // x == y*d+r
    solver.Add(x - (y*d + r) == 0);

  }

        public void Test_no_solution()
        {
            var value = 4;
            var capacities = new[] { 3, 5 };

            var pouringGeneratorFactory = MockRepository.GenerateStrictMock<IPouringGeneratorFactory>();
            var pouringGenerator = MockRepository.GenerateStrictMock<IPouringGenerator>();

            var solver = new Solver(
                pouringGeneratorFactory
            );

            pouringGeneratorFactory
                .Expect(f => f.Create(capacities.Length))
                .Return(pouringGenerator);

            pouringGenerator
                .Stub(g => g.GetNextGeneration(null))
                .IgnoreArguments()
                .Return(Enumerable.Empty<Pouring>());

            var solutions = solver
                .SolutionSequence(value, capacities)
                .ToArray();

            Assert.AreEqual(0, solutions.Length);
        }

  /*
   * Decompositon of cumulative.
   *
   * Inspired by the MiniZinc implementation:
   * http://www.g12.csse.unimelb.edu.au/wiki/doku.php?id=g12:zinc:lib:minizinc:std:cumulative.mzn&s[]=cumulative
   * The MiniZinc decomposition is discussed in the paper:
   * A. Schutt, T. Feydy, P.J. Stuckey, and M. G. Wallace.
   * "Why cumulative decomposition is not as bad as it sounds."
   * Download:
   * http://www.cs.mu.oz.au/%7Epjs/rcpsp/papers/cp09-cu.pdf
   * http://www.cs.mu.oz.au/%7Epjs/rcpsp/cumu_lazyfd.pdf
   *
   *
   * Parameters:
   *
   * s: start_times    assumption: IntVar[]
   * d: durations      assumption: int[]
   * r: resources      assumption: int[]
   * b: resource limit assumption: IntVar or int
   *
   *
   */
  static void MyCumulative(Solver solver,
                           IntVar[] s,
                           int[] d,
                           int[] r,
                           IntVar b) {

    int[] tasks = (from i in Enumerable.Range(0, s.Length)
                   where r[i] > 0 && d[i] > 0
                   select i).ToArray();
    int times_min = tasks.Min(i => (int)s[i].Min());
    int d_max = d.Max();
    int times_max = tasks.Max(i => (int)s[i].Max() + d_max);
    for(int t = times_min; t <= times_max; t++) {
      ArrayList bb = new ArrayList();
      foreach(int i in tasks) {
        bb.Add(((s[i] <= t) * (s[i] + d[i]> t) * r[i]).Var());
      }
      solver.Add((bb.ToArray(typeof(IntVar)) as IntVar[]).Sum() <= b);
    }

    // Somewhat experimental:
    // This constraint is needed to constrain the upper limit of b.
    if (b is IntVar) {
      solver.Add(b <= r.Sum());
    }

   }

  public static void minus(Solver solver, 
                           IntVar x, 
                           IntVar y, 
                           IntVar z) 
 {
   solver.Add(z == (x - y).Abs());
 }

 public FltGenerate( Solver solver, FltVar[] list )
     : base(solver)
 {
     m_FltVarList		= list;
     m_SelectVar			= FltVarSelector.CardinalityMin;
     m_Search			= new FltSearchDichotomize();
 }

    public static void Main(String[] args)
    {
        String problem = "ft10";
        long timeout = 1000 * 60 * 10;
        String[] solverNames = new String[] { "sa", "ibb", "taboo" };
        int i = 0;
        if (i < args.Length)
            problem = args[i++];
        if (i < args.Length)
            timeout = Int32.Parse(args[i++]) * 1000;
        if (i < args.Length)
        {
            solverNames = new String[args.Length - i];
            int j = 0;
            for (; i < args.Length; i++)
            {
                solverNames[j++] = args[i];
            }
        }
        Network network = (new JSSPProblem(problem)).network();
        if (network == null)
            return;
        //int opt = Solver.MINIMIZE | Solver.BETTER;
        int opt = Solver.Default;
        Solver[] solvers = new Solver[solverNames.Length];
        for (i = 0; i < solvers.Length; i++)
        {
            String name = solverNames[i];
            if (name.Equals("sa"))
            {
                solvers[i] = new SimulatedAnneallingSearch((Network)network.Clone(), opt, name);
            }
            else if (name.Equals("ibb"))
            {
                solvers[i] = new IterativeBranchAndBoundSearch((Network)network.Clone(), opt, name);
            }
            else if (name.Equals("taboo") || name.Equals("tabu"))
            {
                solvers[i] = new TabooSearch((Network)network.Clone(), opt, name);
            }
            else if (name.Equals("rw"))
            {
                solvers[i] = new LocalSearch((Network)network.Clone(), opt, name);
            }
            else
            {
                Console.Out.WriteLine("Unknown solver name " + name);
                solvers[i] = null;
            }
        }
        Solver all = new ParallelSolver(solvers);

        //Monitor monitor = new Monitor();
         //monitor.setX(0, (int)(timeout/1000));
        //all.setMonitor(monitor);
        //SolutionHandler sh=null;
        Solution solution = all.FindBest(timeout);
        Console.Out.WriteLine(solution);
        Console.In.ReadLine();
    }

        public void SolveCaseLarge()
        {
            Solver solver = new Solver();

            solver.Solve(1091.73252, 0.2, 15.44421, 656.09352);
            solver.Solve(1.03291, 0.2, 99.49224, 99999.91210);
        }

        public void SanityCheck_GivenInsaneDataDueToWrongNumberOfBlackAndWhiteSquares_ReturnsFalse()
        {
            // Arrange
            var board = new Board(TestBoardSize);
            var solver = new Solver();
            var bogusPieceD = new Piece(
                new[]
                    {
                        //  B
                        //  W
                        // WW
                        new Square(0, 0, Colour.White),
                        new Square(1, 0, Colour.White),
                        new Square(1, 1, Colour.White),
                        new Square(1, 2, Colour.Black)
                    },
                'D');
            var pieceFeeder = new PieceFeeder(Piece.TestPieceA, Piece.TestPieceB, Piece.TestPieceC, bogusPieceD);

            // Act
            var actual = solver.SanityCheck(board, pieceFeeder);

            // Assert
            Assert.That(actual, Is.False);
        }

        public void NotResolveEmptyPosition()
        {
            Position position = new Position();
            Solver solver = new Solver();

            Assert.IsNull(solver.Resolve(position));
        }

  /**
   *
   * Secret Santa problem in Google CP Solver.
   *
   * From Ruby Quiz Secret Santa
   * http://www.rubyquiz.com/quiz2.html
   * """
   * Honoring a long standing tradition started by my wife's dad, my friends
   * all play a Secret Santa game around Christmas time. We draw names and
   * spend a week sneaking that person gifts and clues to our identity. On the
   * last night of the game, we get together, have dinner, share stories, and,
   * most importantly, try to guess who our Secret Santa was. It's a crazily
   * fun way to enjoy each other's company during the holidays.
   *
   * To choose Santas, we use to draw names out of a hat. This system was
   * tedious, prone to many 'Wait, I got myself...' problems. This year, we
   * made a change to the rules that further complicated picking and we knew
   * the hat draw would not stand up to the challenge. Naturally, to solve
   * this problem, I scripted the process. Since that turned out to be more
   * interesting than I had expected, I decided to share.
   *
   * This weeks Ruby Quiz is to implement a Secret Santa selection script.
   * *  Your script will be fed a list of names on STDIN.
   * ...
   * Your script should then choose a Secret Santa for every name in the list.
   * Obviously, a person cannot be their own Secret Santa. In addition, my friends
   * no longer allow people in the same family to be Santas for each other and your
   * script should take this into account.
   * """
   *
   *  Comment: This model skips the file input and mail parts. We
   *        assume that the friends are identified with a number from 1..n,
   *        and the families is identified with a number 1..num_families.
   *
   * Also see http://www.hakank.org/or-tools/secret_santa.py 
   * Also see http://www.hakank.org/or-tools/secret_santa2.cs 
   *
   */
  private static void Solve()
  {

    Solver solver = new Solver("SecretSanta");

    int[] family = {1,1,1,1, 2, 3,3,3,3,3, 4,4};
    int n = family.Length;

    Console.WriteLine("n = {0}", n);

    IEnumerable<int> RANGE = Enumerable.Range(0, n);

    //
    // Decision variables
    //
    IntVar[] x = solver.MakeIntVarArray(n, 0, n-1, "x");


    //
    // Constraints
    //
    solver.Add(x.AllDifferent());

    // Can't be one own"s Secret Santa
    // (i.e. ensure that there are no fix-point in the array.)
    foreach(int i in RANGE) {
      solver.Add(x[i] != i);
    }


    // No Secret Santa to a person in the same family
    foreach(int i in RANGE) {
      solver.Add(solver.MakeIntConst(family[i]) != family.Element(x[i]));
    }

    //
    // Search
    //
    DecisionBuilder db = solver.MakePhase(x,
                                          Solver.INT_VAR_SIMPLE,
                                          Solver.INT_VALUE_SIMPLE);

    solver.NewSearch(db);

    while (solver.NextSolution()) {
      Console.Write("x:  ");
      foreach(int i in RANGE) {
        Console.Write(x[i].Value() + " ");
      }
      Console.WriteLine();
    }

    Console.WriteLine("\nSolutions: {0}", solver.Solutions());
    Console.WriteLine("WallTime: {0}ms", solver.WallTime());
    Console.WriteLine("Failures: {0}", solver.Failures());
    Console.WriteLine("Branches: {0} ", solver.Branches());

    solver.EndSearch();

  }

        public void FillCellWithIntersectionOfKey()
        {
            IList<Line> columns = new List<Line>
                {
                    new Line( new List<Clue>() ),
                    new Line( new List<Clue>{new Clue( 2 )}),
                    new Line( new List<Clue>{new Clue( 3 )}),
                    new Line( new List<Clue>{new Clue( 1 )}),
                    new Line( new List<Clue>() )
                };

            IList<Line> rows = new List<Line>
                {
                    new Line( new List<Clue>() ),
                    new Line( new List<Clue>{new Clue( 2 )}),
                    new Line( new List<Clue>{new Clue( 3 )}),
                    new Line( new List<Clue>{new Clue( 1 )}),
                    new Line( new List<Clue>() )
                };
            var newField = new Field( columns, rows );

            var solver = new Solver( columns, rows );

            bool res =  solver.CheckFilled( newField.Cells[2, 2] );

            Assert.AreEqual( res, true );

            res = solver.CheckFilled( newField.Cells[1, 2] );

            Assert.AreEqual( res, false );
        }

        public void SolveBackPackProblemWith16RandomItems()
        {
            const int tests = 10;

            double bfFitness = 0.0;
            double gsFitness = 0.0;

            for (int n = 0; n < tests; n++)
            {
                var backPack = new BackPack(2000);
                var items = BackPackEnvironmentTest.RandomItems(16, backPack.Volume, 200);

                var environment = new BackPackEnvironment(backPack, items, 100);

                var solver = new Solver<BackPackIndividual>(environment);
                solver.Start(() => solver.CurrentGeneration > 10);

                var bf = BruteForce(environment);
                var gs = solver.CurrentOptimum;

                Console.WriteLine(environment.RateFitness(bf));
                Console.WriteLine(environment.RateFitness(gs));

                bfFitness += environment.RateFitness(bf);
                gsFitness += environment.RateFitness(gs);
            }
            // Should be atleast 90% of BF'ed fitness
            Console.WriteLine(gsFitness / bfFitness);
            Assert.IsTrue(bfFitness * 0.9 
                <= gsFitness);

        }

 static void TestVarOperator()
 {
   Console.WriteLine("Running TestVarOperator");
   Solver solver = new Solver("TestVarOperator",
                              Solver.CLP_LINEAR_PROGRAMMING);
   Variable x = solver.MakeNumVar(0.0, 100.0, "x");
   Constraint ct1 = solver.Add(x >= 1);
   Constraint ct2 = solver.Add(x <= 1);
   Constraint ct3 = solver.Add(x == 1);
   Constraint ct4 = solver.Add(1 >= x);
   Constraint ct5 = solver.Add(1 <= x);
   Constraint ct6 = solver.Add(1 == x);
   CheckDoubleEq(ct1.GetCoefficient(x), 1.0, "test1");
   CheckDoubleEq(ct2.GetCoefficient(x), 1.0, "test2");
   CheckDoubleEq(ct3.GetCoefficient(x), 1.0, "test3");
   CheckDoubleEq(ct4.GetCoefficient(x), 1.0, "test4");
   CheckDoubleEq(ct5.GetCoefficient(x), 1.0, "test5");
   CheckDoubleEq(ct6.GetCoefficient(x), 1.0, "test6");
   CheckDoubleEq(ct1.Lb(), 1.0, "test7");
   CheckDoubleEq(ct1.Ub(), double.PositiveInfinity, "test8");
   CheckDoubleEq(ct2.Lb(), double.NegativeInfinity, "test9");
   CheckDoubleEq(ct2.Ub(), 1.0, "test10");
   CheckDoubleEq(ct3.Lb(), 1.0, "test11");
   CheckDoubleEq(ct3.Ub(), 1.0, "test12");
   CheckDoubleEq(ct4.Lb(), double.NegativeInfinity, "test13");
   CheckDoubleEq(ct4.Ub(), 1.0, "test14");
   CheckDoubleEq(ct5.Lb(), 1.0, "test15");
   CheckDoubleEq(ct5.Ub(), double.PositiveInfinity, "test16");
   CheckDoubleEq(ct6.Lb(), 1.0, "test17");
   CheckDoubleEq(ct6.Ub(), 1.0, "test18");
 }

        public void SolverCanWinGamesButNotAll(string title, int rowStart, int colStart, GameState finalState, int rows, int cols, int[] minedCellsPositions)
        {
            var minedCells = new List<MineCell>();

            for (int i = 0; i < minedCellsPositions.Length; i += 2)
            {
                minedCells.Add(new MineCell(minedCellsPositions[i], minedCellsPositions[i + 1]));
            }

            var mineField = new MineField(rows, cols, minedCells.ToArray());
            var solver = new Solver(mineField);
            mineField.UncoverCell(rowStart, colStart);
            solver.UncoverGrid();

            Assert.Equal(mineField.GameState, finalState);

            mineField.Reset(true);

            mineField.UncoverCell(rowStart, colStart);

            for (var i = 0; i < 100 && mineField.GameState == GameState.InProgress; i++)
            {
                solver.PlayNextStep();
            }

            Assert.Equal(finalState, mineField.GameState);
        }

    public static int Main()
    {
        for ( ; ; )
        {
            int n = int.Parse(ReadLine());

            if (n == 0) break;

            IList<string> stopWords =
                Enumerable.Range(0, n)
                .Select(_ => ReadLine().ToLowerInvariant())
                .ToArray();

            var testCases =
                Enumerable.Range(0, int.MaxValue)
                .Select(_ => ReadLine().ToLowerInvariant())
                .TakeWhile(s => s != null && s != "last case")
                .Select(s => s.Split(new[]{ ' ' }, StringSplitOptions.RemoveEmptyEntries))
                .Select(words => new { Acronym = words[0], Definition = words.Skip(1).Except(stopWords) })
                .ToArray();

            foreach (var testCase in testCases)
            {
                int solution = new Solver(testCase.Acronym, testCase.Definition).Solve();

                if (solution == 0)
                    WriteLine($"{testCase.Acronym.ToUpperInvariant()} is not a valid abbreviation");
                else
                    WriteLine($"{testCase.Acronym.ToUpperInvariant()} can be formed in {solution} ways");
            }
        }
         
        return 0;
    }

  /**
   *
   * Solve the Least diff problem
   * For more info, see http://www.hakank.org/google_or_tools/least_diff.py
   *
   */
  private static void Solve()
  {
    Solver solver = new Solver("LeastDiff");

    //
    // Decision variables
    //
    IntVar A = solver.MakeIntVar(0, 9, "A");
    IntVar B = solver.MakeIntVar(0, 9, "B");
    IntVar C = solver.MakeIntVar(0, 9, "C");
    IntVar D = solver.MakeIntVar(0, 9, "D");
    IntVar E = solver.MakeIntVar(0, 9, "E");
    IntVar F = solver.MakeIntVar(0, 9, "F");
    IntVar G = solver.MakeIntVar(0, 9, "G");
    IntVar H = solver.MakeIntVar(0, 9, "H");
    IntVar I = solver.MakeIntVar(0, 9, "I");
    IntVar J = solver.MakeIntVar(0, 9, "J");

    IntVar[] all = new IntVar[] {A,B,C,D,E,F,G,H,I,J};
    int[] coeffs = {10000,1000,100,10,1};
    IntVar x = new IntVar[]{A,B,C,D,E}.ScalProd(coeffs).Var();
    IntVar y = new IntVar[]{F,G,H,I,J}.ScalProd(coeffs).Var();
    IntVar diff = (x - y).VarWithName("diff");


    //
    // Constraints
    //
    solver.Add(all.AllDifferent());
    solver.Add(A > 0);
    solver.Add(F > 0);
    solver.Add(diff > 0);


    //
    // Objective
    //
    OptimizeVar obj = diff.Minimize(1);

    //
    // Search
    //
    DecisionBuilder db = solver.MakePhase(all,
                                          Solver.CHOOSE_PATH,
                                          Solver.ASSIGN_MIN_VALUE);

    solver.NewSearch(db, obj);
    while (solver.NextSolution()) {
      Console.WriteLine("{0} - {1} = {2}  ({3}",x.Value(), y.Value(), diff.Value(), diff.ToString());
    }

    Console.WriteLine("\nSolutions: {0}", solver.Solutions());
    Console.WriteLine("WallTime: {0}ms", solver.WallTime());
    Console.WriteLine("Failures: {0}", solver.Failures());
    Console.WriteLine("Branches: {0} ", solver.Branches());

    solver.EndSearch();

  }

 public IntGenerate( Solver solver, IntVar[] list, IntVarSelector.Select select, IntSearch search )
     : base(solver)
 {
     m_IntVarList		= list;
     m_SelectVar			= select;
     m_Search			= search;
     m_Depth				= new RevValue<double>( solver.StateStack, 1 );
 }

    //  We don't need helper functions here
    //  Csharp syntax is easier than C++ syntax!

    private static void CPisFun (int kBase)
    {
        //  Constraint Programming engine
        Solver solver = new Solver ("CP is fun!");

        // Decision variables
        IntVar c = solver.MakeIntVar (1, kBase - 1, "C");
        IntVar p = solver.MakeIntVar (0, kBase - 1, "P");
        IntVar i = solver.MakeIntVar (1, kBase - 1, "I");
        IntVar s = solver.MakeIntVar (0, kBase - 1, "S");
        IntVar f = solver.MakeIntVar (1, kBase - 1, "F");
        IntVar u = solver.MakeIntVar (0, kBase - 1, "U");
        IntVar n = solver.MakeIntVar (0, kBase - 1, "N");
        IntVar t = solver.MakeIntVar (1, kBase - 1, "T");
        IntVar r = solver.MakeIntVar (0, kBase - 1, "R");
        IntVar e = solver.MakeIntVar (0, kBase - 1, "E");

        // We need to group variables in a vector to be able to use
        // the global constraint AllDifferent
        IntVar[] letters = new IntVar[] { c, p, i, s, f, u, n, t, r, e};

        // Check if we have enough digits
        if (kBase < letters.Length) {
          throw new Exception("kBase < letters.Length");
        }

        //  Constraints
        solver.Add (letters.AllDifferent ());

        // CP + IS + FUN = TRUE
        solver.Add (p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
               e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t);

        SolutionCollector all_solutions = solver.MakeAllSolutionCollector();
        //  Add the interesting variables to the SolutionCollector
        all_solutions.Add(c);
        all_solutions.Add(p);
        //  Create the variable kBase * c + p
        IntVar v1 = solver.MakeSum(solver.MakeProd(c, kBase), p).Var();
        //  Add it to the SolutionCollector
        all_solutions.Add(v1);

        //  Decision Builder: hot to scour the search tree
        DecisionBuilder db = solver.MakePhase (letters,
                                               Solver.CHOOSE_FIRST_UNBOUND,
                                               Solver.ASSIGN_MIN_VALUE);
        solver.Solve(db, all_solutions);

        //  Retrieve the solutions
        int numberSolutions = all_solutions.SolutionCount();
        Console.WriteLine ("Number of solutions: " + numberSolutions);

        for (int index = 0; index < numberSolutions; ++index) {
            Assignment solution = all_solutions.Solution(index);
            Console.WriteLine ("Solution found:");
            Console.WriteLine ("v1=" + solution.Value(v1));
        }
    }