001package ball.game.sudoku;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * %%
006 * Copyright (C) 2010 - 2022 Allen D. Ball
007 * %%
008 * Licensed under the Apache License, Version 2.0 (the "License");
009 * you may not use this file except in compliance with the License.
010 * You may obtain a copy of the License at
011 *
012 *      http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 * ##########################################################################
020 */
021import ball.annotation.ServiceProviderFor;
022import ball.util.CoordinateMap;
023import java.util.TreeSet;
024import lombok.NoArgsConstructor;
025import lombok.ToString;
026
027/**
028 * Sudoku "rule-of-uniqueness" {@link Rule} implementation.  If a digit is
029 * the only possible solution for a {@link Cell} in its row, column, and 3x3
030 * nonet once other possible solutions for the other cells in the same row,
031 * column, and nonet are removed then it must be the solution for that cell.
032 *
033 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
034 */
035@ServiceProviderFor({ Rule.class })
036@NoArgsConstructor @ToString
037public class RuleOfUniqueness extends RuleOfElimination {
038    @Override
039    public boolean applyTo(Puzzle puzzle) {
040        var modified = false;
041
042        for (;;) {
043            if (iterate(puzzle)) {
044                modified |= true;
045                super.applyTo(puzzle);
046            } else {
047                break;
048            }
049        }
050
051        return modified;
052    }
053
054    private boolean iterate(Puzzle puzzle) {
055        var modified = false;
056
057        for (var cell : puzzle.values()) {
058            if (! cell.isSolved()) {
059                TreeSet<Integer> set = new TreeSet<>();
060
061                for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) {
062                    TreeSet<Integer> subset = new TreeSet<>(cell);
063
064                    for (var other : map.values()) {
065                        if (other != cell) {
066                            subset.removeAll(other);
067                        }
068                    }
069
070                    set.addAll(subset);
071                }
072
073                if (! set.isEmpty()) {
074                    modified |= cell.retainAll(set);
075                }
076            }
077        }
078
079        return modified;
080    }
081}