Mercurial > hg > Sudoku / changeset

     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 _ _ _