001package ball.game.sudoku;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * $Id: RuleOfElimination.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/RuleOfElimination.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 lombok.NoArgsConstructor;
024import lombok.ToString;
025import ball.annotation.ServiceProviderFor;
026import ball.util.CoordinateMap;
027
028/**
029 * Sudoku "rule-of-elimination" {@link Rule} implementation.  If a digit is
030 * the solution to a {@link Cell} then it cannot be the solution to any
031 * other {@link Cell} in the row, column, or 3x3 nonet.
032 *
033 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
034 * @version $Revision: 5285 $
035 */
036@ServiceProviderFor({ Rule.class })
037@NoArgsConstructor @ToString
038public class RuleOfElimination extends Rule {
039    @Override
040    public boolean applyTo(Puzzle puzzle) {
041        boolean modified = false;
042
043        for (;;) {
044            if (iterate(puzzle)) {
045                modified |= true;
046            } else {
047                break;
048            }
049        }
050
051        return modified;
052    }
053
054    private boolean iterate(Puzzle puzzle) {
055        boolean modified = false;
056
057        for (Cell cell : puzzle.values()) {
058            if (cell.isSolved()) {
059                for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) {
060                    for (Cell other : map.values()) {
061                        if (other != cell) {
062                            modified |= other.removeAll(cell);
063                        }
064                    }
065                }
066            }
067        }
068
069        return modified;
070    }
071}