default/src/main/java/de/uapcore/sudoku/Solver.java

/*
 * 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;

/**
 * Implements the backtracking algorithm for solving the Sudoku.
 */
public final class 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;
    }

    /**
     * Attempts to solve the given Sudoku field.
     *
     * The solution, if any, is directly entered into the field.
     * All solved fields will be in modified state.
     * The already given fields are left untouched.
     *
     * @param f the field to solve
     * @return true if a solution could be found, false if the field is unsolvable
     */
    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);
    }

    /**
     * Performs a fast check whether any field violates the Sudoku rules.
     *
     * @param f the field to check
     * @return true, if the check succeeds, false otherwise
     */
    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);
    }
}