1 /* 2 * BlueberryMuffins.java 3 * This file is part of JaCoP. 4 * <p> 5 * JaCoP is a Java Constraint Programming solver. 6 * <p> 7 * Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek 8 * <p> 9 * This program is free software: you can redistribute it and/or modify 10 * it under the terms of the GNU Affero General Public License as published by 11 * the Free Software Foundation, either version 3 of the License, or 12 * (at your option) any later version. 13 * <p> 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU Affero General Public License for more details. 18 * <p> 19 * Notwithstanding any other provision of this License, the copyright 20 * owners of this work supplement the terms of this License with terms 21 * prohibiting misrepresentation of the origin of this work and requiring 22 * that modified versions of this work be marked in reasonable ways as 23 * different from the original version. This supplement of the license 24 * terms is in accordance with Section 7 of GNU Affero General Public 25 * License version 3. 26 * <p> 27 * You should have received a copy of the GNU Affero General Public License 28 * along with this program. If not, see <http://www.gnu.org/licenses/>. 29 */ 30 31 package org.jacop.examples.fd; 32 33 import org.jacop.constraints.*; 34 import org.jacop.core.IntVar; 35 import org.jacop.core.Store; 36 37 import java.util.ArrayList; 38 39 /** 40 * It solves a simple logic puzzle about blueberry muffins. 41 * 42 * @author Radoslaw Szymanek 43 * @version 4.8 44 * <p> 45 * Logic Puzzle: Blueberry Muffins 46 * <p> 47 * Description : 48 * <p> 49 * Daniel made a dozen blueberry muffins on Friday night -- and by 50 * the timehe was ready for brunch on Saturday, there were only 51 * two left. The other ten had been snitched by his housemates, 52 * all of whom had gotten up early because they had to work on 53 * Saturday. The fourhousemates include two men named Bill and 54 * Mark, and two women named Calla and Lynn; last names are Ellis, 55 * Ingham, Oakley, and Summers, and their differing professions 56 * are dogcatcher, flautist, secretary, and zookeeper. Can you 57 * discover each one's full name, profession, and number of 58 * muffins snitched? 59 * <p> 60 * 1. Each housemate snitched a different number of muffins from one to four. 61 * 2. Bill and Ellis snitched a total of six muffins. 62 * 3. The secretary (who is a woman) snitched more than the dogcatcher. 63 * 4. Mark snitched two more than Summers did. 64 * 5. The flautist snitched twice as many as Ms. Oakley did. 65 * 6. Calla's last name isn't Ingham. 66 * <p> 67 * Solution: 68 * <p> 69 * Calla Oakley dogcatcher 1 muffin 70 * Bill Summers flautist 2 muffins 71 * Lynn Ingham secretary 3 muffins 72 * Mark Ellis zookeeper 4 muffins 73 */ 74 75 76 public class BlueberryMuffins extends ExampleFD { 77 model()78 @Override public void model() { 79 80 // Constraint store created below. 81 82 store = new Store(); 83 vars = new ArrayList<IntVar>(); 84 85 System.out.println("Program to solve Blueberry Muffins "); 86 87 // String arrays with peoples' names. 88 89 String[] lastnames = {"Ellis", "Ingham", "Oakley", "Summers"}; 90 91 // Constant indexes to ease referring to variables denoting people. 92 int iellis = 0, iingham = 1, ioakley = 2, isummer = 3; 93 94 // String arrays with profession names. 95 96 String[] professionNames = {"dogcatcher", "flautist", "secretary", "zookeeper"}; 97 98 // Constant indexes to ease referring to profession variables. 99 100 int /* izookeeper = 0, */ idogcatcher = 1, iflautist = 2, isecretary = 3; 101 102 // String arrays with firstname. 103 104 String[] firstnames = {"Lynn", "Calla", "Bill", "Mark"}; 105 106 // Constant indexes to ease referring to firstname variables. 107 108 int ilynn = 0, icalla = 1, ibill = 2, imark = 3; 109 110 // String arrays with muffin numbers. 111 112 String[] muffinnumbers = {"muffin1", "muffin2", "muffin3", "muffin4"}; 113 int i1 = 0, i2 = 1, i3 = 2, i4 = 3; 114 115 // Arrays for variables. 116 117 IntVar person[] = new IntVar[4]; 118 IntVar last[] = new IntVar[4]; 119 IntVar profession[] = new IntVar[4]; 120 IntVar muffins[] = new IntVar[4]; 121 122 // All variables are created with domain 0..3. Variables from 123 // different arrays with the same values denote the same person. 124 125 for (int i = 0; i < 4; i++) { 126 last[i] = new IntVar(store, lastnames[i], 0, 3); 127 profession[i] = new IntVar(store, professionNames[i], 0, 3); 128 muffins[i] = new IntVar(store, muffinnumbers[i], 0, 3); 129 person[i] = new IntVar(store, firstnames[i], 0, 3); 130 vars.add(last[i]); 131 vars.add(profession[i]); 132 vars.add(muffins[i]); 133 vars.add(person[i]); 134 } 135 136 // It is not possible that one person had two lastnames, or 137 // two professions. 138 store.impose(new Alldifferent(person)); 139 store.impose(new Alldifferent(last)); 140 store.impose(new Alldifferent(profession)); 141 142 // 1. Each housemate snitched a different number of muffins from 143 // one to four. 144 store.impose(new Alldifferent(muffins)); 145 146 // Auxilary variables to help express clue number 2. 147 148 IntVar six = new IntVar(store, "six", 6, 6); 149 IntVar I1 = new IntVar(store, "temp1", 1, 4); 150 IntVar I2 = new IntVar(store, "temp2", 1, 4); 151 152 // I1 denotes number of muffins taken by Bill. 153 store.impose(Element.choose(I1, muffins, person[ibill])); 154 // I2 denotes number of muffins taken by Ellis. 155 store.impose(Element.choose(I2, muffins, last[iellis])); 156 // 2. Bill and Ellis snitched a total of six muffins. 157 store.impose(new XplusYeqZ(I1, I2, six)); 158 159 // 3. The secretary (who is a woman) snitched more than the dogcatcher. 160 161 // secretary is a women, so it must have had the same number 162 // as Calla or Lynn. 163 store.impose(new Or(new XeqY(profession[isecretary], person[icalla]), new XeqY(profession[isecretary], person[ilynn]))); 164 165 IntVar I3 = new IntVar(store, "temp3", 1, 4); 166 IntVar I4 = new IntVar(store, "temp4", 1, 4); 167 168 // I3 denotes number of muffins taken by secretary. 169 store.impose(Element.choose(I3, muffins, profession[isecretary])); 170 // I4 denotes number of muffins taken by dogcatcher 171 store.impose(Element.choose(I4, muffins, profession[idogcatcher])); 172 173 // secretary has snitched more muffins than the dogcatcher. 174 store.impose(new XgtY(I3, I4)); 175 176 // 4. Mark snitched two more than Summers did. 177 store.impose(new Or(new And(new XeqY(last[isummer], muffins[i1]), new XeqY(person[imark], muffins[i3])), 178 new And(new XeqY(last[isummer], muffins[i2]), new XeqY(person[imark], muffins[i4])))); 179 180 // 5. The flautist snitched twice as many as Ms. Oakley did. 181 store.impose(new Or(new And(new XeqY(last[ioakley], muffins[i1]), new XeqY(profession[iflautist], muffins[i2])), 182 new And(new XeqY(last[ioakley], muffins[i2]), new XeqY(profession[iflautist], muffins[i4])))); 183 184 // 6. Calla's last name isn't Ingham. 185 store.impose(new XneqY(person[icalla], last[iingham])); 186 187 } 188 189 190 /** 191 * It executes the program solving this puzzle. 192 * 193 * @param args no arguments are read. 194 */ main(String args[])195 public static void main(String args[]) { 196 197 BlueberryMuffins example = new BlueberryMuffins(); 198 199 example.model(); 200 201 if (example.search()) 202 System.out.println("Solution(s) found"); 203 204 } 205 206 } 207