1 /* 2 * HistoricHomes.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 is a simple logic puzzle about houses. 41 * 42 * @author Radoslaw Szymanek 43 * @version 4.8 44 * <p> 45 * Each year the Glendale Women's Club sponsors a Historic Homes Tour in which 46 * five old houses are (with the owners' permission, of course) opened to the 47 * public. This year the five homes are on different streets (Azalea Drive, 48 * Crepe Myrtle Court, Jasmine Boulevard, Magnolia Street, and Oleander Road), 49 * and each was built in a different year (1860, 1870, 1890, 1900, and 1920). 50 * Can you give the order in which the tour visited the five homes (identifying 51 * them by street) and match each with its year? 52 * <p> 53 * 1. The home on Jasmine is 20 years older than the one on Azalea. 54 * 2. The third home on the tour was built in 1860. 55 * 3. The tour visited the home on Magnolia sometime before the one built in 1890. 56 * 4. The tour visited the home on Oleander (which wasn't the last of the five to 57 * be built) sometime before it visited the one on Jasmine, which in turn was 58 * seen sometime before the one built in 1900. 59 * <p> 60 * Determine: Order -- Street -- Year 61 */ 62 63 64 public class HistoricHomes extends ExampleFD { 65 model()66 @Override public void model() { 67 68 store = new Store(); 69 vars = new ArrayList<IntVar>(); 70 71 System.out.println("Program to solve Historic Homes logic puzzle"); 72 73 String streetName[] = {"street_Azalea_Drive", "street_Crepe_Myrtle_Court", "street_Jasmine_Boulevard", "street_Magnolia_Street", 74 "street_Oleander_Road",}; 75 76 int iAzalea_Drive = 0, /* iCrepe_Myrtle_Court = 1, */ iJasmine_Boulevard = 2, iMagnolia_Street = 3, iOleander_Road = 4; 77 78 String orderName[] = {"1st", "2nd", "3rd", "4th", "5th"}; 79 80 int i1st = 0, i2nd = 1, i3rd = 2, i4th = 3, i5th = 4; 81 82 IntVar order[] = new IntVar[5]; 83 IntVar street[] = new IntVar[5]; 84 85 for (int i = 0; i < 5; i++) { 86 87 order[i] = new IntVar(store, orderName[i]); 88 order[i].addDom(1860, 1860); 89 order[i].addDom(1870, 1870); 90 order[i].addDom(1890, 1890); 91 order[i].addDom(1900, 1900); 92 order[i].addDom(1920, 1920); 93 94 street[i] = new IntVar(store, streetName[i]); 95 street[i].addDom(1860, 1860); 96 street[i].addDom(1870, 1870); 97 street[i].addDom(1890, 1890); 98 street[i].addDom(1900, 1900); 99 street[i].addDom(1920, 1920); 100 vars.add(order[i]); 101 vars.add(street[i]); 102 } 103 104 store.impose(new Alldifferent(street)); 105 store.impose(new Alldifferent(order)); 106 107 // 1. The home on Jasmine is 20 years older than the one on Azalea. 108 109 store.impose(new XplusCeqZ(street[iAzalea_Drive], -20, street[iJasmine_Boulevard])); 110 111 // 2. The third home on the tour was built in 1860. 112 113 store.impose(new XeqC(order[i3rd], 1860)); 114 115 // 3. The tour visited the home on Magnolia sometime before the one 116 // built in 1890. 117 118 // Position of MagnoliaStreet within order array determines its order. 119 IntVar index1 = new IntVar(store, "index1", 1, 5); 120 store.impose(Element.choose(index1, order, street[iMagnolia_Street])); 121 // Position of value 1890 within order array determines its order. 122 IntVar index2 = new IntVar(store, "index2", 1, 5); 123 IntVar value1890 = new IntVar(store, "1890", 1890, 1890); 124 store.impose(Element.choose(index2, order, value1890)); 125 126 store.impose(new XltY(index1, index2)); 127 128 // implied constraints 129 store.impose(new XneqC(street[iMagnolia_Street], 1890)); 130 store.impose(new XneqC(order[i1st], 1890)); 131 store.impose(new XneqY(order[i5th], street[iMagnolia_Street])); 132 133 // 4. The tour visited the home on Oleander (which wasn't the last of 134 // the five to 135 // be built) sometime before it visited the one on Jasmine, which in 136 // turn was 137 // seen sometime before the one built in 1900. 138 139 store.impose(new XneqC(street[iOleander_Road], 1920)); 140 141 // Index 3 specifies the order for iOleander_Road 142 IntVar index3 = new IntVar(store, "index3", 1, 5); 143 store.impose(Element.choose(index3, order, street[iOleander_Road])); 144 // Index 4 specifies the order for Jasmine buiding. 145 IntVar index4 = new IntVar(store, "index4", 1, 5); 146 store.impose(Element.choose(index4, order, street[iJasmine_Boulevard])); 147 // index 2 specifies the order for building built at 1890. 148 IntVar index5 = new IntVar(store, "index5", 1, 5); 149 IntVar value1900 = new IntVar(store, "1900", 1900, 1900); 150 store.impose(Element.choose(index5, order, value1900)); 151 152 store.impose(new XltY(index3, index4)); 153 store.impose(new XltY(index4, index5)); 154 155 // implied constraints. 156 store.impose(new XneqY(street[iOleander_Road], order[i5th])); 157 store.impose(new XneqY(street[iOleander_Road], order[i4th])); 158 store.impose(new XneqC(street[iOleander_Road], 1900)); 159 160 store.impose(new XneqC(order[i1st], 1900)); 161 store.impose(new XneqC(order[i2nd], 1900)); 162 163 store.impose(new XneqY(order[i1st], street[iJasmine_Boulevard])); 164 store.impose(new XneqY(order[i5th], street[iJasmine_Boulevard])); 165 166 vars.add(index1); 167 vars.add(index2); 168 vars.add(index3); 169 vars.add(index4); 170 171 } 172 173 174 /** 175 * It executes the program to solve this simple logic puzzle. 176 * 177 * @param args parameters (none) 178 */ main(String args[])179 public static void main(String args[]) { 180 181 HistoricHomes example = new HistoricHomes(); 182 183 example.model(); 184 185 if (example.search()) 186 System.out.println("Solution(s) found"); 187 188 } 189 190 } 191