| 1 | /* |
| 2 | * Copyright (c) 2005 The PseudoQ Project. |
| 3 | * |
| 4 | * This file is part of PseudoQ. |
| 5 | * |
| 6 | * PseudoQ is free software; you can redistribute it and/or modify |
| 7 | * it under the terms of the GNU Lesser General Public License as published by |
| 8 | * the Free Software Foundation; either version 2.1 of the License, or |
| 9 | * (at your option) any later version. |
| 10 | * |
| 11 | * PseudoQ is distributed in the hope that it will be useful, |
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 | * GNU Lesser General Public License for more details. |
| 15 | * |
| 16 | * You should have received a copy of the GNU Lesser General Public License |
| 17 | * along with PseudoQ; if not, write to the Free Software |
| 18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
| 19 | */ |
| 20 | |
| 21 | package net.sourceforge.pseudoq.solver; |
| 22 | |
| 23 | import java.util.ArrayList; |
| 24 | import java.util.HashMap; |
| 25 | import java.util.Iterator; |
| 26 | import java.util.List; |
| 27 | import java.util.Map; |
| 28 | |
| 29 | import net.sourceforge.pseudoq.model.Coordinate; |
| 30 | import net.sourceforge.pseudoq.model.Grid; |
| 31 | import net.sourceforge.pseudoq.model.Puzzle; |
| 32 | |
| 33 | /** |
| 34 | * Abstract Solver base class. |
| 35 | * @author <a href="http://sourceforge.net/users/stevensa">Andrew Stevens</a> |
| 36 | */ |
| 37 | public abstract class AbstractSolver implements Solver { |
| 38 | /** Log4J logger */ |
| 39 | private static final org.apache.log4j.Logger log = |
| 40 | org.apache.log4j.LogManager.getLogger(AbstractSolver.class); |
| 41 | |
| 42 | protected Grid grid = null; |
| 43 | protected List<Strategy> strategies = new ArrayList<Strategy>(); |
| 44 | protected Map<String, Counter> counters = new HashMap<String, Counter>(); |
| 45 | |
| 46 | /** Creates a new instance of AbstractSolver */ |
| 47 | protected AbstractSolver(Puzzle puzzle) { |
| 48 | this.grid = (Grid) puzzle.getGrid().clone(); |
| 49 | |
| 50 | // setup(puzzle); |
| 51 | setupCounters(puzzle); |
| 52 | setupStrategies(puzzle); |
| 53 | |
| 54 | // pre-fill extra data from existing grid entries |
| 55 | for (Coordinate coord : grid.keySet()) { |
| 56 | int value = grid.get(coord).intValue(); |
| 57 | if (value != 0) { |
| 58 | place(coord, value); |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | public Solution solveEntirePuzzle() throws UnsolveablePuzzleException { |
| 64 | Solution solution = null; |
| 65 | List<SolutionStep> steps = new ArrayList<SolutionStep>(); |
| 66 | |
| 67 | while (grid.containsValue(Integer.valueOf(0))) { |
| 68 | steps.add(solveOneCell()); |
| 69 | } |
| 70 | log.debug("Solved."); |
| 71 | solution = new Solution(grid, steps); |
| 72 | return solution; |
| 73 | } |
| 74 | |
| 75 | public SolutionStep solveOneCell() throws UnsolveablePuzzleException { |
| 76 | SolutionStep nextStep = null; |
| 77 | |
| 78 | if (grid.containsValue(Integer.valueOf(0))) { |
| 79 | for (Iterator<Strategy> strategyIterator = strategies.iterator(); |
| 80 | nextStep == null && strategyIterator.hasNext();) { |
| 81 | Strategy strategy = strategyIterator.next(); |
| 82 | try { |
| 83 | nextStep = strategy.evaluate(); |
| 84 | } catch (ObsoleteStrategyException ignored) { |
| 85 | if (log.isDebugEnabled()) |
| 86 | log.debug("removing strategy " + strategy.toString() + |
| 87 | " from future consideration."); |
| 88 | strategyIterator.remove(); |
| 89 | } |
| 90 | } |
| 91 | if (nextStep == null) { |
| 92 | // tried every strategy, without success |
| 93 | throw new UnsolveablePuzzleException("Ran out of ideas. Either " + |
| 94 | "there is no\nunique solution, or I'm not clever enough..."); |
| 95 | } |
| 96 | } else { |
| 97 | log.warn("solveOneCell called when grid already complete"); |
| 98 | } |
| 99 | grid.put(nextStep.getCoordinate(), nextStep.getValue()); |
| 100 | place(nextStep.getCoordinate(), nextStep.getValue()); |
| 101 | log.debug(nextStep); |
| 102 | |
| 103 | return nextStep; |
| 104 | } |
| 105 | |
| 106 | protected abstract void setupCounters(Puzzle puzzle); |
| 107 | |
| 108 | protected abstract void setupStrategies(Puzzle puzzle); |
| 109 | |
| 110 | // protected abstract void place(Coordinate coord, int value); |
| 111 | protected void place(Coordinate coord, int value) { |
| 112 | for (Counter counter : counters.values()) { |
| 113 | counter.place(coord, value); |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | protected int counterValue(String counterKey) { |
| 118 | Counter counter = counters.get(counterKey); |
| 119 | if (counter == null) { |
| 120 | throw new IllegalStateException("Counter " + counterKey + " not found."); |
| 121 | } else { |
| 122 | return counter.getCount(); |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | } |