Zebra Puzzle in Java - Javatpoint
The zebra puzzle is a complex puzzle that requires a lot of effort and mental exercise to solve the puzzle. Sometimes is also known as Einstein's Puzzle or Einstein's Riddle because it is invented by the famous German physicist Albert Einstein.
The puzzle is widely used in the evaluation of computer algorithms for solving constraint satisfaction problems (CSP). Most of the AI problems can be modeled as constraint satisfaction problems (CSP).
Generally, the CSP problem is composed of a finite set of variables, each of which has a finite domain of values, and a set of constraints. Each constraint is defined over some subset of the original set of variables and restricts the values these variables can simultaneously take. The task is to find an assignment of a value for each variable such that the assignments satisfy all the constraints, in some problems, the goal is to find all such assignments.
Therefore, we can define CSP as a set of objects whose state must satisfy a number of constraints or limitations.
Some popular examples of the problem are the N-queens problem, graph coloring problem, crossword puzzle, etc.
The general approach to solving a CSP is the generate-and-test method. Each possible assignment of values to variables is systematically generated and then tested to see if it satisfies all the constraints. The first assignment that satisfies all the constraints is the solution. In the worst-case (or when we are trying to find all the solutions for a CSP, the number of assignments to be considered is the size of the Cartesian product of all the variable domains. Thus, the time complexity of this approach is exponential in the number of variables. Empirically this method performs very poorly.
Randomized generate-and-test algorithms that select the assignments to test at random in accord with some biased distribution (e.g. the distribution might be biased by the most recently tested assignments as in randomized hill-climbing) can sometimes perform extremely well, but unfortunately, lose systematicity. That is, these randomized methods are unable to prove that no solution exists since they do not necessarily test all assignments.
Generally, there are the following three approaches to solve the CSP:
The puzzle has several variants. Other versions of the puzzle have various differences from the Life International puzzle, in which various colors, nationalities, cigarette brands, drinks, and pets are substituted. But the logic will not change. The following variant was published in Life International.
Note that each of the five houses is painted a different color, and their residents are of different national extractions, own different pets, drink different beverages, and smoke different brands of American cigarettes. One other thing: in statement 5, left means your's right.
The question is, who owns the zebra? Additionally, list the solution for all the houses. Optionally, show the solution is unique.
In the last few years, several ways have been presented for solving this problem such as backtracking, minimum remaining values (MRV), forward chaining (FC), minimum conflicts, etc. But in this section, we will use the general approach i.e. generate-and-test.
From the above 16 constraints (statements), let's summarize the attributes of the puzzle.
Color: red, green, ivory, yellow, blue
Nationality: Englishman, Spaniard, Ukrainian, Norwegian, Japanese
Drink: coffee, tea, milk, orange juice, Water
Smoke: Old Gold, Kools, Chesterfields, Lucky Strike, Parliaments
Pet: dog, snail, fox, horse, Zebra
Let's organize the given data in table form for better understanding.
The following Java program includes the following four user-defined classes:
Zebra.java
it = puzzleTable.iterator(); it.hasNext(); ) { boolean validLine = true; PossibleLine possibleLine = it.next(); if (possibleLine.leftNeighbor != null) { PossibleLine neighbor = possibleLine.leftNeighbor; if (neighbor.order 5) { validLine = false; it.remove(); } } if (validLine && possibleLine.rightNeighbor != null) { PossibleLine neighbor = possibleLine.rightNeighbor; if (neighbor.order 5) { it.remove(); } } } System.out.println("After removing out of bound neighbors, remains " + puzzleTable.size() + " lines."); //Setting left and right neighbors for (PossibleLine puzzleLine : puzzleTable) { for (PossibleLine leftNeighbor : puzzleLine.neighbors) { PossibleLine rightNeighbor = leftNeighbor.copy(); //make it left neighbor leftNeighbor.order = puzzleLine.order - 1; if (puzzleTable.contains(leftNeighbor)) { if (puzzleLine.leftNeighbor != null) puzzleLine.leftNeighbor.merge(leftNeighbor); else puzzleLine.setLeftNeighbor(leftNeighbor); } rightNeighbor.order = puzzleLine.order + 1; if (puzzleTable.contains(rightNeighbor)) { if (puzzleLine.rightNeighbor != null) puzzleLine.rightNeighbor.merge(rightNeighbor); else puzzleLine.setRightNeighbor(rightNeighbor); } } } int iteration = 1; int lastSize = 0; //Recursively validate against neighbor rules while (puzzleTable.size() > 5 && lastSize != puzzleTable.size()) { lastSize = puzzleTable.size(); puzzleTable.clearLineCountFlags(); recursiveSearch(null, puzzleTable, -1); constraints.clear(); // Assuming we'll get at leas one valid line each iteration, we create // a set of new rules with lines which have no more then one instance of same OrderId. for (int i = 1; i !constraints.accepts(puzzleLine)); System.out.println("After " + iteration + " recursive iteration, remains " + puzzleTable.size() + " lines"); iteration++; } // Print the results System.out.println("-------------------------------------------"); if (puzzleTable.size() == 5) { for (PossibleLine puzzleLine : puzzleTable) { System.out.println(puzzleLine.getWholeLine()); } } else System.out.println("Sorry, solution not found!"); } private void addPossibleNeighbors( PossibleLines constraints, Integer orderId, String nation, String color, String animal, String drink, String cigarette) { boolean validLine = true; PossibleLine pzlLine = new PossibleLine(orderId, nation, color, animal, drink, cigarette); // Checking against a set of knowing facts if (constraints.accepts(pzlLine)) { // Adding rules of neighbors if (cigarette.equals("Blend") && (animal.equals("Cats") || drink.equals("Water"))) validLine = false; if (cigarette.equals("Dunhill") && animal.equals("Horse")) validLine = false; if (validLine) { puzzleTable.add(pzlLine); //set neighbors constraints if (color.equals("Green")) { pzlLine.setRightNeighbor( new PossibleLine(null, null, "White", null, null, null)); } if (color.equals("White")) { pzlLine.setLeftNeighbor( new PossibleLine(null, null, "Green", null, null, null)); } // if (animal.equals("Cats") && !cigarette.equals("Blend")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null, "Blend")); } if (cigarette.equals("Blend") && !animal.equals("Cats")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, "Cats", null , null)); } // if (drink.equals("Water") && !animal.equals("Cats") && !cigarette.equals("Blend")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null, "Blend")); } if (cigarette.equals("Blend") && !drink.equals("Water")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, null, "Water" , null)); } // if (animal.equals("Horse") && !cigarette.equals("Dunhill")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null, "Dunhill")); } if (cigarette.equals("Dunhill") && !animal.equals("Horse")) { pzlLine.neighbors.add(new PossibleLine(null, null, null, "Horse", null, null)); } } } } // Recursively checks the input set to ensure each line has right neighbor. // Neighbors can be of three type, left, right or undefined. // Direction: -1 left, 0 undefined, 1 right private boolean recursiveSearch(PossibleLine pzzlNodeLine, PossibleLines possibleLines, int direction) { boolean validLeaf = false; boolean hasNeighbor; PossibleLines puzzleSubSet; for (Iterator it = possibleLines.iterator(); it.hasNext(); ) { PossibleLine pzzlLeafLine = it.next(); validLeaf = false; hasNeighbor = pzzlLeafLine.hasNeighbor(direction); if (hasNeighbor) { puzzleSubSet = puzzleTable.getSimilarLines(pzzlLeafLine.getNeighbor(direction)); if (puzzleSubSet != null) { if (pzzlNodeLine != null) validLeaf = puzzleSubSet.contains(pzzlNodeLine); else validLeaf = recursiveSearch(pzzlLeafLine, puzzleSubSet, -1 * direction); } } if (!validLeaf && pzzlLeafLine.hasNeighbor(-1 * direction)) { hasNeighbor = true; puzzleSubSet = puzzleTable.getSimilarLines(pzzlLeafLine.getNeighbor(-1 * direction)); if (puzzleSubSet != null) { if (pzzlNodeLine != null) validLeaf = puzzleSubSet.contains(pzzlNodeLine); else validLeaf = recursiveSearch(pzzlLeafLine, puzzleSubSet, direction); } } if (pzzlNodeLine != null && validLeaf) return true; if (pzzlNodeLine == null && hasNeighbor && !validLeaf) { it.remove(); } if (pzzlNodeLine == null) { if (hasNeighbor && validLeaf) { possibleLines.riseLineCountFlags(pzzlLeafLine.order); } if (!hasNeighbor) { possibleLines.riseLineCountFlags(pzzlLeafLine.order); } } } return validLeaf; } } public static void main(String[] args) { Solver solver = new Solver(); solver.solve(); } static class PossibleLines extends LinkedHashSet { private final int[] count = new int[5]; public PossibleLine get(int index) { return ((PossibleLine) toArray()[index]); } public PossibleLines getSimilarLines(PossibleLine searchLine) { PossibleLines puzzleSubSet = new PossibleLines(); for (PossibleLine possibleLine : this) { if (possibleLine.getCommonFactsCount(searchLine) == searchLine.getFactsCount()) puzzleSubSet.add(possibleLine); } if (puzzleSubSet.isEmpty()) return null; return puzzleSubSet; } public boolean contains(PossibleLine searchLine) { for (PossibleLine puzzleLine : this) { if (puzzleLine.getCommonFactsCount(searchLine) == searchLine.getFactsCount()) return true; } return false; } public boolean accepts(PossibleLine searchLine) { int passed = 0; int notpassed = 0; for (PossibleLine puzzleSetLine : this) { int lineFactsCnt = puzzleSetLine.getFactsCount(); int comnFactsCnt = puzzleSetLine.getCommonFactsCount(searchLine); if (lineFactsCnt != comnFactsCnt && lineFactsCnt != 0 && comnFactsCnt != 0) { notpassed++; } if (lineFactsCnt == comnFactsCnt) passed++; } return passed >= 0 && notpassed == 0; } public void riseLineCountFlags(int lineOrderId) { count[lineOrderId - 1]++; } public void clearLineCountFlags() { Arrays.fill(count, 0); } public int getLineCountByOrderId(int lineOrderId) { return count[lineOrderId - 1]; } } static class PossibleLine { Integer order; String nation; String color; String animal; String drink; String cigarette; PossibleLine rightNeighbor; PossibleLine leftNeighbor; Set neighbors = new LinkedHashSet(); public PossibleLine(Integer order, String nation, String color, String animal, String drink, String cigarette) { this.animal = animal; this.cigarette = cigarette; this.color = color; this.drink = drink; this.nation = nation; this.order = order; } @Override public boolean equals(Object obj) { return obj instanceof PossibleLine && getWholeLine().equals(((PossibleLine) obj).getWholeLine()); } public int getFactsCount() { int facts = 0; facts += order != null ? 1 : 0; facts += nation != null ? 1 : 0; facts += color != null ? 1 : 0; facts += animal != null ? 1 : 0; facts += cigarette != null ? 1 : 0; facts += drink != null ? 1 : 0; return facts; } private static int common(Object a, Object b) { return a != null && Objects.equals(a, b) ? 1 : 0; } public int getCommonFactsCount(PossibleLine facts) { return common(order, facts.order) + common(nation, facts.nation) + common(color, facts.color) + common(animal, facts.animal) + common(cigarette, facts.cigarette) + common(drink, facts.drink); } public void setLeftNeighbor(PossibleLine leftNeighbor) { this.leftNeighbor = leftNeighbor; this.leftNeighbor.order = order - 1; } public void setRightNeighbor(PossibleLine rightNeighbor) { this.rightNeighbor = rightNeighbor; this.rightNeighbor.order = order + 1; } public boolean hasNeighbor(int direction) { return getNeighbor(direction) != null; } public PossibleLine getNeighbor(int direction) { if (direction
Output:
After general rule set validation, remains 60 lines. After removing out of bound neighbors, remains 52 lines. After 1 recursive iteration, remains 17 lines After 2 recursive iteration, remains 6 lines After 3 recursive iteration, remains 5 lines ------------------------------------------- 1 - Norwegian - Yellow - Cats - Water - Dunhill 2 - Danish - Blue - Horse - Tea - Blend 3 - English - Red - Birds - Milk - Pall Mall 4 - German - Green - Zebra - Coffee - Prince 5 - Swedish - White - Dog - Beer - Blue Master
Next TopicDisplay Unique Rows in a Binary Matrix in Java
For Videos Join Our Youtube Channel: Join Now
Feedback
- Send your Feedback to [email protected]
Help Others, Please Share
Learn Latest Tutorials
Address: G-13, 2nd Floor, Sec-3
Contact No: 0120-4256464, 9990449935
© Copyright 2011-2021 www.javatpoint.com. All rights reserved. Developed by JavaTpoint.
