Solve Sudoku Puzzle #1

Sudoku puzzles can be rather difficult to solve.

The rules are simple. Each row, each column, and each 3 x 3 block must all have the digits 1 through 9 in them, with no duplicates. For example, look at the underlined blank in the Initial state, center row all the way to the right, just below the 9. It cannot be a 1 2 3 5 or 8 because of the other values in that row. Nor can it be a 2 6 8 or 9 because of the other column values. And 1 4 5 and 9 are already in the same 3 x 3 block. So the only remaining possible value is 7, as you can see in the Final state.

Complexity Analysis:

Initial state:
     9  6  .    .  2  3    .  .  .
     1  .  7    .  8  .    .  .  6
     .  .  .    .  .  6    7  5  2

     .  .  .    .  .  .    4  1  9
     8  .  3    1  .  2    5  .  .
     7  .  1    6  .  4    .  .  .

     .  3  .    .  .  .    6  9  8
     .  1  8    2  4  .    .  .  .
     .  .  .    3  6  .    .  2  .

Puzzle solved!!
Final state:
     9  6  5    7  2  3    8  4  1
     1  2  7    4  8  5    9  3  6
     3  8  4    9  1  6    7  5  2

     2  5  6    8  3  7    4  1  9
     8  4  3    1  9  2    5  6  7
     7  9  1    6  5  4    2  8  3

     4  3  2    5  7  1    6  9  8
     6  1  8    2  4  9    3  7  5
     5  7  9    3  6  8    1  2  4

Elapsed time = 16 ms.

TestSudoku.java - test program

   1: /*
   2:  * Created on Dec 29, 2005
   3:  * Steve O'Hara
   4:  *
   5:  * Create a couple samples and run them
   6:  */
   7: 
   8: public class TestSudoku
   9: {
  10:     private int tried = 0;
  11:     private int solved = 0;
  12: 
  13:     private void tst(int k, String[] config)
  14:     {
  15:         long startTime = System.currentTimeMillis();
  16:         tried++;
  17: 
  18:         if (k < 2 || k > 5)
  19:         {
  20:             throw new RuntimeException("Can only handles sizes 4x4 9x9 16x16 and 25x25");
  21:         }
  22:         int kk = k * k;
  23: 
  24:         // Safety check config strings
  25:         if (config.length != kk)
  26:         {
  27:             throw new RuntimeException("Config array size is incorrect, should be " +
  28:                 kk + " not " + config.length);
  29:         }
  30:         for (int i = 0; i < kk; i++)
  31:         {
  32:             if (config[i].length() != kk)
  33:             {
  34:                 throw new RuntimeException("Config string " + (i+1) + " is wrong length, should be " +
  35:                     kk + " not " + config[i].length());
  36:             }
  37:         }
  38: 
  39:         // Allocate main data structure
  40:         // Fill in each cell with 0=empty or digit 1-9 or A-Z
  41:         // This is why limited to sizes 2x2 to 5x5
  42:         GridSudoku grid = new GridSudoku(k);
  43:         for (int i = 0; i < k; i++)
  44:         {
  45:             for (int j = 0; j < k; j++)
  46:             {
  47:                 for (int m = 0; m < k; m++)
  48:                 {
  49:                     for (int n = 0; n < k; n++)
  50:                     {
  51:                         int val;
  52:                         char ch = config[k*j+n].charAt(k*i+m);
  53:                         if (ch == '.')
  54:                         {
  55:                             val = 0;
  56:                         }
  57:                         else
  58:                         {
  59:                             val = GridSudoku.CODE.indexOf(ch);
  60:                             if (val < 1 || val > kk)
  61:                             {
  62:                                 throw new RuntimeException("Config string " + (k*j+n+1) +
  63:                                     " has invalid digit at char " + (k*i+m+1) +
  64:                                     ": " + ch);
  65:                             }
  66:                         }
  67:                         grid.setCell(i, j, m, n, val);
  68:                     }
  69:                 }
  70:             }
  71:         }
  72: 
  73:         System.out.println("==================================");
  74:         System.out.println("Initial state:");
  75:         grid.prtGrid();
  76:         int startEmpties = grid.countEmpties();
  77: 
  78:         // Now, try to solve it!
  79:         // But let somebody else do that
  80:         SolveSudoku.findUniqueValid(grid);
  81: 
  82:         int empties = grid.countEmpties();
  83:         if (empties == 0)
  84:         {
  85:             System.out.println("Puzzle solved!!");
  86:         }
  87:         else
  88:         {
  89:             System.out.println("Puzzle not solved yet, empty cells = " + empties);
  90:             System.out.println();
  91:             if (SolveSudoku.allowGuessing)
  92:             {
  93:                 if (empties < startEmpties)
  94:                 {
  95:                     System.out.println("Intermediate state:");
  96:                     grid.prtGrid();
  97:                 }
  98:                 SolveSudoku.searchForSolution(grid);
  99:             }
 100:         }
 101: 
 102:         System.out.println();
 103:         System.out.println("Final state:");
 104:         grid.prtGrid();
 105:         if (grid.countEmpties() == 0) solved++;
 106: 
 107:         long elapsedTime = System.currentTimeMillis() - startTime;
 108:         System.out.println("Elapsed time = " + elapsedTime + " ms.");
 109:         System.out.println();
 110:     }
 111: 
 112: 	public static void main(String[] args)
 113:     {
 114:         TestSudoku ts = new TestSudoku();
 115: 
 116:         if (args.length > 0)
 117:         {
 118:             if (args[0].equals("3") && args.length == 10)
 119:             {
 120:                 String[] tst3 = new String[9];
 121:                 for (int i = 0; i < 9; i++)
 122:                 {
 123:                     tst3[i] = args[i+1];
 124:                 }
 125:                 ts.tst(3, tst3);
 126:             }
 127:             else if (args[0].equals("4") && args.length == 17)
 128:             {
 129:                 String[] tst4 = new String[16];
 130:                 for (int i = 0; i < 16; i++)
 131:                 {
 132:                     tst4[i] = args[i+1];
 133:                 }
 134:                 ts.tst(4, tst4);
 135:             }
 136:             else
 137:             {
 138:                 System.out.println("Usage Sudoku 3 96..23... 1.7.8...6 .....6752 ......419 8.31.25.. 7.16.4... .3....698 .1824.... ...36..2.");
 139:                 System.out.println("      or similar for 4x4x4x4");
 140:             }
 141:             System.exit(1);
 142:         }
 143: 
 144:         // Source: Dell magazine, "Math Puzzles and Logic Problems", November 2005, page 21, #1
 145:         String[] t1 = new String[] {
 146:             "96..23...", "1.7.8...6", ".....6752",
 147:             "......419", "8.31.25..", "7.16.4...",
 148:             ".3....698", ".1824....", "...36..2." };
 149:         ts.tst(3, t1);
 150: 
 151:         // Source: Newspaper, Austin American Statesman, Thursday Dec 29, 2005, page E5
 152:         String[] t2 = new String[] {
 153:             "..4...918", "...4.....", "1..2..3..",
 154:             "8.762....", ".31...65.", "....378.2",
 155:             "..3..4..5", ".....2...", "562...1.." };
 156:         ts.tst(3, t2);
 157: 
 158:         // Source: Sudoku Mega, from Mary Anne
 159:         String[] t3 = new String [] {
 160:             "FE9..C..B..A.G.2", "...18.5F3...4C..", ".8C.1.....5.A..6", "..4D..6..1...5F.",
 161:             "5....A.2C.....6G", "C..27.1...6.....", ".G.4.9.6....B.D.", ".FB.E4...7.....C",
 162:             "7.....8...16.29.", ".D.6....E.F.G.C.", ".....D...C.G6..3", "A3.....52.B....E",
 163:             ".C3...E..B..2A..", "E..B.G.....1.64.", "..19...CG2.58...", "G.F.D..A..C..7B9" };
 164:         ts.tst(4, t3);
 165: 
 166:         // Source: Newspaper, The University Star, Wednesday March 8, 2006, page 5
 167:         String[] t4 = new String[] {
 168:             ".3.4...95", "..4.52...", "8.....7..",
 169:             "....1.94.", "2.......7", ".53.6....",
 170:             "..2.....6", "...63.4..", "34...7.8." };
 171:         ts.tst(3, t4);
 172: 
 173:         // Source: www.websudoku.com on 7/12/2006
 174:         String[] t5 = new String[] {
 175:             "4.586....", "36....9..", "..9..3...",
 176:             "...3....4", ".7..1..5.", "6....5...",
 177:             "...6..5..", "..1....92", "....971.3" };
 178:         ts.tst(3, t5);
 179: 
 180:         System.out.println("Solved " + ts.solved + " out of " + ts.tried +
 181:             " puzzle" + (ts.tried == 1 ? "" : "s") + ".");
 182: 	}
 183: }
 184: 

