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}