001package ball.game.sudoku;
002/*-
003 * ##########################################################################
004 * Game Applications and Utilities
005 * $Id: RuleOfNIdenticalCellsOfSizeN.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/RuleOfNIdenticalCellsOfSizeN.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 lombok.NoArgsConstructor;
026import lombok.ToString;
027
028import static java.util.Collections.frequency;
029
030/**
031 * Sudoku "rule-of-N-identical-cells-of-size-N" {@link Rule} implementation.
032 * If a row, column, or nonet contain two cells that are identical with the
033 * same two possible digits, then those digits may be removed as possible
034 * solutions from the other cells in that same row, column, or nonet because
035 * those two digits may only be used as a solution in those two cells.
036 *
037 * This idea can be extended to three identical cells of three remaining
038 * options, four of four, etc...  It also works for N=1 (cell is solved).
039 *
040 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
041 * @version $Revision: 5285 $
042 */
043@ServiceProviderFor({ Rule.class })
044@NoArgsConstructor @ToString
045public class RuleOfNIdenticalCellsOfSizeN extends RuleOfElimination {
046    @Override
047    public boolean applyTo(Puzzle puzzle) {
048        boolean modified = false;
049
050        for (;;) {
051            if (iterate(puzzle)) {
052                modified |= true;
053                super.applyTo(puzzle);
054            } else {
055                break;
056            }
057        }
058
059        return modified;
060    }
061
062    private boolean iterate(Puzzle puzzle) {
063        boolean modified = false;
064
065        for (Cell cell : puzzle.values()) {
066            if (! cell.isSolved()) {
067                for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) {
068                    if (frequency(map.values(), cell) == cell.size()) {
069                        for (Cell other : map.values()) {
070                            if (! other.equals(cell)) {
071                                modified |= other.removeAll(cell);
072                            }
073                        }
074                    }
075                }
076            }
077        }
078
079        return modified;
080    }
081}