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