| 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.generation; |
| 22 | |
| 23 | import java.util.ArrayList; |
| 24 | import java.util.HashMap; |
| 25 | import java.util.LinkedList; |
| 26 | import java.util.List; |
| 27 | import java.util.ListIterator; |
| 28 | import java.util.Map; |
| 29 | |
| 30 | import net.sourceforge.pseudoq.model.Coordinate; |
| 31 | import net.sourceforge.pseudoq.model.Grid; |
| 32 | import net.sourceforge.pseudoq.model.Region; |
| 33 | |
| 34 | /** |
| 35 | * Fills a grid with values by a recursive brute force search over all the empty |
| 36 | * cells in sequence, trying each cell's possible values in random order until |
| 37 | * the grid is filled. The first such completed grid is returned. |
| 38 | * @author <a href="http://sourceforge.net/users/stevensa">Andrew Stevens</a> |
| 39 | */ |
| 40 | public class SequentialGridFiller implements GridFiller { |
| 41 | /** Log4J logger */ |
| 42 | private static final org.apache.log4j.Logger log = |
| 43 | org.apache.log4j.LogManager.getLogger(SequentialGridFiller.class); |
| 44 | |
| 45 | private Map<Coordinate, Region> influences = null; |
| 46 | private Grid grid = null; |
| 47 | private int digits = 0; |
| 48 | private List<Coordinate> emptyCells = null; |
| 49 | private ListIterator<Coordinate> emptyCellsIterator = null; |
| 50 | |
| 51 | /** |
| 52 | * Creates a new instance of SequentialGridFiller. |
| 53 | */ |
| 54 | public SequentialGridFiller() { |
| 55 | } |
| 56 | |
| 57 | public void fill(Grid grid, Map<String, Region> regions, int digits) |
| 58 | throws GenerationException { |
| 59 | if (grid == null) { |
| 60 | throw new IllegalArgumentException("Can't fill a grid that doesn't exist"); |
| 61 | } |
| 62 | if (regions == null) { |
| 63 | throw new IllegalArgumentException("Can't fill grid with no regions"); |
| 64 | } |
| 65 | if (digits <= 0) { |
| 66 | throw new IllegalArgumentException("Can't fill grid with no digits"); |
| 67 | } |
| 68 | |
| 69 | this.grid = grid; |
| 70 | this.digits = digits; |
| 71 | |
| 72 | this.emptyCells = getEmptyCells(grid); |
| 73 | log.debug(this.emptyCells.size() + " empty cells"); |
| 74 | this.emptyCellsIterator = this.emptyCells.listIterator(); |
| 75 | |
| 76 | this.influences = new HashMap<Coordinate, Region>(); |
| 77 | for (Coordinate coord : emptyCells) { |
| 78 | influences.put(coord, getInfluences(coord, regions)); |
| 79 | } |
| 80 | |
| 81 | if (!fill()) { |
| 82 | throw new GenerationException("Couldn't complete grid"); |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | /** |
| 87 | * Fills the rest of the grid with values. At each step it tries one of |
| 88 | * the possible values for the next cell, the calls itself recursively. If |
| 89 | * there are no more possibilities, it backtracks and tries a different |
| 90 | * value in the earlier cell. |
| 91 | */ |
| 92 | private boolean fill() { |
| 93 | assert grid != null; |
| 94 | assert emptyCellsIterator != null; |
| 95 | assert influences != null; |
| 96 | assert digits > 0; |
| 97 | |
| 98 | if (emptyCellsIterator.hasNext()) { |
| 99 | // check next empty cell |
| 100 | Coordinate emptyCell = emptyCellsIterator.next(); |
| 101 | List<Integer> possibles = randomise( |
| 102 | getPossibles(grid, influences.get(emptyCell), digits)); |
| 103 | for (int i = 0; i <= possibles.size(); i++) { |
| 104 | if (i == possibles.size()) { |
| 105 | // all possibilities failed (or there were none), so backtrack |
| 106 | log.debug("backtrack " + emptyCellsIterator.previousIndex()); |
| 107 | grid.put(emptyCell, Integer.valueOf(0)); |
| 108 | return false; |
| 109 | } else { |
| 110 | log.debug("try " + possibles.get(i) + " in " + emptyCell.toString()); |
| 111 | grid.put(emptyCell, possibles.get(i)); |
| 112 | // recursively fill the rest of the grid |
| 113 | if (fill()) { |
| 114 | return true; |
| 115 | } else { |
| 116 | // can't complete grid from here, so try the next alternative |
| 117 | // (continue looping) |
| 118 | |
| 119 | // above call to fill() will move iterator on, so reset it |
| 120 | emptyCellsIterator.previous(); |
| 121 | } |
| 122 | } |
| 123 | } |
| 124 | } else { |
| 125 | // no more empty cells, grid is complete |
| 126 | log.debug("Generated grid:\n" + grid.toString()); |
| 127 | return true; |
| 128 | } |
| 129 | return false; |
| 130 | } |
| 131 | |
| 132 | /** |
| 133 | * Returns an ordered list of the coordinates of all the empty cells in a |
| 134 | * grid. The cells are ordered by scanning across each row of the grid in |
| 135 | * turn. Various other orderings have been tested, but this one turned out |
| 136 | * to be the fastest (least backtracking when filling the grid). Random |
| 137 | * order is a <em>really</em> bad idea; depending on grid size, it can be |
| 138 | * several orders of magnitude slower! |
| 139 | * @param grid The grid to scan. |
| 140 | * @return List of Coordinate of the empty cells. |
| 141 | */ |
| 142 | private List<Coordinate> getEmptyCells(Grid grid) { |
| 143 | List<Coordinate> emptyCells = new ArrayList<Coordinate>(); |
| 144 | |
| 145 | for (int i = 0; i < grid.getSize(); i++) { |
| 146 | for (int j = 0; j < grid.getSize(); j++) { |
| 147 | Coordinate coord = new Coordinate(i, j); |
| 148 | if (Integer.valueOf(0).equals(grid.get(coord))) { |
| 149 | emptyCells.add(coord); |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | |
| 154 | return emptyCells; |
| 155 | } |
| 156 | |
| 157 | /** |
| 158 | * Find all the cells that affect the possible values for a given cell. |
| 159 | * @param coord The coordinates of the cell of interest. |
| 160 | * @param regions Map of all the grid regions, for example, from |
| 161 | * {@link net.sourceforge.pseudoq.model.Puzzle#getRegions()}. |
| 162 | * @return Region of all the cells that might restrict the possible values. |
| 163 | * Does not include the cell itself. |
| 164 | */ |
| 165 | private Region getInfluences(Coordinate coord, Map<String, Region> regions) { |
| 166 | Region cellRegions = new Region(); |
| 167 | |
| 168 | // find all the Rows, Columns & Boxes that contain this cell |
| 169 | for (Region region : regions.values()) { |
| 170 | if (region.contains(coord) && region.getName() != null && |
| 171 | (region.getName().startsWith("Row ") || |
| 172 | region.getName().startsWith("Column ") || |
| 173 | region.getName().startsWith("Box "))) { |
| 174 | cellRegions.addAll(region); |
| 175 | } |
| 176 | } |
| 177 | // ignore the cell itself |
| 178 | cellRegions.remove(coord); |
| 179 | |
| 180 | return cellRegions; |
| 181 | } |
| 182 | |
| 183 | /** |
| 184 | * Find all the remaining possible values for a cell in the grid. |
| 185 | * @param grid The grid. |
| 186 | * @param region Region of all the cells affecting the one being tested. |
| 187 | * @param digits Maximum possible value. |
| 188 | * @return List of the remaining possible Integer values. |
| 189 | */ |
| 190 | private List<Integer> getPossibles(Grid grid, Region region, int digits) { |
| 191 | List<Integer> possibilities = new LinkedList<Integer>(); |
| 192 | |
| 193 | for (int i = 1; i <= digits; i++) { |
| 194 | possibilities.add(Integer.valueOf(i)); |
| 195 | } |
| 196 | for (Coordinate coord : region) { |
| 197 | Integer value = grid.get(coord); |
| 198 | if (value.intValue() > 0) { |
| 199 | possibilities.remove(value); |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | return possibilities; |
| 204 | } |
| 205 | |
| 206 | /** |
| 207 | * Shuffle the elements of a list into random order. The original list is |
| 208 | * not altered, so it should be thread safe. |
| 209 | * @param list List to be scrambled. |
| 210 | * @return New List containing all the elements of the original, but in |
| 211 | * random order. |
| 212 | */ |
| 213 | private <T> List<T> randomise(List<T> list) { |
| 214 | List<T> retval = new ArrayList<T>(); |
| 215 | List<T> copy = new ArrayList<T>(list); |
| 216 | |
| 217 | while (!copy.isEmpty()) { |
| 218 | int pos = (int) (Math.random() * copy.size()); |
| 219 | retval.add(copy.remove(pos)); |
| 220 | } |
| 221 | |
| 222 | return retval; |
| 223 | } |
| 224 | |
| 225 | } |