# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1359654284 -3600
# Node ID 2c0a2766461cfdfd10ef88a9e799fd3b88551f9a
# Parent  5bab2e97133337433f295d3ffcb61d39572a7e4e
added solving algorithm

diff -r 5bab2e971333 -r 2c0a2766461c easy-sudoku
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/easy-sudoku	Thu Jan 31 18:44:44 2013 +0100
@@ -0,0 +1,9 @@
+3 _ _ 2 4 _ _ 6 _
+_ 4 _ _ _ _ _ 5 3
+1 8 9 6 3 5 4 _ _
+_ _ _ _ 8 _ 2 _ _
+_ _ 7 4 9 6 8 _ 1
+8 9 3 1 5 _ 6 _ 4
+_ _ 1 9 2 _ 5 _ _
+2 _ _ 3 _ _ 7 4 _
+9 6 _ 5 _ _ 3 _ 2
diff -r 5bab2e971333 -r 2c0a2766461c src/de/uapcore/sudoku/ActionHandler.java
--- a/src/de/uapcore/sudoku/ActionHandler.java	Sun Jan 27 15:03:57 2013 +0100
+++ b/src/de/uapcore/sudoku/ActionHandler.java	Thu Jan 31 18:44:44 2013 +0100
@@ -134,7 +134,10 @@
     }
     
     private void solve() {
-        // TODO: solve
+        if (!solver.check(field) || !solver.solve(field)) {
+            JOptionPane.showMessageDialog(field, "Das Feld ist nicht lösbar!",
+                    "Sudoku", JOptionPane.WARNING_MESSAGE);
+        }
     }
     
     private boolean saveUnsaved() {
@@ -162,6 +165,7 @@
         switch (e.getActionCommand()) {
         case NEW:
             if (saveUnsaved()) {
+                doc.clearFilename();
                 field.clear();
             }
             break;
diff -r 5bab2e971333 -r 2c0a2766461c src/de/uapcore/sudoku/DocumentHandler.java
--- a/src/de/uapcore/sudoku/DocumentHandler.java	Sun Jan 27 15:03:57 2013 +0100
+++ b/src/de/uapcore/sudoku/DocumentHandler.java	Thu Jan 31 18:44:44 2013 +0100
@@ -76,6 +76,7 @@
                 throw new IOException("Kein Sudoku-Feld enthalten!");
             }
         }
+        field.setAllCellsModified(false);
     }
     
     public void save(Field field) throws IOException {
diff -r 5bab2e971333 -r 2c0a2766461c src/de/uapcore/sudoku/Field.java
--- a/src/de/uapcore/sudoku/Field.java	Sun Jan 27 15:03:57 2013 +0100
+++ b/src/de/uapcore/sudoku/Field.java	Thu Jan 31 18:44:44 2013 +0100
@@ -92,6 +92,10 @@
         super.paintChildren(graphics);
     }
     
+    public boolean isCellEmpty(int x, int y) {
+        return getCellValue(x, y) == 0;
+    }
+    
     public int getCellValue(int x, int y) {
         return cells[x][y].getValue();
     }
@@ -100,6 +104,14 @@
         cells[x][y].setValue(v);
     }
     
