diff -r e70a0e3555fb -r 576e7a2861ae src/de/uapcore/sudoku/Solver.java --- a/src/de/uapcore/sudoku/Solver.java Fri Feb 01 10:18:47 2013 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,227 +0,0 @@ -/* - * Copyright 2013 Mike Becker. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -package de.uapcore.sudoku; - -import java.util.ArrayList; -import java.util.List; - -/** - * - * @author mike - */ -public final class Solver { - - public Solver() { - } - - private Integer fillInCandidate(Field f, List[][] 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[][] candidates, List[][] 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[][] candidates, List[][] 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[][] candidates) { - - // Make backup - List[][] 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[][] 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 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); - } - - public boolean check(Field f) { - int line[]; - for (int i = 0 ; i < 9 ; i++) { - line = f.getRow(i); - if (!valid(line)) { - return false; - } - line = f.getColumn(i); - if (!valid(line)) { - return false; - } - } - - int square[][]; - for (int x = 0 ; x < 3 ; x++) { - for (int y = 0 ; y < 3 ; y++) { - square = f.getSquare(x, y); - if (!valid(square)) { - return false; - } - } - } - - return true; - } - - private boolean valid(int[] line) { - int numbers[]; - numbers = new int[9]; - for (int i = 0 ; i < 9 ; i++) { - int l = line[i]-1; - if (l >= 0) { - if ((++numbers[l]) > 1) { - return false; - } - } - } - - return true; - } - - private boolean valid(int[][] square) { - int[] line = new int[9]; - for (int x = 0 ; x < 3 ; x++) { - System.arraycopy(square[x], 0, line, 3*x, 3); - } - return valid(line); - } -}