1 /* 2 * SiblingUproar.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.Alldifferent; 34 import org.jacop.constraints.Element; 35 import org.jacop.constraints.XeqY; 36 import org.jacop.constraints.XneqY; 37 import org.jacop.core.IntVar; 38 import org.jacop.core.Store; 39 40 import java.util.ArrayList; 41 42 /** 43 * It is quite complex logic puzzle about siblings. 44 * 45 * @author Krzysztof "Vrbl" Wrobel, Wioletta "Vuka" Kruzolek, and Radoslaw Szymanek 46 * @version 4.8 47 * <p> 48 * This is quite difficult logic puzzle to be modeled and solved by CP. 49 * <p> 50 * Mrs. Wheatley returned home from her job to find the household in a 51 * turmoil of arguments. Each of her five teenagers (three boys named 52 * Bryan, Russell, and Stuart, and two girls named Nina and Paula) had 53 * gotten angry at one of his or her siblings for a different reason 54 * (finished cereal, let dog in room, used up hot water, failed to return 55 * rollerblades, and hogged television) and had decided to retaliate in a 56 * different way (knocked over chess game, let gerbil out of cage, hung 57 * up on friend, removed light bulbs, and hid violin). 58 * <p> 59 * After a few futile minutes of trying to sort out blame, 60 * Mrs. Wheatley called a halt to the arguments by declaring everyone 61 * equally guilty and giving each a different chore around the house 62 * as that evening's punishment (cleaning the attic, basement, or garage, 63 * or washing the Venetian blinds or windows). Can you discover, for 64 * each child, the sibling he or she was initially angry at, the reason 65 * for the anger, the retaliatory measure he or she took, and the chore 66 * meted out to each child? 67 * <p> 68 * 1. No one was originally angry at the sibling who was angry at him or 69 * her. 70 * <p> 71 * 2. The boy who was angry at the sibling who used up all the hot water 72 * taking a shower retaliated against him or her by removing all the 73 * light bulbs from his or her room; the child who was angry at this boy 74 * was later punished by being sent to sweep the basement. 75 * <p> 76 * 3. The five siblings are: Paula, the person who was angry at Paula, 77 * the person who was angry because a sibling was hogging the television, 78 * the child who was told to straighten the attic, and a child to didn't 79 * remove a sibling's light bulbs or hide a sibling's violin. 80 * <p> 81 * 4. The child who was angry at Stuart was punished by being told to wash 82 * the Venetian blinds. 83 * <p> 84 * 5. Russell was punished by being sent to clean out a section of the garage. 85 * <p> 86 * 6. The child who let the dog in a sibling's room didn't retaliate against another sibling by knocking over a chess game that he or she was playing. 87 * <p> 88 * 7. The child who was hogging the television was angry at a sibling who wasn't punished by being told to straighten up the attic or wash the windows. 89 * <p> 90 * 8. In retaliation, one person hid the violin belonging to the person who was angry at Paula. 91 * <p> 92 * 9. Bryan and the person who was punished by being told to wash the 93 * windows are, in same order, the child who was angry at the sibling 94 * who didn't return the rollerblades and the one who retaliated against 95 * a sibling by knocking over a chess game in progress. 96 * <p> 97 * 10. Stuart and the person who was angry at Nina are, in some order, the child 98 * who was angry at the person who finished the best cereal in the house and the one who retaliated against a sibling by hanging up on his or her best friend. 99 * <p> 100 * Determine: Sibling - Angry at - Reason - Retaliation - Chore 101 */ 102 103 public class SiblingUproar extends ExampleFD { 104 model()105 @Override public void model() { 106 107 // Array of FDV's which will be used during search. 108 vars = new ArrayList<IntVar>(); 109 store = new Store(); 110 111 System.out.println("Problem name: Sibling Uproar "); 112 113 // Specification of children names 114 String[] childrenNames = {"Brian", "Russell", "Stuart", "Nina", "Paula"}; 115 116 // Creation of indexes for ease of referring 117 int iBrian = 0, iRussell = 1, iStuart = 2, iNina = 3, iPaula = 4; 118 119 // Specification of being angry at someone. 120 String[] angryatNames = {"angryAtBrian", "angryAtRussell", "angryAtStuart", "angryAtNina", "angryAtPaula"}; 121 122 // Creation of indexes for ease of referring 123 int jBrian = 0, jRussell = 1, jStuart = 2, jNina = 3, jPaula = 4; 124 125 // Specification of the reasons for being angry. 126 String[] reasonNames = 127 {"finished_cereal", "let_dog_in_room", "used_up_hot_water", "failed_to_return_rollerblades", "hogged_television"}; 128 // Creation of indexes for ease of referring 129 int ifinished_cereal = 0, ilet_dog_in_room = 1, iused_up_hot_water = 2, ifailed_to_return_rollerblades = 3, ihogged_television = 4; 130 131 // Specification of different types of revenge. 132 String[] wayNames = {"knocked_over_chess_game", "let_gerbil_out_of_cage", "hung_up_on_friend", "removed_light_bulbs", "hid_violin"}; 133 134 // Creation of indexes for ease of referring 135 int iknocked_over_chess_game = 0, /* ilet_gerbil_out_of_cage = 1, */ 136 ihung_up_on_friend = 2, iremoved_light_bulbs = 3, ihid_violin = 4; 137 138 // Specification of different punishment. 139 String[] choreNames = 140 {"cleaning_the_attic", "cleaning_the_basement", "cleaning_the_garage", "washing_the_blinds", "washing_the_windows"}; 141 // Creation of indexes for ease of referring 142 int icleaning_the_attic = 0, icleaning_the_basement = 1, icleaning_the_garage = 2, iwashing_the_blinds = 3, iwashing_the_windows = 143 4; 144 145 // Creation of FDV's array 146 IntVar children[] = new IntVar[5]; 147 IntVar angryat[] = new IntVar[5]; 148 IntVar reason[] = new IntVar[5]; 149 IntVar way[] = new IntVar[5]; 150 IntVar chore[] = new IntVar[5]; 151 152 // All variables can have five values, as they are five children, five 153 // types of activities, etc. 154 for (int i = 0; i < 5; i++) { 155 children[i] = new IntVar(store, childrenNames[i], 1, 5); 156 angryat[i] = new IntVar(store, angryatNames[i], 1, 5); 157 reason[i] = new IntVar(store, reasonNames[i], 1, 5); 158 way[i] = new IntVar(store, wayNames[i], 1, 5); 159 chore[i] = new IntVar(store, choreNames[i], 1, 5); 160 vars.add(children[i]); 161 vars.add(angryat[i]); 162 vars.add(reason[i]); 163 vars.add(way[i]); 164 vars.add(chore[i]); 165 } 166 167 // Each child has a different id 168 store.impose(new Alldifferent(children)); 169 // Only one child can be angry at the same person. 170 store.impose(new Alldifferent(angryat)); 171 // Each child is angry for a different reason. 172 store.impose(new Alldifferent(reason)); 173 // Each child has chosen a different type of the revenge. 174 store.impose(new Alldifferent(way)); 175 // Each child is punished ina different way. 176 store.impose(new Alldifferent(chore)); 177 178 // Auxilary variables. 179 IntVar x1 = new IntVar(store, "x1", 1, 5); 180 IntVar x2 = new IntVar(store, "x2", 1, 5); 181 IntVar x3 = new IntVar(store, "x3", 1, 5); 182 IntVar x4 = new IntVar(store, "x4", 1, 5); 183 IntVar x5 = new IntVar(store, "x5", 1, 5); 184 IntVar y1 = new IntVar(store, "y1", 1, 5); 185 IntVar y2 = new IntVar(store, "y2", 1, 5); 186 IntVar y3 = new IntVar(store, "y3", 1, 5); 187 IntVar y4 = new IntVar(store, "y4", 1, 5); 188 IntVar y5 = new IntVar(store, "y5", 1, 5); 189 190 // Constraints to connect variables angryat and children. 191 // y1=angryat[x1] denotes child y1 angry at x1. 192 store.impose(Element.choose(x1, angryat, y1)); 193 store.impose(Element.choose(y1, children, x1)); 194 store.impose(Element.choose(x2, angryat, y2)); 195 store.impose(Element.choose(y2, children, x2)); 196 store.impose(Element.choose(x3, angryat, y3)); 197 store.impose(Element.choose(y3, children, x3)); 198 store.impose(Element.choose(x4, angryat, y4)); 199 store.impose(Element.choose(y4, children, x4)); 200 store.impose(Element.choose(x5, angryat, y5)); 201 store.impose(Element.choose(y5, children, x5)); 202 203 IntVar xs[] = {x1, x2, x3, x4, x5}; 204 // The same relation as for angry at and children. 205 store.impose(new Alldifferent(xs)); 206 207 for (IntVar v : xs) 208 vars.add(v); 209 IntVar ys[] = {y1, y2, y3, y4, y5}; 210 for (IntVar v : ys) 211 vars.add(v); 212 213 // 1. No one was originally angry at the sibling who was angry at him or 214 // her. 215 // Bryan is not angry at somebody who is angry at Bryan. 216 store.impose(new XneqY(children[iBrian], angryat[jBrian])); 217 // Russell ... 218 store.impose(new XneqY(children[iRussell], angryat[jRussell])); 219 store.impose(new XneqY(children[iStuart], angryat[jStuart])); 220 store.impose(new XneqY(children[iNina], angryat[jNina])); 221 store.impose(new XneqY(children[iPaula], angryat[jPaula])); 222 223 // 2. The boy who was angry at the sibling who used up all the hot water 224 // taking a shower retaliated against him 225 // or her by removing all the light bulbs from his or her room; 226 // the child who was angry at this boy was later punished by being sent 227 // to sweep the basement. 228 229 // auxilary variable, boys are denoted by values from 1 to 3. 230 IntVar boy = new IntVar(store, "boy", 1, 3); 231 IntVar s = new IntVar(store, "sibling", 1, 5); 232 vars.add(boy); 233 vars.add(s); 234 235 store.impose(Element.choose(boy, children, way[iremoved_light_bulbs])); 236 store.impose(Element.choose(s, angryat, reason[iused_up_hot_water])); 237 store.impose(new XeqY(way[iremoved_light_bulbs], reason[iused_up_hot_water])); 238 239 IntVar ktos = new IntVar(store, "somebody", 1, 5); 240 store.impose(Element.choose(boy, angryat, ktos)); 241 store.impose(new XeqY(chore[icleaning_the_basement], ktos)); 242 vars.add(ktos); 243 244 // 3. The five siblings are: Paula, the person who was angry at Paula, 245 // the person who was angry because a sibling was hogging the 246 // television, the child who was told to straighten the attic, 247 // and a child to didn't remove a sibling's light bulbs or hide a 248 // sibling's violin. 249 250 IntVar someone = new IntVar(store, "someone", 1, 5); 251 store.impose(Element.choose(someone, angryat, reason[ihogged_television])); 252 vars.add(someone); 253 254 IntVar Z = new IntVar(store, "Z", 1, 5); 255 store.impose(new XneqY(Z, way[iremoved_light_bulbs])); 256 store.impose(new XneqY(Z, way[ihid_violin])); 257 vars.add(Z); 258 259 IntVar all[] = {children[iPaula], angryat[jPaula], reason[ihogged_television], chore[icleaning_the_attic], Z};// piatka 260 // rodzenstwa 261 store.impose(new Alldifferent(all)); 262 263 // 4. The child who was angry at Stuart was punished by being told to 264 // wash the Venetian blinds. 265 266 store.impose(new XeqY(angryat[jStuart], chore[iwashing_the_blinds])); 267 268 // 5. Russell was punished by being sent to clean out a section of the 269 // garage. 270 271 store.impose(new XeqY(chore[icleaning_the_garage], children[iRussell])); 272 273 // 6. The child who let the dog in a sibling's room didn't retaliate 274 // against another sibling by knocking over a chess game 275 // that he or she was playing. 276 277 store.impose(new XneqY(reason[ilet_dog_in_room], way[iknocked_over_chess_game])); 278 279 // 7. The child who was hogging the television was angry at a sibling 280 // who wasn't punished by being told to 281 // straighten up the attic or wash the windows. 282 283 store.impose(new XneqY(reason[ihogged_television], chore[icleaning_the_attic])); 284 store.impose(new XneqY(reason[ihogged_television], chore[iwashing_the_windows])); 285 286 // 8. In retaliation, one person hid the violin belonging to the person 287 // who was angry at Paula. 288 289 IntVar imie = new IntVar(store, "imie", 1, 5); 290 store.impose(Element.choose(imie, angryat, way[ihid_violin])); 291 store.impose(Element.choose(imie, children, angryat[jPaula])); 292 vars.add(imie); 293 294 // 9. Bryan and the person who was punished by being told to wash the 295 // windows are, in same order, 296 // the child who was angry at the sibling who didn't return the 297 // rollerblades 298 // and the one who retaliated against a sibling by knocking over a chess 299 // game in progress. 300 301 store.impose(new XeqY(way[iknocked_over_chess_game], children[iBrian])); 302 store.impose(new XeqY(chore[iwashing_the_windows], reason[ifailed_to_return_rollerblades])); 303 304 // 10. Stuart and the person who was angry at Nina are, in some order, 305 // the child who 306 // was angry at the person who finished the best cereal in the house and 307 // the one who 308 // retaliated against a sibling by hanging up on his or her best friend. 309 310 IntVar kto = new IntVar(store, "kto", 1, 5); 311 store.impose(Element.choose(kto, children, reason[ifinished_cereal])); 312 store.impose(new XeqY(angryat[jNina], reason[ifinished_cereal])); 313 store.impose(new XeqY(children[iStuart], way[ihung_up_on_friend])); 314 vars.add(kto); 315 316 } 317 318 /** 319 * It executes the program to solve this logic puzzle. 320 * 321 * @param args no argument is used. 322 */ main(String args[])323 public static void main(String args[]) { 324 325 SiblingUproar example = new SiblingUproar(); 326 327 example.model(); 328 329 if (example.search()) 330 System.out.println("Solution(s) found"); 331 332 } 333 334 } 335