src/classes/net/jankenpoi/sudokuki/solver/BruteForceGridSolver.java

   1 package net.jankenpoi.sudokuki.solver;\r
   2 \r
   3 import net.jankenpoi.sudokuki.model.GridModel;\r
   4 \r
   5 public class BruteForceGridSolver implements GridSolver {\r
   6 \r
   7         private static final int MAX_ITER_NB = 20000;\r
   8         /*\r
   9          * Maybe spurious field - is it useful ??\r
  10          */\r
  11         private final GridModel originalGrid;\r
  12         /**\r
  13          * Equivalent of 81 grids\r
  14          */\r
  15         private final int[] cellShadowMemory = new int[81 * GRID_LENGTH];\r
  16 \r
  17         private int currentIndex = 0;\r
  18 \r
  19         private Boolean cancelled = Boolean.FALSE;\r
  20 \r
  21         public BruteForceGridSolver(GridModel originalGrid) {\r
  22                 this.originalGrid = originalGrid;\r
  23 \r
  24                 int[] originalFlags = originalGrid.cloneCellInfosAsInts();\r
  25                 System.arraycopy(originalFlags, 0, cellShadowMemory, 0,\r
  26                                 originalFlags.length);\r
  27         }\r
  28 \r
  29         private boolean cancelRequested() {\r
  30                 synchronized (cancelled) {\r
  31                         return cancelled.booleanValue();\r
  32                 }\r
  33         }\r
  34         \r
  35         public void cancel() {\r
  36                 synchronized (cancelled) {\r
  37                         cancelled = Boolean.TRUE;\r
  38                 }\r
  39         }\r
  40         \r
  41         @Override\r
  42         public GridSolution resolve() {\r
  43 \r
  44                 GridShadow gs = new GridShadow(cellShadowMemory, currentIndex, true); // 2.1\r
  45                 gs.debugDump();\r
  46                 boolean totalDeadEndNoSolution = false;\r
  47                 \r
  48                 for (int iter = 1; totalDeadEndNoSolution == false && iter < MAX_ITER_NB; iter++) {\r
  49                         if (cancelRequested()) {\r
  50                                 return null;\r
  51                         }\r
  52 \r
  53                         int[] liCo = gs.popFirstCellWithMinPossValues(); // 3, 4\r
  54                         int li = liCo[0];\r
  55                         int co = liCo[1];\r
  56 \r
  57                         if (li == 10 && co == 10) {\r
  58                                 /**\r
  59                                  * TABLE COMPLETE\r
  60                                  * \r
  61                                  * Return the solution\r
  62                                  */\r
  63                                 short[] shorts = new short[GRID_LENGTH];\r
  64                                 for (int i=0; i<GRID_LENGTH; i++) {\r
  65                                         shorts[i] = (short) cellShadowMemory[currentIndex + i];\r
  66                                 }\r
  67                                 GridModel solModel = new GridModel(shorts,\r
  68                                                 0);\r
  69                                 GridSolution solution = new GridSolution(true, solModel);\r
  70                                 return solution;\r
  71                         }\r
  72 \r
  73                         if (li == 11 && co == 11) {\r
  74                                 /**\r
  75                                  * DEAD END\r
  76                                  * \r
  77                                  * Go back one position and continue the solving process\r
  78                                  */\r
  79                                 totalDeadEndNoSolution = backToPreviousPosition();\r
  80                                 if (totalDeadEndNoSolution) {\r
  81                                         break;\r
  82                                 }\r
  83                                 gs = new GridShadow(cellShadowMemory, currentIndex, false);\r
  84                                 gs.debugDump();\r
  85                                 continue;\r
  86                         }\r
  87 \r
  88                         byte value = gs.popFirstValueForCell(li, co); // 5\r
  89 \r
  90                         copyCurrentFlagsToNextPosition(); // 6\r
  91 \r
  92                         gs = new GridShadow(cellShadowMemory, currentIndex, false); // 7\r
  93                         gs.debugDump();\r
  94                         \r
  95                         gs.setCellValueScreened(li, co, value); // 7\r
  96 \r
  97                         forwardToNextPosition(); // 8\r
  98                         gs = new GridShadow(cellShadowMemory, currentIndex, false); // 8\r
  99                         gs.debugDump();\r
 100 \r
 101                         boolean deadEnd = gs.setCellValueAt(li, co, value); // 8.1\r
 102                         if (deadEnd) {\r
 103                                 totalDeadEndNoSolution = backToPreviousPosition(); // 9\r
 104                                 gs = new GridShadow(cellShadowMemory, currentIndex, false); // 9.1\r
 105                                 gs.debugDump();\r
 106                         }\r
 107 \r
 108                 }\r
 109 \r
 110                 GridSolution solution = new GridSolution(false, originalGrid);\r
 111                 return solution;\r
 112         }\r
 113 \r
 114         void copyCurrentFlagsToNextPosition() {\r
 115                 if (currentIndex + GRID_LENGTH >= cellShadowMemory.length) {\r
 116                         throw new IllegalStateException(\r
 117                                         "Already reached the end of the solver memory");\r
 118                 }\r
 119                 System.arraycopy(cellShadowMemory, currentIndex, cellShadowMemory,\r
 120                                 currentIndex + GRID_LENGTH, GRID_LENGTH);\r
 121         }\r
 122 \r
 123         void forwardToNextPosition() {\r
 124                 currentIndex = currentIndex + GRID_LENGTH;\r
 125         }\r
 126 \r
 127         boolean backToPreviousPosition() {\r
 128                 currentIndex = currentIndex - GRID_LENGTH;\r
 129                 if (currentIndex < 0) {\r
 130                         return true;\r
 131                 }\r
 132                 return false;\r
 133         }\r
 134 \r
 135         /*\r
 136          * FOR TESTING ONLY\r
 137          */\r
 138         int[] getCellShadowMemory() {\r
 139                 return cellShadowMemory;\r
 140         }\r
 141 \r
 142         /*\r
 143          * FOR TESTING ONLY\r
 144          */\r
 145         int getCurrentIndex() {\r
 146                 return currentIndex;\r
 147         }\r
 148 \r
 149 }\r