sudoku-java
changeset 14:1bea104dd817
Added findExclusiveCell and corresponding cell search.
author | David McLeish <dave@mcleish.id.au> |
---|---|
date | Sun Nov 07 13:20:27 2010 +1100 (2010-11-07) |
parents | 2a535c274e7f |
children | ec017ba6ab61 |
files | src/au/id/mcleish/sudoku/SudokuGrid.java |
line diff
1.1 --- a/src/au/id/mcleish/sudoku/SudokuGrid.java Sun Nov 07 10:20:30 2010 +1100 1.2 +++ b/src/au/id/mcleish/sudoku/SudokuGrid.java Sun Nov 07 13:20:27 2010 +1100 1.3 @@ -12,9 +12,11 @@ 1.4 1.5 private final int stringColumnWidth; 1.6 1.7 - private SudokuCell[][] grid; 1.8 + private Cell[][] grid; 1.9 private int numEmpty; 1.10 1.11 + private ArrayList<ExclusiveSetConstraint> constraints; 1.12 + 1.13 private final List<Integer> orderedValues; 1.14 1.15 public static SudokuGrid newPuzzle(int cellWidth, int cellHeight) { 1.16 @@ -58,21 +60,23 @@ 1.17 1.18 orderedValues = Collections.unmodifiableList(values); 1.19 1.20 - grid = new SudokuCell[numValues][numValues]; 1.21 + grid = new Cell[numValues][numValues]; 1.22 for (int y = 0; y < numValues; ++y) 1.23 for (int x = 0; x < numValues; ++x) 1.24 - grid[x][y] = new SudokuCell(); 1.25 + grid[x][y] = new Cell(); 1.26 + 1.27 + constraints = new ArrayList<ExclusiveSetConstraint>(numValues * numValues * 3); 1.28 1.29 for (int x = 0; x < numValues; ++x) 1.30 { 1.31 - SudokuExclusiveSet rowConstraint = new SudokuExclusiveSet(); 1.32 + ExclusiveSetConstraint rowConstraint = new ExclusiveSetConstraint(); 1.33 for (int y = 0; y < numValues; ++y) 1.34 grid[x][y].addConstraint(rowConstraint); 1.35 } 1.36 1.37 for (int y = 0; y < numValues; ++y) 1.38 { 1.39 - SudokuExclusiveSet rowConstraint = new SudokuExclusiveSet(); 1.40 + ExclusiveSetConstraint rowConstraint = new ExclusiveSetConstraint(); 1.41 for (int x = 0; x < numValues; ++x) 1.42 grid[x][y].addConstraint(rowConstraint); 1.43 } 1.44 @@ -81,7 +85,7 @@ 1.45 { 1.46 for (int cellY = 0; cellY < blockWidth; ++cellY) 1.47 { 1.48 - SudokuExclusiveSet blockConstraint = new SudokuExclusiveSet(); 1.49 + ExclusiveSetConstraint blockConstraint = new ExclusiveSetConstraint(); 1.50 for (int dx = 0; dx < blockWidth; ++dx) 1.51 for (int dy = 0; dy < blockHeight; ++dy) 1.52 grid[cellX*blockWidth + dx][cellY*blockHeight + dy].addConstraint(blockConstraint); 1.53 @@ -98,16 +102,16 @@ 1.54 } 1.55 1.56 public boolean solve(Random random, boolean revert, int depth) { 1.57 - List<SudokuCell> modified = new ArrayList<SudokuCell>(); 1.58 + List<Cell> modified = new ArrayList<Cell>(); 1.59 1.60 try { 1.61 List<Integer> values = orderedValues; 1.62 1.63 - SudokuCell mostConstrained = null; 1.64 + Cell mostConstrained = null; 1.65 while (mostConstrained == null && numEmpty > 0) { 1.66 int minAvailable = Integer.MAX_VALUE; 1.67 - for (SudokuCell[] row : grid) { 1.68 - for (SudokuCell cell : row) { 1.69 + for (Cell[] row : grid) { 1.70 + for (Cell cell : row) { 1.71 if (cell.isEmpty()) { 1.72 int n = cell.numAvailable(); 1.73 if (n == 0) { 1.74 @@ -132,6 +136,17 @@ 1.75 } 1.76 } 1.77 } 1.78 + for (ExclusiveSetConstraint constraint : constraints) { 1.79 + for (int value : values) { 1.80 + Cell cell = constraint.findExclusiveCell(value); 1.81 + if (cell != null) { 1.82 + cell.setValue(value); 1.83 + mostConstrained = null; 1.84 + modified.add(cell); 1.85 + //System.out.println(value + " " + numEmpty); 1.86 + } 1.87 + } 1.88 + } 1.89 } 1.90 1.91 if (numEmpty == 0) 1.92 @@ -164,7 +179,7 @@ 1.93 1.94 } finally { 1.95 if (revert) 1.96 - for (SudokuCell m : modified) 1.97 + for (Cell m : modified) 1.98 m.clearValue(); 1.99 } 1.100 } 1.101 @@ -174,15 +189,15 @@ 1.102 } 1.103 1.104 public void removeRedundant(Random random, int depth) { 1.105 - List<SudokuCell> cells = new ArrayList<SudokuCell>(numValues * numValues); 1.106 - for (SudokuCell[] row : grid) 1.107 - for (SudokuCell cell : row) 1.108 + List<Cell> cells = new ArrayList<Cell>(numValues * numValues); 1.109 + for (Cell[] row : grid) 1.110 + for (Cell cell : row) 1.111 cells.add(cell); 1.112 1.113 if (random != null) 1.114 shuffle(cells, random); 1.115 1.116 - for (SudokuCell cell : cells) { 1.117 + for (Cell cell : cells) { 1.118 if (cell.numAvailable() == 0) 1.119 cell.clearValue(); 1.120 } 1.121 @@ -190,7 +205,7 @@ 1.122 1.123 // long lastTime = System.nanoTime(); 1.124 // int remaining = cells.size() - numEmpty; 1.125 - for (SudokuCell cell : cells) { 1.126 + for (Cell cell : cells) { 1.127 if (cell.isEmpty()) 1.128 continue; 1.129 1.130 @@ -263,19 +278,19 @@ 1.131 return s.toString(); 1.132 } 1.133 1.134 - private class SudokuCell { 1.135 + private class Cell { 1.136 private int value; 1.137 - private List<SudokuExclusiveSet> constraints = new ArrayList<SudokuExclusiveSet>(); 1.138 + private List<ExclusiveSetConstraint> constraints = new ArrayList<ExclusiveSetConstraint>(); 1.139 1.140 - public SudokuCell() { 1.141 + public Cell() { 1.142 this.value = 0; 1.143 } 1.144 1.145 - public SudokuCell(int value) { 1.146 + public Cell(int value) { 1.147 this.value = value; 1.148 } 1.149 1.150 - public void addConstraint(SudokuExclusiveSet constraint) { 1.151 + public void addConstraint(ExclusiveSetConstraint constraint) { 1.152 constraints.add(constraint); 1.153 constraint.addCell(this); 1.154 } 1.155 @@ -291,14 +306,14 @@ 1.156 public void setValue(int value) { 1.157 if (this.value != 0) { 1.158 ++SudokuGrid.this.numEmpty; 1.159 - for (SudokuExclusiveSet c : constraints) { 1.160 + for (ExclusiveSetConstraint c : constraints) { 1.161 c.decrementCount(this.value); 1.162 } 1.163 } 1.164 this.value = value; 1.165 if (this.value != 0) { 1.166 --SudokuGrid.this.numEmpty; 1.167 - for (SudokuExclusiveSet c : constraints) { 1.168 + for (ExclusiveSetConstraint c : constraints) { 1.169 c.incrementCount(this.value); 1.170 } 1.171 } 1.172 @@ -314,7 +329,7 @@ 1.173 int count = 0; 1.174 for (int value = 1; value <= SudokuGrid.this.numValues; ++value) { 1.175 boolean available = true; 1.176 - for (SudokuExclusiveSet c : constraints) { 1.177 + for (ExclusiveSetConstraint c : constraints) { 1.178 if (!c.isAvailable(value)) 1.179 { 1.180 available = false; 1.181 @@ -328,7 +343,7 @@ 1.182 } 1.183 1.184 public boolean isAvailable(int value) { 1.185 - for (SudokuExclusiveSet c : constraints) { 1.186 + for (ExclusiveSetConstraint c : constraints) { 1.187 if (!c.isAvailable(value)) 1.188 return false; 1.189 } 1.190 @@ -346,15 +361,16 @@ 1.191 } 1.192 } 1.193 1.194 - private class SudokuExclusiveSet { 1.195 - private List<SudokuCell> cells = new ArrayList<SudokuCell>(); 1.196 + private class ExclusiveSetConstraint { 1.197 + private List<Cell> cells = new ArrayList<Cell>(); 1.198 private int[] valueCount; 1.199 1.200 - public SudokuExclusiveSet() { 1.201 + public ExclusiveSetConstraint() { 1.202 valueCount = new int[SudokuGrid.this.numValues]; 1.203 + SudokuGrid.this.constraints.add(this); 1.204 } 1.205 1.206 - public void addCell(SudokuCell cell) { 1.207 + public void addCell(Cell cell) { 1.208 cells.add(cell); 1.209 } 1.210 1.211 @@ -370,11 +386,27 @@ 1.212 assert(valueCount[value + 1] > 0); 1.213 --valueCount[value - 1]; 1.214 } 1.215 + 1.216 + public Cell findExclusiveCell(int value) { 1.217 + if (valueCount[value - 1] != 0) 1.218 + return null; 1.219 + 1.220 + Cell found = null; 1.221 + for (Cell cell : cells) { 1.222 + if (cell.isEmpty() && cell.isAvailable(value)) { 1.223 + if (found == null) 1.224 + found = cell; 1.225 + else 1.226 + return null; 1.227 + } 1.228 + } 1.229 + return found; 1.230 + } 1.231 } 1.232 1.233 public static void main(String[] args) { 1.234 // long lastTime = System.nanoTime(); 1.235 - SudokuGrid grid = SudokuGrid.randomPuzzle(3, 3); 1.236 + SudokuGrid grid = SudokuGrid.randomPuzzle(4, 4, new Random(1234)); 1.237 System.out.println(grid); 1.238 // System.out.println((System.nanoTime() - lastTime) / 1000000000.0); 1.239 }