+    public void clearCellValue(int x, int y) {
+        setCellValue(x, y, 0);
+    }
+    
+    public void setCellModified(int x, int y, boolean modified) {
+        cells[x][y].setModified(modified);
+    }
+    
     public void setAllCellsModified(boolean modified) {
         for (int x = 0 ; x < 9 ; x++) {
             for (int y = 0 ; y < 9 ; y++) {
diff -r 5bab2e971333 -r 2c0a2766461c src/de/uapcore/sudoku/Solver.java
--- a/src/de/uapcore/sudoku/Solver.java	Sun Jan 27 15:03:57 2013 +0100
+++ b/src/de/uapcore/sudoku/Solver.java	Thu Jan 31 18:44:44 2013 +0100
@@ -26,6 +26,9 @@
 
 package de.uapcore.sudoku;
 
+import java.util.ArrayList;
+import java.util.List;
+
 /**
  *
  * @author mike
@@ -35,6 +38,144 @@
     public Solver() {
     }
     
+    private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
+        Integer c = candidates[x][y].remove(0);
+        f.setCellValue(x, y, c);
+        f.setCellModified(x, y, true);
+        for (int i = 0 ; i < 9 ; i++) {
+            candidates[x][i].remove(c);
+            candidates[i][y].remove(c);
+        }
+        for (int i = 0 ; i < 3 ; i++) {
+            for (int j = 0 ; j < 3 ; j++) {
+                candidates[x-x%3+i][y-y%3+j].remove(c);
+            }
+        }
+        return c;
+    }
+    
+    private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                candidatesBackup[x][y] = new ArrayList<>(9);
+                candidatesBackup[x][y].addAll(candidates[x][y]);
+            }
+        }
+    }
+    
+    private void makeBackup(Field f, int[][] fieldBackup) {
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                fieldBackup[x][y] = f.getCellValue(x, y);
+            }
+        }
+    }
+    
+    private void restoreBackup(Field f, int[][] fieldBackup) {
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                f.setCellValue(x, y, fieldBackup[x][y]);
+            }
+        }
+    }
+    
+    private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                candidates[x][y].clear();
+                candidates[x][y].addAll(candidatesBackup[x][y]);
+            }
+        }
+    }
+    
+    private boolean solve(Field f, List<Integer>[][] candidates) {
+        
+        // Make backup
+        List<Integer>[][] candidatesBackup = new List[9][9];
+        int[][] fieldBackup = new int[9][9];
+        makeBackup(candidates, candidatesBackup);
+        makeBackup(f, fieldBackup);
+        
+        // Fill in distinct solutions
+        boolean fillDistinct;
+        do {
+            fillDistinct = false;
+            for (int x = 0 ; x < 9 ; x++) {
+                for (int y = 0 ; y < 9 ; y++) {
+                    if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
+                        fillInCandidate(f, candidates, x, y);
+                        fillDistinct = true;
+                    }
+                }
+            }
+        } while (fillDistinct);
+        
+        // Try out remaining candidates
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                if (f.isCellEmpty(x, y)) {
+                    while (candidates[x][y].size() > 0) {
+                        List<Integer>[][] cb = new List[9][9];
+                        makeBackup(candidates, cb);
+                        Integer c = fillInCandidate(f, candidates, x, y);
+                        if (solve(f, candidates)) {
+                            break;
+                        } else {
+                            f.clearCellValue(x, y);
+                            restoreBackup(candidates, cb);
+                            // Remove current candidate anyway
+                            candidates[x][y].remove(c);
+                        }
+                    }
+                }
+                if (f.isCellEmpty(x, y)) {
+                    restoreBackup(f, fieldBackup);
+                    restoreBackup(candidates, candidatesBackup);
+                    return false;
+                }
+            }
+        }
+        
+        return true;
+    }
+    
+    public boolean solve(Field f) {
+        
+        // Calculate initial candidates
+        List<Integer> candidates[][] = new List[9][9];
+        for (int x = 0 ; x < 9 ; x++) {
+            for (int y = 0 ; y < 9 ; y++) {
+                candidates[x][y] = new ArrayList<>(9);
+                if (f.getCellValue(x, y) == 0) {
+                    // All numbers are candidates
+                    for (int c = 1 ; c <= 9 ; c++) {
+                        candidates[x][y].add(c);
+                    }
+                    // Remove row duplicates
+                    int[] line = f.getRow(y);
+                    for (Integer c : line) {
+                        candidates[x][y].remove(c);
+                    }
+                    // Remove column duplicates
+                    line = f.getColumn(x);
+                    for (Integer c : line) {
+                        candidates[x][y].remove(c);
+                    }
+                    // Remove square duplicates
+                    int[][] square = f.getSquare(x/3, y/3);
+                    for (int[] sq : square) {
+                        for (Integer c : sq) {
+                            candidates[x][y].remove(c);
+                        }
+                    }
+                }
+            }
+        }
+        
+        // Backtrack
+        return solve(f, candidates) && complete(f);
+    }
+    
     public boolean check(Field f) {
         int line[];
         for (int i = 0 ; i < 9 ; i++) {
@@ -61,6 +202,25 @@
         return true;
     }
     
+    private boolean complete(Field f) {
+        for (int i = 0 ; i < 9 ; i++) {
+            if (!complete(f.getRow(i))) {
+                return false;
+            }
+            if (!complete(f.getColumn(i))) {
+                return false;
+            }
+        }
+        for (int x = 0 ; x < 3 ; x++) {
+            for (int y = 0 ; y < 3 ; y++) {
+                if (!complete(f.getSquare(x, y))) {
+                    return false;
+                }
+            }
+        }
+        return true;
+    }
+    
     private boolean complete(int[][] square) {
         for (int x = 0 ; x < 3 ; x++) {
             for (int y = 0 ; y < 3 ; y++) {
diff -r 5bab2e971333 -r 2c0a2766461c test-sudoku
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test-sudoku	Thu Jan 31 18:44:44 2013 +0100
@@ -0,0 +1,9 @@
+_ 1 _ 9 _ _ 8 _ _
+_ _ _ _ _ 8 _ _ 4
+6 _ 5 _ _ _ 7 _ _
+_ 9 _ _ 6 _ _ _ 8
+_ _ _ 2 _ 7 _ _ _
+8 _ _ _ 3 _ _ 6 _
+_ _ 2 _ _ _ 5 _ 3
+1 _ _ 4 _ _ _ _ _
+_ _ 6 _ _ 2 _ 1 _
diff -r 5bab2e971333 -r 2c0a2766461c veryhard-sudoku
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/veryhard-sudoku	Thu Jan 31 18:44:44 2013 +0100
@@ -0,0 +1,9 @@
+_ _ _ 1 9 _ _ _ 8
+1 _ _ 2 _ 7 9 6 _
+6 9 _ _ _ 4 _ _ _
+_ _ _ _ _ _ 1 _ _
+_ 5 _ 6 _ 9 _ 7 _
+_ _ 3 _ _ _ _ _ _
+_ _ _ 9 _ _ _ 8 1
+_ 1 6 7 _ 8 _ _ 3
+9 _ _ _ 1 2 _ _ _