001package ball.game.sudoku;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * $Id: RuleOfUniqueness.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/RuleOfUniqueness.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.TreeSet;
026import lombok.NoArgsConstructor;
027import lombok.ToString;
028
029/**
030 * Sudoku "rule-of-uniqueness" {@link Rule} implementation.  If a digit is
031 * the only possible solution for a {@link Cell} in its row, column, and 3x3
032 * nonet once other possible solutions for the other cells in the same row,
033 * column, and nonet are removed then it must be the solution for that cell.
034 *
035 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
036 * @version $Revision: 5285 $
037 */
038@ServiceProviderFor({ Rule.class })
039@NoArgsConstructor @ToString
040public class RuleOfUniqueness extends RuleOfElimination {
041    @Override
042    public boolean applyTo(Puzzle puzzle) {
043        boolean modified = false;
044
045        for (;;) {
046            if (iterate(puzzle)) {
047                modified |= true;
048                super.applyTo(puzzle);
049            } else {
050                break;
051            }
052        }
053
054        return modified;
055    }
056
057    private boolean iterate(Puzzle puzzle) {
058        boolean modified = false;
059
060        for (Cell cell : puzzle.values()) {
061            if (! cell.isSolved()) {
062                TreeSet<Integer> set = new TreeSet<>();
063
064                for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) {
065                    TreeSet<Integer> subset = new TreeSet<>(cell);
066
067                    for (Cell other : map.values()) {
068                        if (other != cell) {
069                            subset.removeAll(other);
070                        }
071                    }
072
073                    set.addAll(subset);
074                }
075
076                if (! set.isEmpty()) {
077                    modified |= cell.retainAll(set);
078                }
079            }
080        }
081
082        return modified;
083    }
084}