Thu, 31 Jan 2013 18:44:44 +0100
added solving algorithm
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/easy-sudoku Thu Jan 31 18:44:44 2013 +0100 1.3 @@ -0,0 +1,9 @@ 1.4 +3 _ _ 2 4 _ _ 6 _ 1.5 +_ 4 _ _ _ _ _ 5 3 1.6 +1 8 9 6 3 5 4 _ _ 1.7 +_ _ _ _ 8 _ 2 _ _ 1.8 +_ _ 7 4 9 6 8 _ 1 1.9 +8 9 3 1 5 _ 6 _ 4 1.10 +_ _ 1 9 2 _ 5 _ _ 1.11 +2 _ _ 3 _ _ 7 4 _ 1.12 +9 6 _ 5 _ _ 3 _ 2
2.1 --- a/src/de/uapcore/sudoku/ActionHandler.java Sun Jan 27 15:03:57 2013 +0100 2.2 +++ b/src/de/uapcore/sudoku/ActionHandler.java Thu Jan 31 18:44:44 2013 +0100 2.3 @@ -134,7 +134,10 @@ 2.4 } 2.5 2.6 private void solve() { 2.7 - // TODO: solve 2.8 + if (!solver.check(field) || !solver.solve(field)) { 2.9 + JOptionPane.showMessageDialog(field, "Das Feld ist nicht lösbar!", 2.10 + "Sudoku", JOptionPane.WARNING_MESSAGE); 2.11 + } 2.12 } 2.13 2.14 private boolean saveUnsaved() { 2.15 @@ -162,6 +165,7 @@ 2.16 switch (e.getActionCommand()) { 2.17 case NEW: 2.18 if (saveUnsaved()) { 2.19 + doc.clearFilename(); 2.20 field.clear(); 2.21 } 2.22 break;
3.1 --- a/src/de/uapcore/sudoku/DocumentHandler.java Sun Jan 27 15:03:57 2013 +0100 3.2 +++ b/src/de/uapcore/sudoku/DocumentHandler.java Thu Jan 31 18:44:44 2013 +0100 3.3 @@ -76,6 +76,7 @@ 3.4 throw new IOException("Kein Sudoku-Feld enthalten!"); 3.5 } 3.6 } 3.7 + field.setAllCellsModified(false); 3.8 } 3.9 3.10 public void save(Field field) throws IOException {
4.1 --- a/src/de/uapcore/sudoku/Field.java Sun Jan 27 15:03:57 2013 +0100 4.2 +++ b/src/de/uapcore/sudoku/Field.java Thu Jan 31 18:44:44 2013 +0100 4.3 @@ -92,6 +92,10 @@ 4.4 super.paintChildren(graphics); 4.5 } 4.6 4.7 + public boolean isCellEmpty(int x, int y) { 4.8 + return getCellValue(x, y) == 0; 4.9 + } 4.10 + 4.11 public int getCellValue(int x, int y) { 4.12 return cells[x][y].getValue(); 4.13 } 4.14 @@ -100,6 +104,14 @@ 4.15 cells[x][y].setValue(v); 4.16 } 4.17 4.18 + public void clearCellValue(int x, int y) { 4.19 + setCellValue(x, y, 0); 4.20 + } 4.21 + 4.22 + public void setCellModified(int x, int y, boolean modified) { 4.23 + cells[x][y].setModified(modified); 4.24 + } 4.25 + 4.26 public void setAllCellsModified(boolean modified) { 4.27 for (int x = 0 ; x < 9 ; x++) { 4.28 for (int y = 0 ; y < 9 ; y++) {
5.1 --- a/src/de/uapcore/sudoku/Solver.java Sun Jan 27 15:03:57 2013 +0100 5.2 +++ b/src/de/uapcore/sudoku/Solver.java Thu Jan 31 18:44:44 2013 +0100 5.3 @@ -26,6 +26,9 @@ 5.4 5.5 package de.uapcore.sudoku; 5.6 5.7 +import java.util.ArrayList; 5.8 +import java.util.List; 5.9 + 5.10 /** 5.11 * 5.12 * @author mike 5.13 @@ -35,6 +38,144 @@ 5.14 public Solver() { 5.15 } 5.16 5.17 + private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) { 5.18 + Integer c = candidates[x][y].remove(0); 5.19 + f.setCellValue(x, y, c); 5.20 + f.setCellModified(x, y, true); 5.21 + for (int i = 0 ; i < 9 ; i++) { 5.22 + candidates[x][i].remove(c); 5.23 + candidates[i][y].remove(c); 5.24 + } 5.25 + for (int i = 0 ; i < 3 ; i++) { 5.26 + for (int j = 0 ; j < 3 ; j++) { 5.27 + candidates[x-x%3+i][y-y%3+j].remove(c); 5.28 + } 5.29 + } 5.30 + return c; 5.31 + } 5.32 + 5.33 + private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { 5.34 + for (int x = 0 ; x < 9 ; x++) { 5.35 + for (int y = 0 ; y < 9 ; y++) { 5.36 + candidatesBackup[x][y] = new ArrayList<>(9); 5.37 + candidatesBackup[x][y].addAll(candidates[x][y]); 5.38 + } 5.39 + } 5.40 + } 5.41 + 5.42 + private void makeBackup(Field f, int[][] fieldBackup) { 5.43 + for (int x = 0 ; x < 9 ; x++) { 5.44 + for (int y = 0 ; y < 9 ; y++) { 5.45 + fieldBackup[x][y] = f.getCellValue(x, y); 5.46 + } 5.47 + } 5.48 + } 5.49 + 5.50 + private void restoreBackup(Field f, int[][] fieldBackup) { 5.51 + for (int x = 0 ; x < 9 ; x++) { 5.52 + for (int y = 0 ; y < 9 ; y++) { 5.53 + f.setCellValue(x, y, fieldBackup[x][y]); 5.54 + } 5.55 + } 5.56 + } 5.57 + 5.58 + private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) { 5.59 + for (int x = 0 ; x < 9 ; x++) { 5.60 + for (int y = 0 ; y < 9 ; y++) { 5.61 + candidates[x][y].clear(); 5.62 + candidates[x][y].addAll(candidatesBackup[x][y]); 5.63 + } 5.64 + } 5.65 + } 5.66 + 5.67 + private boolean solve(Field f, List<Integer>[][] candidates) { 5.68 + 5.69 + // Make backup 5.70 + List<Integer>[][] candidatesBackup = new List[9][9]; 5.71 + int[][] fieldBackup = new int[9][9]; 5.72 + makeBackup(candidates, candidatesBackup); 5.73 + makeBackup(f, fieldBackup); 5.74 + 5.75 + // Fill in distinct solutions 5.76 + boolean fillDistinct; 5.77 + do { 5.78 + fillDistinct = false; 5.79 + for (int x = 0 ; x < 9 ; x++) { 5.80 + for (int y = 0 ; y < 9 ; y++) { 5.81 + if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) { 5.82 + fillInCandidate(f, candidates, x, y); 5.83 + fillDistinct = true; 5.84 + } 5.85 + } 5.86 + } 5.87 + } while (fillDistinct); 5.88 + 5.89 + // Try out remaining candidates 5.90 + for (int x = 0 ; x < 9 ; x++) { 5.91 + for (int y = 0 ; y < 9 ; y++) { 5.92 + if (f.isCellEmpty(x, y)) { 5.93 + while (candidates[x][y].size() > 0) { 5.94 + List<Integer>[][] cb = new List[9][9]; 5.95 + makeBackup(candidates, cb); 5.96 + Integer c = fillInCandidate(f, candidates, x, y); 5.97 + if (solve(f, candidates)) { 5.98 + break; 5.99 + } else { 5.100 + f.clearCellValue(x, y); 5.101 + restoreBackup(candidates, cb); 5.102 + // Remove current candidate anyway 5.103 + candidates[x][y].remove(c); 5.104 + } 5.105 + } 5.106 + } 5.107 + if (f.isCellEmpty(x, y)) { 5.108 + restoreBackup(f, fieldBackup); 5.109 + restoreBackup(candidates, candidatesBackup); 5.110 + return false; 5.111 + } 5.112 + } 5.113 + } 5.114 + 5.115 + return true; 5.116 + } 5.117 + 5.118 + public boolean solve(Field f) { 5.119 + 5.120 + // Calculate initial candidates 5.121 + List<Integer> candidates[][] = new List[9][9]; 5.122 + for (int x = 0 ; x < 9 ; x++) { 5.123 + for (int y = 0 ; y < 9 ; y++) { 5.124 + candidates[x][y] = new ArrayList<>(9); 5.125 + if (f.getCellValue(x, y) == 0) { 5.126 + // All numbers are candidates 5.127 + for (int c = 1 ; c <= 9 ; c++) { 5.128 + candidates[x][y].add(c); 5.129 + } 5.130 + // Remove row duplicates 5.131 + int[] line = f.getRow(y); 5.132 + for (Integer c : line) { 5.133 + candidates[x][y].remove(c); 5.134 + } 5.135 + // Remove column duplicates 5.136 + line = f.getColumn(x); 5.137 + for (Integer c : line) { 5.138 + candidates[x][y].remove(c); 5.139 + } 5.140 + // Remove square duplicates 5.141 + int[][] square = f.getSquare(x/3, y/3); 5.142 + for (int[] sq : square) { 5.143 + for (Integer c : sq) { 5.144 + candidates[x][y].remove(c); 5.145 + } 5.146 + } 5.147 + } 5.148 + } 5.149 + } 5.150 + 5.151 + // Backtrack 5.152 + return solve(f, candidates) && complete(f); 5.153 + } 5.154 + 5.155 public boolean check(Field f) { 5.156 int line[]; 5.157 for (int i = 0 ; i < 9 ; i++) { 5.158 @@ -61,6 +202,25 @@ 5.159 return true; 5.160 } 5.161 5.162 + private boolean complete(Field f) { 5.163 + for (int i = 0 ; i < 9 ; i++) { 5.164 + if (!complete(f.getRow(i))) { 5.165 + return false; 5.166 + } 5.167 + if (!complete(f.getColumn(i))) { 5.168 + return false; 5.169 + } 5.170 + } 5.171 + for (int x = 0 ; x < 3 ; x++) { 5.172 + for (int y = 0 ; y < 3 ; y++) { 5.173 + if (!complete(f.getSquare(x, y))) { 5.174 + return false; 5.175 + } 5.176 + } 5.177 + } 5.178 + return true; 5.179 + } 5.180 + 5.181 private boolean complete(int[][] square) { 5.182 for (int x = 0 ; x < 3 ; x++) { 5.183 for (int y = 0 ; y < 3 ; y++) {
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 6.2 +++ b/test-sudoku Thu Jan 31 18:44:44 2013 +0100 6.3 @@ -0,0 +1,9 @@ 6.4 +_ 1 _ 9 _ _ 8 _ _ 6.5 +_ _ _ _ _ 8 _ _ 4 6.6 +6 _ 5 _ _ _ 7 _ _ 6.7 +_ 9 _ _ 6 _ _ _ 8 6.8 +_ _ _ 2 _ 7 _ _ _ 6.9 +8 _ _ _ 3 _ _ 6 _ 6.10 +_ _ 2 _ _ _ 5 _ 3 6.11 +1 _ _ 4 _ _ _ _ _ 6.12 +_ _ 6 _ _ 2 _ 1 _
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/veryhard-sudoku Thu Jan 31 18:44:44 2013 +0100 7.3 @@ -0,0 +1,9 @@ 7.4 +_ _ _ 1 9 _ _ _ 8 7.5 +1 _ _ 2 _ 7 9 6 _ 7.6 +6 9 _ _ _ 4 _ _ _ 7.7 +_ _ _ _ _ _ 1 _ _ 7.8 +_ 5 _ 6 _ 9 _ 7 _ 7.9 +_ _ 3 _ _ _ _ _ _ 7.10 +_ _ _ 9 _ _ _ 8 1 7.11 +_ 1 6 7 _ 8 _ _ 3 7.12 +9 _ _ _ 1 2 _ _ _