SolveSudoku.java - solving logic

   1: /*
   2:  * Created on Dec 29, 2005
   3:  * Steve O'Hara
   4:  * 
   5:  * All the solution logic goes here
   6:  */
   7: 
   8: public class SolveSudoku
   9: {
  10:     public static final boolean allowGuessing = true;
  11: 
  12:     // Note that these methods are static because they do not store any class variables
  13:     // It is only logic, not data.
  14:     
  15:     // Main entry point
  16:     // This tries all the solvers in order
  17:     // But you can easily call them yourself, in the same order
  18:     public static boolean solve(GridSudoku grid)
  19:     {
  20:         return solve(grid, 0);
  21:     }
  22:     
  23:     private static boolean solve(GridSudoku grid, int depth)
  24:     {
  25:         ////////////////////////////////////////////////////////
  26:         // There are several techniques used here:
  27:         // 1. Search for all cells that can only have a unique value
  28:         // 2. Search by rows, for each digit, to see if there is a unique spot left
  29:         // 3. Bail if the current state has a row or column or block that lacks a possible solution
  30:         // 4. Search. Set a cell and recurse
  31:         // Technique #3 is optional, but speeds things up quite a bit
  32:         ////////////////////////////////////////////////////////
  33: 
  34:         findUniqueValid(grid, depth);       // Technique #1 and #2
  35:         if (!stillSolvable(grid))           // Technique #3
  36:         {
  37:             return false;
  38:         } 
  39:         if (allowGuessing)
  40:         {
  41:             searchForSolution(grid, depth);     // Technique #4
  42:         }
  43:         
  44:         int empties = grid.countEmpties();
  45:         if (empties == 0)
  46:         {
  47:             return true;
  48:         }
  49:         
  50:         // System.out.println("Remaining empties = " + empties);
  51:         return false;
  52:     }
  53:     
  54:     // This is destructive -- it changes the grid
  55:     // Also, it is recursive
  56:     // Return true if we did anything at all
  57:     public static void findUniqueValid(GridSudoku grid)
  58:     {
  59:         findUniqueValid(grid, 0);
  60:     }
  61:     
  62:     private static void findUniqueValid(GridSudoku grid, int depth)
  63:     {
  64:         boolean didAnything;
  65:         int k = grid.getSize();
  66:         int kk = k * k;
  67:         //int iterations = 0;
  68:         
  69:         do
  70:         {
  71:             // Technique #1
  72:             //iterations++;
  73:             didAnything = false;
  74:             for (int j = 0; j < k; j++)
  75:             {
  76:                 for (int n = 0; n < k; n++)
  77:                 {
  78:                     for (int i = 0; i < k; i++)
  79:                     {
  80:                         for (int m = 0; m < k; m++)
  81:                         {
  82:                             int currval = grid.getCell(i, j, m, n);
  83:                             if (currval == 0)   // If already set, go to next cell
  84:                             {
  85:                                 int newval = findUniqueValue(grid, k, i, j, m, n, depth);
  86:                                 if (newval > 0)
  87:                                 {
  88:                                     grid.setCell(i, j, m, n, newval);
  89:                                     didAnything = true;
  90:                                 }
  91:                             }
  92:                         }
  93:                     }
  94:                 }
  95:             }
  96: 
  97:             // Technique #2
  98:             for (int j = 0; j < k; j++)
  99:             {
 100:                 for (int n = 0; n < k; n++)
 101:                 {
 102:                     // Now look to see if there is exactly one possible value here
 103:                     for (int val = 1; val < kk; val++)
 104:                     {
 105:                         int possibles = 0;
 106:                         int savei = 0;
 107:                         int savem = 0;
 108:     
 109:                         for (int i = 0; i < k; i++)
 110:                         {
 111:                             for (int m = 0; m < k; m++)
 112:                             {
 113:                                 int currval = grid.getCell(i, j, m, n);
 114:                                 if (currval == 0)
 115:                                 {
 116:                                     // Found an empty cell
 117:                                     if (isValidValue(grid, k, i, j, m, n, val))
 118:                                     {
 119:                                         // Pretend to set it
 120:                                         grid.setCell(i, j, m, n, val);
 121:                                         if (stillSolvable(grid))
 122:                                         {
 123:                                             possibles++;
 124:                                             savei = i;
 125:                                             savem = m;
 126:                                         }
 127:                                         // Stop pretending
 128:                                         grid.setCell(i, j, m, n, 0);
 129:                                     }
 130:                                 }
 131:                             }
 132:                         }
 133:                         
 134:                         if (possibles == 1)
 135:                         {
 136:                             grid.setCell(savei, j, savem, n, val);
 137:                             didAnything = true;
 138:                         }
 139:                     }
 140:                 }
 141:             }
 142: 
 143:             for (int val = 1; val <= kk; val++)
 144:             {
 145:                 // Technique #3a : check each row for just 1 possible spot for each digit
 146:                 for (int j = 0; j < k; j++)
 147:                 {
 148:                     for (int n = 0; n < k; n++)
 149:                     {
 150:                         boolean done = false;
 151:                         int possibles = 0;
 152:                         int savei = 0;
 153:                         int savem = 0;
 154: 
 155:                         for (int i = 0; i < k && !done; i++)
 156:                         {
 157:                             for (int m = 0; m < k && !done; m++)
 158:                             {
 159:                                 int v = grid.getCell(i, j, m, n);
 160:                                 if (val == v)
 161:                                 {
 162:                                     done = true;    // Found one on this row already
 163:                                 }
 164:                                 if (v == 0)
 165:                                 {
 166:                                     if (isValidValue(grid, k, i, j, m, n, val))
 167:                                     {
 168:                                         possibles++;    // One could go here
 169:                                         savei = i;
 170:                                         savem = m;
 171:                                         if (possibles > 1) done = true;
 172:                                     }
 173:                                 }
 174:                             }
 175:                         }
 176:                         if (possibles == 1)
 177:                         {
 178:                             // Can only go in one spot on this row
 179:                             grid.setCell(savei, j, savem, n, val);
 180:                             didAnything = true;
 181:                         }
 182:                     }
 183:                 }
 184:             
 185:                 // Technique #3a : check each column for just 1 possible spot for each digit
 186:                 for (int i = 0; i < k; i++)
 187:                 {
 188:                     for (int m = 0; m < k; m++)
 189:                     {
 190:                         boolean done = false;
 191:                         int possibles = 0;
 192:                         int savej = 0;
 193:                         int saven = 0;
 194: 
 195:                         for (int j = 0; j < k && !done; j++)
 196:                         {
 197:                             for (int n = 0; n < k && !done; n++)
 198:                             {
 199:                                 int v = grid.getCell(i, j, m, n);
 200:                                 if (val == v)
 201:                                 {
 202:                                     done = true;    // Found one on this column already
 203:                                 }
 204:                                 if (v == 0)
 205:                                 {
 206:                                     if (isValidValue(grid, k, i, j, m, n, val))
 207:                                     {
 208:                                         possibles++;    // One could go here
 209:                                         savej = j;
 210:                                         saven = n;
 211:                                         if (possibles > 1) done = true;
 212:                                     }
 213:                                 }
 214:                             }
 215:                         }
 216:                         if (possibles == 1)
 217:                         {
 218:                             // Can only go in one spot on this column
 219:                             grid.setCell(i, savej, m, saven, val);
 220:                             didAnything = true;
 221:                         }
 222:                     }
 223:                 }
 224:             
 225:                 // Technique #3a : check each 3x3 block for just 1 possible spot for each digit
 226:                 for (int i = 0; i < k; i++)
 227:                 {
 228:                     for (int j = 0; j < k; j++)
 229:                     {
 230:                         boolean done = false;
 231:                         int possibles = 0;
 232:                         int savem = 0;
 233:                         int saven = 0;
 234: 
 235:                         for (int m = 0; m < k && !done; m++)
 236:                         {
 237:                             for (int n = 0; n < k && !done; n++)
 238:                             {
 239:                                 int v = grid.getCell(i, j, m, n);
 240:                                 if (val == v)
 241:                                 {
 242:                                     done = true;    // Found one on this 3x3 block already
 243:                                 }
 244:                                 if (v == 0)
 245:                                 {
 246:                                     if (isValidValue(grid, k, i, j, m, n, val))
 247:                                     {
 248:                                         possibles++;    // One could go here
 249:                                         savem = m;
 250:                                         saven = n;
 251:                                         if (possibles > 1) done = true;
 252:                                     }
 253:                                 }
 254:                             }
 255:                         }
 256:                         if (possibles == 1)
 257:                         {
 258:                             // Can only go in one spot on this 3x3 block
 259:                             grid.setCell(i, j, savem, saven, val);
 260:                             didAnything = true;
 261:                         }
 262:                     }
 263:                 }
 264:             }
 265:             
 266:         }
 267:         while (didAnything);
 268:         
 269:         //System.out.println("Iterations = " + iterations);
 270:     }
 271:     
 272:     // return 0 if no unique value
 273:     private static int findUniqueValue(GridSudoku grid, int k, int i, int j, int m, int n, int depth)
 274:     {
 275:         int kk = k * k;
 276:         int uniqueVal = 0;
 277:         
 278:         for (int val = 1; val <= kk; val++)
 279:         {
 280:             if (isValidValue(grid, k, i, j, m, n, val))
 281:             {
 282:                 if (uniqueVal > 0)
 283:                 {
 284:                     //System.out.println("Cell " + (k*j+n+1) + ", " + (k*i+m+1) +
 285:                     //    " could be either " + GridSudoku.CODE.charAt(val) + " or " +
 286:                     //    GridSudoku.CODE.charAt(uniqueVal));
 287:                     return 0;   // Already found another valid value
 288:                 }
 289:                 uniqueVal = val;
 290:             }
 291:         }
 292:         
 293:         if (uniqueVal > 0)
 294:         {
 295:             for (int indent = 0; indent < depth; indent++)
 296:             {
 297:                 //System.out.print(".  ");
 298:             }
 299:             //System.out.println("Cell " + (k*j+n+1) + ", " + (k*i+m+1) +
 300:             //    " has to be " + GridSudoku.CODE.charAt(uniqueVal));
 301:         }
 302:         return uniqueVal;
 303:     }
 304:     
 305:     public static boolean isValidValue(GridSudoku grid, int k, int i, int j, int m, int n, int val)
 306:     {
 307:         // Check the row first
 308:         for (int ii = 0; ii < k; ii++)
 309:         {
 310:             for (int mm = 0; mm < k; mm++)
 311:             {
 312:                 if (grid.getCell(ii, j, mm, n) == val)
 313:                 {
 314:                     return false;
 315:                 }
 316:             }
 317:         }
 318:         
 319:         // Check the column next
 320:         for (int jj = 0; jj < k; jj++)
 321:         {
 322:             for (int nn = 0; nn < k; nn++)
 323:             {
 324:                 if (grid.getCell(i, jj, m, nn) == val)
 325:                 {
 326:                     return false;
 327:                 }
 328:             }
 329:         }
 330:         
 331:         // Check the small block
 332:         for (int mm = 0; mm < k; mm++)
 333:         {
 334:             for (int nn = 0; nn < k; nn++)
 335:             {
 336:                 if (grid.getCell(i, j, mm, nn) == val)
 337:                 {
 338:                     return false;
 339:                 }
 340:             }
 341:         }
 342:                 
 343:         return true;
 344:     }
 345:     
 346:     // Make sure there still exists a possible solution at this point
 347:     private static boolean stillSolvable(GridSudoku grid)
 348:     {
 349:         int k = grid.getSize();
 350:         int kk = k * k;
 351:         
 352:         for (int val = 1; val <= kk; val++)
 353:         {
 354:             // These 3 blocks could be combined, but it would not really speed anything
 355:             // up and, although briefer, it would be harder to understand
 356:             
 357:             // Check each row
 358:             for (int j = 0; j < k; j++)
 359:             {
 360:                 for (int n = 0; n < k; n++)
 361:                 {
 362:                     boolean done = false;
 363:                     for (int i = 0; i < k && !done; i++)
 364:                     {
 365:                         for (int m = 0; m < k && !done; m++)
 366:                         {
 367:                             int v = grid.getCell(i, j, m, n);
 368:                             if (val == v)
 369:                             {
 370:                                 done = true;    // Found one on this row already
 371:                             }
 372:                             if (v == 0)
 373:                             {
 374:                                 if (isValidValue(grid, k, i, j, m, n, val))
 375:                                 {
 376:                                     done = true;    // One could go here
 377:                                 }
 378:                             }
 379:                         }
 380:                     }
 381:                     if (!done)
 382:                     {
 383:                         return false;   // Could find a space on the whole row
 384:                     }
 385:                 }
 386:             }
 387:             
 388:             // Check each column
 389:             for (int i = 0; i < k; i++)
 390:             {
 391:                 for (int m = 0; m < k; m++)
 392:                 {
 393:                     boolean done = false;
 394:                     for (int j = 0; j < k && !done; j++)
 395:                     {
 396:                         for (int n = 0; n < k && !done; n++)
 397:                         {
 398:                             int v = grid.getCell(i, j, m, n);
 399:                             if (val == v)
 400:                             {
 401:                                 done = true;    // Found one on this column already
 402:                             }
 403:                             if (v == 0)
 404:                             {
 405:                                 if (isValidValue(grid, k, i, j, m, n, val))
 406:                                 {
 407:                                     done = true;    // One could go here
 408:                                 }
 409:                             }
 410:                         }
 411:                     }
 412:                     if (!done)
 413:                     {
 414:                         return false;   // Could find a space on the whole column
 415:                     }
 416:                 }
 417:             }
 418:             
 419:             // Check each 3x3 block
 420:             for (int i = 0; i < k; i++)
 421:             {
 422:                 for (int j = 0; j < k; j++)
 423:                 {
 424:                     boolean done = false;
 425:                     for (int m = 0; m < k && !done; m++)
 426:                     {
 427:                         for (int n = 0; n < k && !done; n++)
 428:                         {
 429:                             int v = grid.getCell(i, j, m, n);
 430:                             if (val == v)
 431:                             {
 432:                                 done = true;    // Found one on this 3x3 block already
 433:                             }
 434:                             if (v == 0)
 435:                             {
 436:                                 if (isValidValue(grid, k, i, j, m, n, val))
 437:                                 {
 438:                                     done = true;    // One could go here
 439:                                 }
 440:                             }
 441:                         }
 442:                     }
 443:                     if (!done)
 444:                     {
 445:                         return false;   // Could find a space on the whole 3x3 block
 446:                     }
 447:                 }
 448:             }
 449:         }
 450:         
 451:         return true;
 452:     }
 453:     
 454:     // Blindly search for solutions
 455:     public static void searchForSolution(GridSudoku grid)
 456:     {
 457:         searchForSolution(grid, 0);
 458:     }
 459:     
 460:     private static void searchForSolution(GridSudoku grid, int depth)
 461:     {
 462:         int k = grid.getSize();
 463:         int kk = k * k;
 464:         GridSudoku tempGrid = new GridSudoku(k);
 465: 
 466:         // Find a random cell that is empty and set it to a random valid value, and recurse!
 467:         // Could be improved by searching for cells with fewer possible values, I think
 468:         for (int j = 0; j < k; j++)
 469:         {
 470:             for (int n = 0; n < k; n++)
 471:             {
 472:                 for (int i = 0; i < k; i++)
 473:                 {
 474:                     for (int m = 0; m < k; m++)
 475:                     {
 476:                         // Stop when we find the first empty cell
 477:                         int val = grid.getCell(i, j, m, n);
 478:                         if (val == 0)
 479:                         {
 480:                             for (val = 1; val <= kk; val++)
 481:                             {
 482:                                 if (isValidValue(grid, k, i, j, m, n, val))
 483:                                 {
 484:                                     if (depth <= 5)
 485:                                     {
 486:                                         for (int indent = 0; indent < depth; indent++)
 487:                                         {
 488:                                             System.out.print(".  ");
 489:                                         }
 490:                                         System.out.println("Trying to set cell " + (k*j+n+1) + ", " +                                        
 491:                                             (k*i+m+1) + " to " + GridSudoku.CODE.charAt(val));
 492:                                     }
 493:                                         
 494:                                     // Create a temporary copy
 495:                                     tempGrid.copyCells(grid);
 496:                                     grid.setCell(i, j, m, n, val);
 497:                                     
 498:                                     // Recurse
 499:                                     if (solve(grid, depth+1))
 500:                                     {
 501:                                         return;
 502:                                     }                                                                        
 503:                                     
 504:                                     // Must not have worked, try next value
 505:                                     // Restore grid values and continue to next attempt
 506:                                     grid.copyCells(tempGrid);
 507:                                 }
 508:                             }
 509:                             
 510:                             // No point continuing, ran out of possible values for this cell
 511:                             // Must be an invalid configuration at this point
 512:                             return;
 513:                         }
 514:                     }
 515:                 }
 516:             }
 517:         }
 518:     }
 519: }
 520: 

