crypto.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 Google.OrTools.ConstraintSolver;

public class Crypto
{
  /**
   *
   * Crypto problem.
   * 
   * This is the standard benchmark "crypto" problem.
   *
   * From GLPK:s model cryto.mod.
   *
   * """
   * This problem comes from the newsgroup rec.puzzle.
   * The numbers from 1 to 26 are assigned to the letters of the alphabet.
   * The numbers beside each word are the total of the values assigned to
   * the letters in the word (e.g. for LYRE: L, Y, R, E might be to equal
   * 5, 9, 20 and 13, or any other combination that add up to 47).
   * Find the value of each letter under the equations:
   *
   * BALLET  45     GLEE  66     POLKA      59     SONG     61
   * CELLO   43     JAZZ  58     QUARTET    50     SOPRANO  82
   * CONCERT 74     LYRE  47     SAXOPHONE 134     THEME    72
   * FLUTE   30     OBOE  53     SCALE      51     VIOLIN  100
   * FUGUE   50     OPERA 65     SOLO       37     WALTZ    34
   *
   * Solution:
   * A, B,C, D, E,F, G, H, I, J, K,L,M, N, O, P,Q, R, S,T,U, V,W, X, Y, Z
   * 5,13,9,16,20,4,24,21,25,17,23,2,8,12,10,19,7,11,15,3,1,26,6,22,14,18
   *
   * Reference:
   * Koalog Constraint Solver <http://www.koalog.com/php/jcs.php>,
   * Simple problems, the crypto-arithmetic puzzle ALPHACIPHER.
   * """
   *
   * Also see http://hakank.org/or-tools/crypto.py
   *
   */
  private static void Solve()
  {
    Solver solver = new Solver("Crypto");

    int num_letters = 26;

    int BALLET     =  45;
    int CELLO      =  43;
    int CONCERT    =  74;
    int FLUTE      =  30;
    int FUGUE      =  50;
    int GLEE       =  66;
    int JAZZ       =  58;
    int LYRE       =  47;
    int OBOE       =  53;
    int OPERA      =  65;
    int POLKA      =  59;
    int QUARTET    =  50;
    int SAXOPHONE  = 134;
    int SCALE      =  51;
    int SOLO       =  37;
    int SONG       =  61;
    int SOPRANO    =  82;
    int THEME      =  72;
    int VIOLIN     = 100;
    int WALTZ      =  34;


    //
    // Decision variables
    //
    IntVar[] LD = solver.MakeIntVarArray(num_letters, 1, num_letters, "LD");

    // Note D is not used in the constraints below
    IntVar A =  LD[0]; IntVar B =  LD[1]; IntVar C =  LD[2]; // IntVar D =  LD[3];
    IntVar E =  LD[4]; IntVar F =  LD[5]; IntVar G =  LD[6]; IntVar H =  LD[7]; 
    IntVar I =  LD[8]; IntVar J =  LD[9]; IntVar K = LD[10]; IntVar L = LD[11]; 
    IntVar M = LD[12]; IntVar N = LD[13]; IntVar O = LD[14]; IntVar P = LD[15]; 
    IntVar Q = LD[16]; IntVar R = LD[17]; IntVar S = LD[18]; IntVar T = LD[19]; 
    IntVar U = LD[20]; IntVar V = LD[21]; IntVar W = LD[22]; IntVar X = LD[23]; 
    IntVar Y = LD[24]; IntVar Z = LD[25];

    //
    // Constraints
    //
    solver.Add(LD.AllDifferent());
    solver.Add(            B + A + L + L + E + T == BALLET);
    solver.Add(                C + E + L + L + O == CELLO);
    solver.Add(        C + O + N + C + E + R + T == CONCERT);
    solver.Add(                F + L + U + T + E == FLUTE);
    solver.Add(                F + U + G + U + E == FUGUE);
    solver.Add(                    G + L + E + E == GLEE);
    solver.Add(                    J + A + Z + Z == JAZZ);
    solver.Add(                    L + Y + R + E == LYRE);
    solver.Add(                    O + B + O + E == OBOE);
    solver.Add(                O + P + E + R + A == OPERA);
    solver.Add(                P + O + L + K + A == POLKA);
    solver.Add(        Q + U + A + R + T + E + T == QUARTET);
    solver.Add(S + A + X + O + P + H + O + N + E == SAXOPHONE);
    solver.Add(                S + C + A + L + E == SCALE);
    solver.Add(                    S + O + L + O == SOLO);
    solver.Add(                    S + O + N + G == SONG);
    solver.Add(        S + O + P + R + A + N + O == SOPRANO);
    solver.Add(                T + H + E + M + E == THEME);
    solver.Add(            V + I + O + L + I + N == VIOLIN);
    solver.Add(                W + A + L + T + Z == WALTZ);


    //
    // Search
    //
    DecisionBuilder db = solver.MakePhase(LD,
                                          Solver.CHOOSE_MIN_SIZE_LOWEST_MIN,
                                          Solver.ASSIGN_CENTER_VALUE);

    solver.NewSearch(db);

    String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    while (solver.NextSolution()) {
      for(int i = 0; i < num_letters; i++) {
        Console.WriteLine("{0}: {1,2}", str[i], LD[i].Value());
      }
      Console.WriteLine();
    }

    Console.WriteLine("\nWallTime: " + solver.WallTime() + "ms ");
    Console.WriteLine("Failures: " + solver.Failures());
    Console.WriteLine("Branches: " + solver.Branches());

    solver.EndSearch();

  }

  public static void Main(String[] args)
  {
    Solve();
  }
}