universe@3: /*
universe@3:  * Copyright 2013 Mike Becker. All rights reserved.
universe@3:  * 
universe@3:  * Redistribution and use in source and binary forms, with or without
universe@3:  * modification, are permitted provided that the following conditions are met:
universe@3:  * 
universe@3:  * 1. Redistributions of source code must retain the above copyright
universe@3:  *    notice, this list of conditions and the following disclaimer.
universe@3:  * 
universe@3:  * 2. Redistributions in binary form must reproduce the above copyright
universe@3:  *    notice, this list of conditions and the following disclaimer in the
universe@3:  *    documentation and/or other materials provided with the distribution.
universe@3:  * 
universe@3:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@3:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@3:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@3:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@3:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@3:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@3:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@3:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@3:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@3:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@3:  * POSSIBILITY OF SUCH DAMAGE.
universe@3:  */
universe@3: 
universe@2: package de.uapcore.sudoku;
universe@2: 
universe@7: import java.util.ArrayList;
universe@7: import java.util.List;
universe@7: 
universe@2: /**
universe@2:  *
universe@2:  * @author mike
universe@2:  */
universe@2: public final class Solver {
universe@2:     
universe@2:     public Solver() {
universe@2:     }
universe@2:     
universe@7:     private Integer fillInCandidate(Field f, List<Integer>[][] candidates, int x, int y) {
universe@7:         Integer c = candidates[x][y].remove(0);
universe@7:         f.setCellValue(x, y, c);
universe@7:         f.setCellModified(x, y, true);
universe@7:         for (int i = 0 ; i < 9 ; i++) {
universe@7:             candidates[x][i].remove(c);
universe@7:             candidates[i][y].remove(c);
universe@7:         }
universe@7:         for (int i = 0 ; i < 3 ; i++) {
universe@7:             for (int j = 0 ; j < 3 ; j++) {
universe@7:                 candidates[x-x%3+i][y-y%3+j].remove(c);
universe@7:             }
universe@7:         }
universe@7:         return c;
universe@7:     }
universe@7:     
universe@7:     private void makeBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 candidatesBackup[x][y] = new ArrayList<>(9);
universe@7:                 candidatesBackup[x][y].addAll(candidates[x][y]);
universe@7:             }
universe@7:         }
universe@7:     }
universe@7:     
universe@7:     private void makeBackup(Field f, int[][] fieldBackup) {
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 fieldBackup[x][y] = f.getCellValue(x, y);
universe@7:             }
universe@7:         }
universe@7:     }
universe@7:     
universe@7:     private void restoreBackup(Field f, int[][] fieldBackup) {
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 f.setCellValue(x, y, fieldBackup[x][y]);
universe@7:             }
universe@7:         }
universe@7:     }
universe@7:     
universe@7:     private void restoreBackup(List<Integer>[][] candidates, List<Integer>[][] candidatesBackup) {
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 candidates[x][y].clear();
universe@7:                 candidates[x][y].addAll(candidatesBackup[x][y]);
universe@7:             }
universe@7:         }
universe@7:     }
universe@7:     
universe@7:     private boolean solve(Field f, List<Integer>[][] candidates) {
universe@7:         
universe@7:         // Make backup
universe@7:         List<Integer>[][] candidatesBackup = new List[9][9];
universe@7:         int[][] fieldBackup = new int[9][9];
universe@7:         makeBackup(candidates, candidatesBackup);
universe@7:         makeBackup(f, fieldBackup);
universe@7:         
universe@7:         // Fill in distinct solutions
universe@7:         boolean fillDistinct;
universe@7:         do {
universe@7:             fillDistinct = false;
universe@7:             for (int x = 0 ; x < 9 ; x++) {
universe@7:                 for (int y = 0 ; y < 9 ; y++) {
universe@7:                     if (f.isCellEmpty(x, y) && candidates[x][y].size() == 1) {
universe@7:                         fillInCandidate(f, candidates, x, y);
universe@7:                         fillDistinct = true;
universe@7:                     }
universe@7:                 }
universe@7:             }
universe@7:         } while (fillDistinct);
universe@7:         
universe@7:         // Try out remaining candidates
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 if (f.isCellEmpty(x, y)) {
universe@7:                     while (candidates[x][y].size() > 0) {
universe@7:                         List<Integer>[][] cb = new List[9][9];
universe@7:                         makeBackup(candidates, cb);
universe@7:                         Integer c = fillInCandidate(f, candidates, x, y);
universe@7:                         if (solve(f, candidates)) {
universe@7:                             break;
universe@7:                         } else {
universe@7:                             f.clearCellValue(x, y);
universe@7:                             restoreBackup(candidates, cb);
universe@7:                             // Remove current candidate anyway
universe@7:                             candidates[x][y].remove(c);
universe@7:                         }
universe@7:                     }
universe@7:                 }
universe@7:                 if (f.isCellEmpty(x, y)) {
universe@7:                     restoreBackup(f, fieldBackup);
universe@7:                     restoreBackup(candidates, candidatesBackup);
universe@7:                     return false;
universe@7:                 }
universe@7:             }
universe@7:         }
universe@7:         
universe@7:         return true;
universe@7:     }
universe@7:     
universe@7:     public boolean solve(Field f) {
universe@7:         
universe@7:         // Calculate initial candidates
universe@7:         List<Integer> candidates[][] = new List[9][9];
universe@7:         for (int x = 0 ; x < 9 ; x++) {
universe@7:             for (int y = 0 ; y < 9 ; y++) {
universe@7:                 candidates[x][y] = new ArrayList<>(9);
universe@7:                 if (f.getCellValue(x, y) == 0) {
universe@7:                     // All numbers are candidates
universe@7:                     for (int c = 1 ; c <= 9 ; c++) {
universe@7:                         candidates[x][y].add(c);
universe@7:                     }
universe@7:                     // Remove row duplicates
universe@7:                     int[] line = f.getRow(y);
universe@7:                     for (Integer c : line) {
universe@7:                         candidates[x][y].remove(c);
universe@7:                     }
universe@7:                     // Remove column duplicates
universe@7:                     line = f.getColumn(x);
universe@7:                     for (Integer c : line) {
universe@7:                         candidates[x][y].remove(c);
universe@7:                     }
universe@7:                     // Remove square duplicates
universe@7:                     int[][] square = f.getSquare(x/3, y/3);
universe@7:                     for (int[] sq : square) {
universe@7:                         for (Integer c : sq) {
universe@7:                             candidates[x][y].remove(c);
universe@7:                         }
universe@7:                     }
universe@7:                 }
universe@7:             }
universe@7:         }
universe@7:         
universe@7:         // Backtrack
universe@7:         return solve(f, candidates) && complete(f);
universe@7:     }
universe@7:     
universe@2:     public boolean check(Field f) {
universe@2:         int line[];
universe@2:         for (int i = 0 ; i < 9 ; i++) {
universe@5:             line = f.getRow(i);
universe@2:             if (!valid(line)) {
universe@2:                 return false;
universe@2:             }
universe@5:             line = f.getColumn(i);
universe@2:             if (!valid(line)) {
universe@2:                 return false;
universe@2:             }
universe@2:         }
universe@2:         
universe@2:         int square[][];
universe@2:         for (int x = 0 ; x < 3 ; x++) {
universe@2:             for (int y = 0 ; y < 3 ; y++) {
universe@5:                 square = f.getSquare(x, y);
universe@2:                 if (!valid(square)) {
universe@2:                     return false;
universe@2:                 }
universe@2:             }
universe@2:         }
universe@2:         
universe@2:         return true;
universe@2:     }
universe@2:     
universe@7:     private boolean complete(Field f) {
universe@7:         for (int i = 0 ; i < 9 ; i++) {
universe@7:             if (!complete(f.getRow(i))) {
universe@7:                 return false;
universe@7:             }
universe@7:             if (!complete(f.getColumn(i))) {
universe@7:                 return false;
universe@7:             }
universe@7:         }
universe@7:         for (int x = 0 ; x < 3 ; x++) {
universe@7:             for (int y = 0 ; y < 3 ; y++) {
universe@7:                 if (!complete(f.getSquare(x, y))) {
universe@7:                     return false;
universe@7:                 }
universe@7:             }
universe@7:         }
universe@7:         return true;
universe@7:     }
universe@7:     
universe@2:     private boolean complete(int[][] square) {
universe@2:         for (int x = 0 ; x < 3 ; x++) {
universe@2:             for (int y = 0 ; y < 3 ; y++) {
universe@2:                 if (square[x][y] == 0) {
universe@2:                     return false;
universe@2:                 }
universe@2:             }    
universe@2:         }
universe@2:         return true;
universe@2:     }
universe@2:     
universe@2:     private boolean complete(int[] line) {
universe@2:         for (int i = 0 ; i < 9 ; i++) {
universe@2:             if (line[i] == 0) {
universe@2:                 return false;
universe@2:             }
universe@2:         }
universe@2:         return true;
universe@2:     }
universe@2:     
universe@2:     private boolean valid(int[] line) {
universe@5:         int numbers[];
universe@5:         numbers = new int[9];
universe@2:         for (int i = 0 ; i < 9 ; i++) {
universe@2:             int l = line[i]-1;
universe@2:             if (l >= 0) {
universe@5:                 if ((++numbers[l]) > 1) {
universe@2:                     return false;
universe@2:                 }
universe@2:             }
universe@2:         }
universe@2:         
universe@2:         return true;
universe@2:     }
universe@2:     
universe@2:     private boolean valid(int[][] square) {
universe@2:         int[] line = new int[9];
universe@2:         for (int x = 0 ; x < 3 ; x++) {
universe@5:             System.arraycopy(square[x], 0, line, 3*x, 3);
universe@2:         }
universe@2:         return valid(line);
universe@2:     }
universe@2: }