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}