GridSudoku.java - grid representation

   1: /*
   2:  * Created on Dec 29, 2005
   3:  * Steve O'Hara
   4:  * 
   5:  * This is the data structure for the grid itself
   6:  */
   7: 
   8: import java.io.PrintStream;
   9: 
  10: public class GridSudoku
  11: {
  12:     private int k;       // 3 for a typical 9x9 grid
  13:     private short[][][][] grid;
  14:     public static final String CODE = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  15: 
  16:     // Constructor, size is fixed
  17:     public GridSudoku(int n)
  18:     {
  19:         k = n;
  20:         grid = new short[k][k][k][k];
  21:     }
  22:     
  23:     public int getSize()
  24:     {
  25:         return k;
  26:     }
  27:     
  28:     // Set a cell value
  29:     public void setCell(int i, int j, int m, int n, int val)
  30:     {
  31:         grid[i][j][m][n] = (short) val;
  32:     }
  33:     
  34:     // Access value in a cell
  35:     public int getCell(int i, int j, int m, int n)
  36:     {
  37:         return (int) grid[i][j][m][n];
  38:     }
  39:     
  40:     public int countEmpties()
  41:     {
  42:         int empties = 0;
  43:         for (int j = 0; j < k; j++)
  44:         {
  45:             for (int n = 0; n < k; n++)
  46:             {
  47:                 for (int i = 0; i < k; i++)
  48:                 {
  49:                     for (int m = 0; m < k; m++)
  50:                     {
  51:                         if (grid[i][j][m][n] == 0)
  52:                         {
  53:                             empties++;
  54:                         }
  55:                     }
  56:                 }
  57:             }
  58:         }
  59:         return empties;
  60:     }
  61: 
  62:     public void copyCells(GridSudoku other)
  63:     {
  64:         if (other.getSize() != k)
  65:         {
  66:             throw new RuntimeException("Grids are of different sizes: " + k + " and " + other.getSize());
  67:         }
  68:         
  69:         for (int j = 0; j < k; j++)
  70:         {
  71:             for (int n = 0; n < k; n++)
  72:             {
  73:                 for (int i = 0; i < k; i++)
  74:                 {
  75:                     for (int m = 0; m < k; m++)
  76:                     {
  77:                         grid[i][j][m][n] = other.grid[i][j][m][n];
  78:                     }
  79:                 }
  80:             }
  81:         }
  82:     }
  83:     
  84:     // Simple default print of the grid
  85:     public void prtGrid()
  86:     {
  87:         prtGrid(System.out);
  88:     }
  89:     
  90:     // In case you want to print to a file instead of stdout
  91:     public void prtGrid(PrintStream out)
  92:     {
  93:         for (int j = 0; j < k; j++)
  94:         {
  95:             for (int n = 0; n < k; n++)
  96:             {
  97:                 out.print("    ");  // indent each line a bit
  98:                 for (int i = 0; i < k; i++)
  99:                 {
 100:                     if (i > 0)
 101:                     {
 102:                         out.print("  ");
 103:                     }
 104:                     for (int m = 0; m < k; m++)
 105:                     {
 106:                         int val = grid[i][j][m][n];
 107:                         if (val == 0)
 108:                         {
 109:                             out.print(" . ");
 110:                         }
 111:                         else
 112:                         {
 113:                             out.print(" " + CODE.charAt(val) + " ");
 114:                         }
 115:                     }
 116:                 }
 117:                 out.println();
 118:             }
 119:             out.println();
 120:         }
 121:     }
 122: }
 123: 

