a_round_of_golf.cs

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using Google.OrTools.ConstraintSolver;


public class ARoundOfGolf
{

  /**
   *
   * A Round of Golf puzzle (Dell Logic Puzzles) in Google CP Solver.
   *
   * From http://brownbuffalo.sourceforge.net/RoundOfGolfClues.html
   * """
   * Title: A Round of Golf
   * Author: Ellen K. Rodehorst
   * Publication: Dell Favorite Logic Problems
   * Issue: Summer, 2000
   * Puzzle #: 9
   * Stars: 1
   *
   * When the Sunny Hills Country Club golf course isn't in use by club members,
   * of course, it's open to the club's employees. Recently, Jack and three other
   * workers at the golf course got together on their day off to play a round of
   * eighteen holes of golf.
   * Afterward, all four, including Mr. Green, went to the clubhouse to total
   * their scorecards. Each man works at a different job (one is a short-order
   * cook), and each shot a different score in the game. No one scored below
   * 70 or above 85 strokes. From the clues below, can you discover each man's
   * full name, job and golf score?
   *
   * 1. Bill, who is not the maintenance man, plays golf often and had the lowest
   * score of the foursome.
   * 2. Mr. Clubb, who isn't Paul, hit several balls into the woods and scored ten
   * strokes more than the pro-shop clerk.
   * 3. In some order, Frank and the caddy scored four and seven more strokes than
   * Mr. Sands.
   * 4. Mr. Carter thought his score of 78 was one of his better games, even
   *    though Frank's score  was lower.
   * 5. None of the four scored exactly 81 strokes.
   *
   * Determine: First Name - Last Name - Job - Score
   * """
   *
   * See http://www.hakank.org/google_or_tools/a_round_of_golf.py
   *
   */
  private static void Solve()
  {
    Solver solver = new Solver("ARoundOfGolf");

    // number of speakers
    int n = 4;

    int Jack  = 0;
    int Bill  = 1;
    int Paul  = 2;
    int Frank = 3;

    //
    // Decision variables
    //
    IntVar[] last_name =  solver.MakeIntVarArray(n, 0, n-1, "last_name");
    // IntVar Green  = last_name[0]; // not used
    IntVar Clubb  = last_name[1];
    IntVar Sands  = last_name[2];
    IntVar Carter = last_name[3];

    IntVar[] job =  solver.MakeIntVarArray(n, 0, n-1, "job");
    // IntVar cook            = job[0]; // not used
    IntVar maintenance_man = job[1];
    IntVar clerk           = job[2];
    IntVar caddy           = job[3];

    IntVar[] score =  solver.MakeIntVarArray(n, 70, 85, "score");

    // for search
    IntVar[] all = new IntVar[n*3];
    for(int i = 0; i < n; i++) {
      all[i] = last_name[i];
      all[i+n] = job[i];
      all[i+2*n] = score[i];
    }

    //
    // Constraints
    //
    solver.Add(last_name.AllDifferent());
    solver.Add(job.AllDifferent());
    solver.Add(score.AllDifferent());

    // 1. Bill, who is not the maintenance man, plays golf often and had
    //    the lowest score of the foursome.
    solver.Add(maintenance_man != Bill);
    solver.Add(score[Bill] < score[Jack]);
    solver.Add(score[Bill] < score[Paul]);
    solver.Add(score[Bill] < score[Frank]);

    // 2. Mr. Clubb, who isn't Paul, hit several balls into the woods and
    //    scored ten strokes more than the pro-shop clerk.
    solver.Add(Clubb != Paul);
    solver.Add(score.Element(Clubb) == score.Element(clerk) + 10);

    // 3. In some order, Frank and the caddy scored four and seven more
    //    strokes than Mr. Sands.
    solver.Add(caddy != Frank);
    solver.Add(Sands != Frank);
    solver.Add(caddy != Sands);

    IntVar b3_a_1 = score.Element(Sands) + 4 == score[Frank];
    IntVar b3_a_2 = score.Element(caddy) == score.Element(Sands) + 7;
    IntVar b3_b_1 = score.Element(Sands) + 7 == score[Frank];
    IntVar b3_b_2 = score.Element(caddy) == score.Element(Sands) + 4;
    solver.Add( (b3_a_1*b3_a_2) + (b3_b_1*b3_b_2) == 1);

    // 4. Mr. Carter thought his score of 78 was one of his better games,
    //    even though Frank's score was lower.
    solver.Add(Carter != Frank);
    solver.Add(score.Element(Carter) == 78);
    solver.Add(score[Frank] < score.Element(Carter));

    // 5. None of the four scored exactly 81 strokes.
    for(int i = 0; i < n; i++) {
      solver.Add(score[i] != 81);
    }

    //
    // Search
    //
    DecisionBuilder db = solver.MakePhase(all,
                                          Solver.INT_VAR_DEFAULT,
                                          Solver.INT_VALUE_DEFAULT);

    solver.NewSearch(db);

    while (solver.NextSolution()) {
      Console.WriteLine(
          "Last name: " +
          String.Join(",  ", (from i in last_name
                              select i.Value().ToString()).ToArray()));
      Console.WriteLine(
          "Job      : " +
          String.Join(",  ", (from i in job
                              select i.Value().ToString()).ToArray()));
      Console.WriteLine(
          "Score    : " +
          String.Join(", ", (from i in score
                             select i.Value().ToString()).ToArray()));
    }

    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 static void Main(String[] args)
  {
    Solve();
  }
}