--- 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++) {