RunSudoku.out - sample output

   1: ==================================
   2: Initial state:
   3:      9  6  .    .  2  3    .  .  . 
   4:      1  .  7    .  8  .    .  .  6 
   5:      .  .  .    .  .  6    7  5  2 
   6: 
   7:      .  .  .    .  .  .    4  1  9 
   8:      8  .  3    1  .  2    5  .  . 
   9:      7  .  1    6  .  4    .  .  . 
  10: 
  11:      .  3  .    .  .  .    6  9  8 
  12:      .  1  8    2  4  .    .  .  . 
  13:      .  .  .    3  6  .    .  2  . 
  14: 
  15: Puzzle solved!!
  16: 
  17: Final state:
  18:      9  6  5    7  2  3    8  4  1 
  19:      1  2  7    4  8  5    9  3  6 
  20:      3  8  4    9  1  6    7  5  2 
  21: 
  22:      2  5  6    8  3  7    4  1  9 
  23:      8  4  3    1  9  2    5  6  7 
  24:      7  9  1    6  5  4    2  8  3 
  25: 
  26:      4  3  2    5  7  1    6  9  8 
  27:      6  1  8    2  4  9    3  7  5 
  28:      5  7  9    3  6  8    1  2  4 
  29: 
  30: Elapsed time = 16 ms.
  31: 
  32: ==================================
  33: Initial state:
  34:      .  .  4    .  .  .    9  1  8 
  35:      .  .  .    4  .  .    .  .  . 
  36:      1  .  .    2  .  .    3  .  . 
  37: 
  38:      8  .  7    6  2  .    .  .  . 
  39:      .  3  1    .  .  .    6  5  . 
  40:      .  .  .    .  3  7    8  .  2 
  41: 
  42:      .  .  3    .  .  4    .  .  5 
  43:      .  .  .    .  .  2    .  .  . 
  44:      5  6  2    .  .  .    1  .  . 
  45: 
  46: Puzzle not solved yet, empty cells = 32
  47: 
  48: Intermediate state:
  49:      .  2  4    .  .  .    9  1  8 
  50:      3  .  .    4  .  1    5  2  6 
  51:      1  .  .    2  .  .    3  7  4 
  52: 
  53:      8  9  7    6  2  5    4  3  1 
  54:      2  3  1    .  4  .    6  5  7 
  55:      .  .  .    1  3  7    8  9  2 
  56: 
  57:      .  .  3    .  .  4    2  .  5 
  58:      .  .  .    .  .  2    7  .  . 
  59:      5  6  2    .  .  .    1  4  . 
  60: 
  61: Trying to set cell 1, 1 to 6
  62: 
  63: Final state:
  64:      6  2  4    7  5  3    9  1  8 
  65:      3  7  9    4  8  1    5  2  6 
  66:      1  8  5    2  9  6    3  7  4 
  67: 
  68:      8  9  7    6  2  5    4  3  1 
  69:      2  3  1    8  4  9    6  5  7 
  70:      4  5  6    1  3  7    8  9  2 
  71: 
  72:      7  1  3    9  6  4    2  8  5 
  73:      9  4  8    5  1  2    7  6  3 
  74:      5  6  2    3  7  8    1  4  9 
  75: 
  76: Elapsed time = 62 ms.
  77: 
  78: ==================================
  79: Initial state:
  80:      F  E  9  .    .  C  .  .    B  .  .  A    .  G  .  2 
  81:      .  .  .  1    8  .  5  F    3  .  .  .    4  C  .  . 
  82:      .  8  C  .    1  .  .  .    .  .  5  .    A  .  .  6 
  83:      .  .  4  D    .  .  6  .    .  1  .  .    .  5  F  . 
  84: 
  85:      5  .  .  .    .  A  .  2    C  .  .  .    .  .  6  G 
  86:      C  .  .  2    7  .  1  .    .  .  6  .    .  .  .  . 
  87:      .  G  .  4    .  9  .  6    .  .  .  .    B  .  D  . 
  88:      .  F  B  .    E  4  .  .    .  7  .  .    .  .  .  C 
  89: 
  90:      7  .  .  .    .  .  8  .    .  .  1  6    .  2  9  . 
  91:      .  D  .  6    .  .  .  .    E  .  F  .    G  .  C  . 
  92:      .  .  .  .    .  D  .  .    .  C  .  G    6  .  .  3 
  93:      A  3  .  .    .  .  .  5    2  .  B  .    .  .  .  E 
  94: 
  95:      .  C  3  .    .  .  E  .    .  B  .  .    2  A  .  . 
  96:      E  .  .  B    .  G  .  .    .  .  .  1    .  6  4  . 
  97:      .  .  1  9    .  .  .  C    G  2  .  5    8  .  .  . 
  98:      G  .  F  .    D  .  .  A    .  .  C  .    .  7  B  9 
  99: 
 100: Puzzle not solved yet, empty cells = 122
 101: 
 102: Intermediate state:
 103:      F  E  9  5    .  C  .  .    B  6  .  A    1  G  8  2 
 104:      .  A  6  1    8  .  5  F    3  .  G  .    4  C  .  . 
 105:      .  8  C  G    1  .  .  .    .  .  5  .    A  .  .  6 
 106:      3  7  4  D    A  .  6  G    8  1  .  C    9  5  F  B 
 107: 
 108:      5  1  .  3    .  A  .  2    C  .  .  .    .  .  6  G 
 109:      C  9  .  2    7  .  1  .    .  G  6  .    .  .  .  . 
 110:      8  G  .  4    .  9  .  6    .  .  .  .    B  .  D  . 
 111:      6  F  B  A    E  4  G  .    .  7  .  .    .  .  2  C 
 112: 
 113:      7  .  .  .    .  .  8  .    .  .  1  6    .  2  9  . 
 114:      .  D  .  6    .  .  .  .    E  .  F  .    G  .  C  . 
 115:      .  .  .  .    .  D  .  .    .  C  .  G    6  .  .  3 
 116:      A  3  .  .    .  .  .  5    2  .  B  .    .  .  1  E 
 117: 
 118:      .  C  3  7    .  .  E  .    .  B  .  .    2  A  G  1 
 119:      E  .  A  B    .  G  .  .    .  .  .  1    C  6  4  . 
 120:      .  .  1  9    .  .  .  C    G  2  A  5    8  .  .  . 
 121:      G  .  F  8    D  1  .  A    .  .  C  .    .  7  B  9 
 122: 
 123: Trying to set cell 1, 5 to 3
 124: .  Trying to set cell 1, 7 to 4
 125: .  .  Trying to set cell 1, 8 to 7
 126: .  .  Trying to set cell 1, 8 to D
 127: .  .  .  Trying to set cell 2, 1 to 2
 128: .  .  .  .  Trying to set cell 2, 10 to 9
 129: .  .  .  .  .  Trying to set cell 2, 12 to D
 130: .  .  .  .  .  Trying to set cell 2, 12 to E
 131: .  .  .  .  Trying to set cell 2, 10 to D
 132: .  .  .  .  Trying to set cell 2, 10 to E
 133: .  .  .  Trying to set cell 2, 1 to B
 134: .  .  .  .  Trying to set cell 2, 6 to 2
 135: .  .  .  .  .  Trying to set cell 2, 10 to 9
 136: .  .  .  .  .  Trying to set cell 2, 10 to D
 137: .  .  .  .  .  Trying to set cell 2, 10 to E
 138: .  .  .  .  Trying to set cell 2, 6 to 7
 139: .  .  .  .  Trying to set cell 2, 6 to E
 140: .  Trying to set cell 1, 7 to 7
 141: .  .  Trying to set cell 1, 8 to 4
 142: .  .  Trying to set cell 1, 8 to D
 143: .  .  .  Trying to set cell 2, 1 to 2
 144: .  .  .  .  Trying to set cell 2, 10 to 9
 145: .  .  .  .  .  Trying to set cell 2, 12 to 7
 146: .  .  .  .  .  Trying to set cell 2, 12 to D
 147: .  .  .  .  .  Trying to set cell 2, 12 to E
 148: .  .  .  .  Trying to set cell 2, 10 to D
 149: .  .  .  .  Trying to set cell 2, 10 to E
 150: .  .  .  Trying to set cell 2, 1 to B
 151: .  .  .  .  Trying to set cell 2, 6 to 2
 152: .  .  .  .  .  Trying to set cell 2, 10 to 9
 153: .  .  .  .  .  Trying to set cell 2, 10 to D
 154: .  .  .  .  .  Trying to set cell 2, 10 to E
 155: .  .  .  .  Trying to set cell 2, 6 to E
 156: 
 157: Final state:
 158:      F  E  9  5    3  C  7  D    B  6  4  A    1  G  8  2 
 159:      B  A  6  1    8  E  5  F    3  9  G  2    4  C  7  D 
 160:      2  8  C  G    1  B  4  9    D  F  5  7    A  E  3  6 
 161:      3  7  4  D    A  2  6  G    8  1  E  C    9  5  F  B 
 162: 
 163:      5  1  7  3    F  A  D  2    C  4  9  B    E  8  6  G 
 164:      C  9  D  2    7  8  1  B    5  G  6  E    F  3  A  4 
 165:      8  G  E  4    5  9  C  6    F  A  2  3    B  1  D  7 
 166:      6  F  B  A    E  4  G  3    1  7  D  8    5  9  2  C 
 167: 
 168:      7  B  5  C    G  F  8  E    4  3  1  6    D  2  9  A 
 169:      1  D  2  6    4  3  A  7    E  5  F  9    G  B  C  8 
 170:      9  4  8  E    2  D  B  1    A  C  7  G    6  F  5  3 
 171:      A  3  G  F    C  6  9  5    2  8  B  D    7  4  1  E 
 172: 
 173:      D  C  3  7    6  5  E  4    9  B  8  F    2  A  G  1 
 174:      E  2  A  B    9  G  F  8    7  D  3  1    C  6  4  5 
 175:      4  6  1  9    B  7  3  C    G  2  A  5    8  D  E  F 
 176:      G  5  F  8    D  1  2  A    6  E  C  4    3  7  B  9 
 177: 
 178: Elapsed time = 21438 ms.
 179: 
 180: ==================================
 181: Initial state:
 182:      .  3  .    4  .  .    .  9  5 
 183:      .  .  4    .  5  2    .  .  . 
 184:      8  .  .    .  .  .    7  .  . 
 185: 
 186:      .  .  .    .  1  .    9  4  . 
 187:      2  .  .    .  .  .    .  .  7 
 188:      .  5  3    .  6  .    .  .  . 
 189: 
 190:      .  .  2    .  .  .    .  .  6 
 191:      .  .  .    6  3  .    4  .  . 
 192:      3  4  .    .  .  7    .  8  . 
 193: 
 194: Puzzle solved!!
 195: 
 196: Final state:
 197:      6  3  1    4  7  8    2  9  5 
 198:      9  7  4    3  5  2    1  6  8 
 199:      8  2  5    1  9  6    7  3  4 
 200: 
 201:      7  6  8    2  1  5    9  4  3 
 202:      2  1  9    8  4  3    6  5  7 
 203:      4  5  3    7  6  9    8  1  2 
 204: 
 205:      1  9  2    5  8  4    3  7  6 
 206:      5  8  7    6  3  1    4  2  9 
 207:      3  4  6    9  2  7    5  8  1 
 208: 
 209: Elapsed time = 31 ms.
 210: 
 211: ==================================
 212: Initial state:
 213:      4  .  5    8  6  .    .  .  . 
 214:      3  6  .    .  .  .    9  .  . 
 215:      .  .  9    .  .  3    .  .  . 
 216: 
 217:      .  .  .    3  .  .    .  .  4 
 218:      .  7  .    .  1  .    .  5  . 
 219:      6  .  .    .  .  5    .  .  . 
 220: 
 221:      .  .  .    6  .  .    5  .  . 
 222:      .  .  1    .  .  .    .  9  2 
 223:      .  .  .    .  9  7    1  .  3 
 224: 
 225: Puzzle not solved yet, empty cells = 49
 226: 
 227: Intermediate state:
 228:      4  .  5    8  6  9    .  .  . 
 229:      3  6  7    .  .  .    9  .  . 
 230:      .  .  9    .  .  3    4  .  . 
 231: 
 232:      .  .  .    3  .  .    .  .  4 
 233:      .  7  .    .  1  .    .  5  . 
 234:      6  .  .    .  .  5    .  .  . 
 235: 
 236:      .  .  .    6  .  1    5  .  . 
 237:      7  .  1    .  .  .    6  9  2 
 238:      .  .  6    .  9  7    1  .  3 
 239: 
 240: Trying to set cell 1, 2 to 1
 241: Trying to set cell 1, 2 to 2
 242: .  Trying to set cell 1, 7 to 3
 243: .  .  Trying to set cell 1, 8 to 1
 244: .  .  Trying to set cell 1, 8 to 7
 245: .  Trying to set cell 1, 7 to 7
 246: .  .  Trying to set cell 2, 5 to 2
 247: .  .  Trying to set cell 2, 5 to 4
 248: .  .  Trying to set cell 2, 5 to 5
 249: 
 250: Final state:
 251:      4  2  5    8  6  9    7  3  1 
 252:      3  6  7    1  5  4    9  2  8 
 253:      1  8  9    7  2  3    4  6  5 
 254: 
 255:      9  5  2    3  7  6    8  1  4 
 256:      8  7  4    9  1  2    3  5  6 
 257:      6  1  3    4  8  5    2  7  9 
 258: 
 259:      2  9  8    6  3  1    5  4  7 
 260:      7  3  1    5  4  8    6  9  2 
 261:      5  4  6    2  9  7    1  8  3 
 262: 
 263: Elapsed time = 297 ms.
 264: 
 265: Solved 5 out of 5 puzzles.
 266: 
Email: steve@oharasteve.com