001package ball.game.sudoku;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * $Id: RuleOfSums.java 5285 2020-02-05 04:23:21Z ball $
006 * $HeadURL: svn+ssh://svn.hcf.dev/var/spool/scm/repository.svn/ball-game/trunk/src/main/java/ball/game/sudoku/RuleOfSums.java $
007 * %%
008 * Copyright (C) 2010 - 2020 Allen D. Ball
009 * %%
010 * Licensed under the Apache License, Version 2.0 (the "License");
011 * you may not use this file except in compliance with the License.
012 * You may obtain a copy of the License at
013 *
014 *      http://www.apache.org/licenses/LICENSE-2.0
015 *
016 * Unless required by applicable law or agreed to in writing, software
017 * distributed under the License is distributed on an "AS IS" BASIS,
018 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
019 * See the License for the specific language governing permissions and
020 * limitations under the License.
021 * ##########################################################################
022 */
023import ball.annotation.ServiceProviderFor;
024import ball.util.CoordinateMap;
025import java.util.SortedSet;
026import lombok.NoArgsConstructor;
027import lombok.ToString;
028
029/**
030 * Sudoku simple "rule-of-sums" {@link Rule} implementation.  Calculates the
031 * minimum maximum possible value for any cell and removes any greater
032 * numbers from consideration.
033 *
034 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
035 * @version $Revision: 5285 $
036 */
037@ServiceProviderFor({ Rule.class })
038@NoArgsConstructor @ToString
039public class RuleOfSums extends RuleOfElimination {
040    @Override
041    public boolean applyTo(Puzzle puzzle) {
042        boolean modified = false;
043
044        for (;;) {
045            if (iterate(puzzle)) {
046                modified |= true;
047                super.applyTo(puzzle);
048            } else {
049                break;
050            }
051        }
052
053        return modified;
054    }
055
056    private boolean iterate(Puzzle puzzle) {
057        boolean modified = false;
058
059        for (Cell cell : puzzle.values()) {
060            if (! cell.isSolved()) {
061                int max = cell.last();
062
063                for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) {
064                    max = Math.min(max, max(map.values()));
065                }
066
067                SortedSet<Integer> set = cell.tailSet(max, false);
068
069                modified |= (! set.isEmpty());
070                set.clear();
071            }
072        }
073
074        return modified;
075    }
076
077    protected int max(Iterable<Cell> iterable) {
078        return ((Digits.SUM - sum(iterable))
079                - (Digits.ALL.size() - (count(iterable) + 1)));
080    }
081}