1.1 --- a/src/de/uapcore/sudoku/Solver.java Sun Jan 27 15:03:57 2013 +0100
1.2 +++ b/src/de/uapcore/sudoku/Solver.java Thu Jan 31 18:44:44 2013 +0100
1.3 @@ -26,6 +26,9 @@
1.4
1.5 package de.uapcore.sudoku;
1.6
1.7 +import java.util.ArrayList;
1.8 +import java.util.List;
1.9 +
1.10 /**
1.11 *
1.12 * @author mike
1.13 @@ -35,6 +38,144 @@
1.14 public Solver() {
1.15 }
1.16
1.17 + private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
1.18 + Integer c = candidates[x][y].remove(0);
1.19 + f.setCellValue(x, y, c);
1.20 + f.setCellModified(x, y, true);
1.21 + for (int i = 0 ; i < 9 ; i++) {
1.22 + candidates[x][i].remove(c);
1.23 + candidates[i][y].remove(c);
1.24 + }
1.25 + for (int i = 0 ; i < 3 ; i++) {
1.26 + for (int j = 0 ; j < 3 ; j++) {
1.27 + candidates[x-x%3+i][y-y%3+j].remove(c);
1.28 + }
1.29 + }
1.30 + return c;
1.31 + }
1.32 +
1.33 + private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
1.34 + for (int x = 0 ; x < 9 ; x++) {
1.35 + for (int y = 0 ; y < 9 ; y++) {
1.36 + candidatesBackup[x][y] = new ArrayList<>(9);
1.37 + candidatesBackup[x][y].addAll(candidates[x][y]);
1.38 + }
1.39 + }
1.40 + }
1.41 +
1.42 + private void makeBackup(Field f, int[][] fieldBackup) {
1.43 + for (int x = 0 ; x < 9 ; x++) {
1.44 + for (int y = 0 ; y < 9 ; y++) {
1.45 + fieldBackup[x][y] = f.getCellValue(x, y);
1.46 + }
1.47 + }
1.48 + }
1.49 +
1.50 + private void restoreBackup(Field f, int[][] fieldBackup) {
1.51 + for (int x = 0 ; x < 9 ; x++) {
1.52 + for (int y = 0 ; y < 9 ; y++) {
1.53 + f.setCellValue(x, y, fieldBackup[x][y]);
1.54 + }
1.55 + }
1.56 + }
1.57 +
1.58 + private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
1.59 + for (int x = 0 ; x < 9 ; x++) {
1.60 + for (int y = 0 ; y < 9 ; y++) {
1.61 + candidates[x][y].clear();
1.62 + candidates[x][y].addAll(candidatesBackup[x][y]);
1.63 + }
1.64 + }
1.65 + }
1.66 +
1.67 + private boolean solve(Field f, List<Integer>[][] candidates) {
1.68 +
1.69 + // Make backup
1.70 + List<Integer>[][] candidatesBackup = new List[9][9];
1.71 + int[][] fieldBackup = new int[9][9];
1.72 + makeBackup(candidates, candidatesBackup);
1.73 + makeBackup(f, fieldBackup);
1.74 +
1.75 + // Fill in distinct solutions
1.76 + boolean fillDistinct;
1.77 + do {
1.78 + fillDistinct = false;
1.79 + for (int x = 0 ; x < 9 ; x++) {
1.80 + for (int y = 0 ; y < 9 ; y++) {
1.81 + if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
1.82 + fillInCandidate(f, candidates, x, y);
1.83 + fillDistinct = true;
1.84 + }
1.85 + }
1.86 + }
1.87 + } while (fillDistinct);
1.88 +
1.89 + // Try out remaining candidates
1.90 + for (int x = 0 ; x < 9 ; x++) {
1.91 + for (int y = 0 ; y < 9 ; y++) {
1.92 + if (f.isCellEmpty(x, y)) {
1.93 + while (candidates[x][y].size() > 0) {
1.94 + List<Integer>[][] cb = new List[9][9];
1.95 + makeBackup(candidates, cb);
1.96 + Integer c = fillInCandidate(f, candidates, x, y);
1.97 + if (solve(f, candidates)) {
1.98 + break;
1.99 + } else {
1.100 + f.clearCellValue(x, y);
1.101 + restoreBackup(candidates, cb);
1.102 + // Remove current candidate anyway
1.103 + candidates[x][y].remove(c);
1.104 + }
1.105 + }
1.106 + }
1.107 + if (f.isCellEmpty(x, y)) {
1.108 + restoreBackup(f, fieldBackup);
1.109 + restoreBackup(candidates, candidatesBackup);
1.110 + return false;
1.111 + }
1.112 + }
1.113 + }
1.114 +
1.115 + return true;
1.116 + }
1.117 +
1.118 + public boolean solve(Field f) {
1.119 +
1.120 + // Calculate initial candidates
1.121 + List<Integer> candidates[][] = new List[9][9];
1.122 + for (int x = 0 ; x < 9 ; x++) {
1.123 + for (int y = 0 ; y < 9 ; y++) {
1.124 + candidates[x][y] = new ArrayList<>(9);
1.125 + if (f.getCellValue(x, y) == 0) {
1.126 + // All numbers are candidates
1.127 + for (int c = 1 ; c <= 9 ; c++) {
1.128 + candidates[x][y].add(c);
1.129 + }
1.130 + // Remove row duplicates
1.131 + int[] line = f.getRow(y);
1.132 + for (Integer c : line) {
1.133 + candidates[x][y].remove(c);
1.134 + }
1.135 + // Remove column duplicates
1.136 + line = f.getColumn(x);
1.137 + for (Integer c : line) {
1.138 + candidates[x][y].remove(c);
1.139 + }
1.140 + // Remove square duplicates
1.141 + int[][] square = f.getSquare(x/3, y/3);
1.142 + for (int[] sq : square) {
1.143 + for (Integer c : sq) {
1.144 + candidates[x][y].remove(c);
1.145 + }
1.146 + }
1.147 + }
1.148 + }
1.149 + }
1.150 +
1.151 + // Backtrack
1.152 + return solve(f, candidates) && complete(f);
1.153 + }
1.154 +
1.155 public boolean check(Field f) {
1.156 int line[];
1.157 for (int i = 0 ; i < 9 ; i++) {
1.158 @@ -61,6 +202,25 @@
1.159 return true;
1.160 }
1.161
1.162 + private boolean complete(Field f) {
1.163 + for (int i = 0 ; i < 9 ; i++) {
1.164 + if (!complete(f.getRow(i))) {
1.165 + return false;
1.166 + }
1.167 + if (!complete(f.getColumn(i))) {
1.168 + return false;
1.169 + }
1.170 + }
1.171 + for (int x = 0 ; x < 3 ; x++) {
1.172 + for (int y = 0 ; y < 3 ; y++) {
1.173 + if (!complete(f.getSquare(x, y))) {
1.174 + return false;
1.175 + }
1.176 + }
1.177 + }
1.178 + return true;
1.179 + }
1.180 +
1.181 private boolean complete(int[][] square) {
1.182 for (int x = 0 ; x < 3 ; x++) {
1.183 for (int y = 0 ; y < 3 ; y++) {
