001package ball.game.sudoku; 002/*- 003 * ########################################################################## 004 * Game Applications and Utilities 005 * $Id: RuleOfSums.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/RuleOfSums.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.SortedSet; 026import lombok.NoArgsConstructor; 027import lombok.ToString; 028 029/** 030 * Sudoku simple "rule-of-sums" {@link Rule} implementation. Calculates the 031 * minimum maximum possible value for any cell and removes any greater 032 * numbers from consideration. 033 * 034 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball} 035 * @version $Revision: 5285 $ 036 */ 037@ServiceProviderFor({ Rule.class }) 038@NoArgsConstructor @ToString 039public class RuleOfSums extends RuleOfElimination { 040 @Override 041 public boolean applyTo(Puzzle puzzle) { 042 boolean modified = false; 043 044 for (;;) { 045 if (iterate(puzzle)) { 046 modified |= true; 047 super.applyTo(puzzle); 048 } else { 049 break; 050 } 051 } 052 053 return modified; 054 } 055 056 private boolean iterate(Puzzle puzzle) { 057 boolean modified = false; 058 059 for (Cell cell : puzzle.values()) { 060 if (! cell.isSolved()) { 061 int max = cell.last(); 062 063 for (CoordinateMap<Cell> map : puzzle.subMapsOf(cell)) { 064 max = Math.min(max, max(map.values())); 065 } 066 067 SortedSet<Integer> set = cell.tailSet(max, false); 068 069 modified |= (! set.isEmpty()); 070 set.clear(); 071 } 072 } 073 074 return modified; 075 } 076 077 protected int max(Iterable<Cell> iterable) { 078 return ((Digits.SUM - sum(iterable)) 079 - (Digits.ALL.size() - (count(iterable) + 1))); 080 } 081}