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      }