A friend of yours is learning how to solve Killer Sudokus (rules below) but struggling to figure out which digits can go in a cage.

They ask you to help them out by writing a small program that lists all valid combinations for a given cage, and any constraints that affect the cage.

To make the output of your program easy to read, the combinations it returns must be sorted.

- [Standard Sudoku rules][sudoku-rules] apply.

- The digits in a cage, usually marked by a dotted line, add up to the small number given in the corner of the cage.

- A digit may only occur once in a cage.

For a more detailed explanation, check out [this guide][killer-guide].

In a 3-digit cage with a sum of 7, there is only one valid combination: 124.

- 1 + 2 + 4 = 7

- Any other combination that adds up to 7, e.g. 232, would violate the rule of not repeating digits within a cage.

![Sudoku grid, with three killer cages that are marked as grouped together. The first killer cage is in the 3×3 box in the top left corner of the grid. The middle column of that box forms the cage, with the followings cells from top to bottom: first cell contains a 1 and a pencil mark of 7, indicating a cage sum of 7, second cell contains a 2, third cell contains a 5. The numbers are highlighted in red to indicate a mistake. The second killer cage is in the central 3×3 box of the grid. The middle column of that box forms the cage, with the followings cells from top to bottom: first cell contains a 1 and a pencil mark of 7, indicating a cage sum of 7, second cell contains a 2, third cell contains a 4. None of the numbers in this cage are highlighted and therefore don't contain any mistakes. The third killer cage follows the outside corner of the central 3×3 box of the grid. It is made up of the following three cells: the top left cell of the cage contains a 2, highlighted in red, and a cage sum of 7. The top right cell of the cage contains a 3. The bottom right cell of the cage contains a 2, highlighted in red. All other cells are empty.][one-solution-img]

In a 2-digit cage with a sum 10, there are 4 possible combinations:

- 19

- 28

- 37

- 46

![Sudoku grid, all squares empty except for the middle column, column 5, which has 8 rows filled. Each continguous two rows form a killer cage and are marked as grouped together. From top to bottom: first group is a cell with value 1 and a pencil mark indicating a cage sum of 10, cell with value 9. Second group is a cell with value 2 and a pencil mark of 10, cell with value 8. Third group is a cell with value 3 and a pencil mark of 10, cell with value 7. Fourth group is a cell with value 4 and a pencil mark of 10, cell with value 6. The last cell in the column is empty.][four-solutions-img]

In a 2-digit cage with a sum 10, where the column already contains a 1 and a 4, there are 2 possible combinations:

- 28

- 37

19 and 46 are not possible due to the 1 and 4 in the column according to standard Sudoku rules.

![Sudoku grid, all squares empty except for the middle column, column 5, which has 8 rows filled. The first row contains a 4, the second is empty, and the third contains a 1. The 1 is highlighted in red to indicate a mistake. The last 6 rows in the column form killer cages of two cells each. From top to bottom: first group is a cell with value 2 and a pencil mark indicating a cage sum of 10, cell with value 8. Second group is a cell with value 3 and a pencil mark of 10, cell with value 7. Third group is a cell with value 1, highlighted in red, and a pencil mark of 10, cell with value 9.][not-possible-img]

If you want to give an approachable Killer Sudoku a go, you can try out [this puzzle][clover-puzzle] by Clover, featured by [Mark Goodliffe on Cracking The Cryptic on the 21st of June 2021][goodliffe-video].

You can also find Killer Sudokus in varying difficulty in numerous newspapers, as well as Sudoku apps, books and websites.

The screenshots above have been generated using [F-Puzzles.com](https://www.f-puzzles.com/), a Puzzle Setting Tool by Eric Fox.

[sudoku-rules]: https://masteringsudoku.com/sudoku-rules-beginners/

[killer-guide]: https://masteringsudoku.com/killer-sudoku/

[one-solution-img]: https://assets.exercism.org/images/exercises/killer-sudoku-helper/example1.png

[four-solutions-img]: https://assets.exercism.org/images/exercises/killer-sudoku-helper/example2.png

[not-possible-img]: https://assets.exercism.org/images/exercises/killer-sudoku-helper/example3.png

[clover-puzzle]: https://app.crackingthecryptic.com/sudoku/HqTBn3Pr6R

[goodliffe-video]: https://youtu.be/c_NjEbFEeW0?t=1180

{

"authors": [

"sougat818"

],

"files": {

"solution": [

"src/main/java/KillerSudokuHelper.java"

],

"test": [

"src/test/java/KillerSudokuHelperTest.java"

],

"example": [

".meta/src/reference/java/KillerSudokuHelper.java"

],

"invalidator": [

"build.gradle"

]

},

"blurb": "Write a tool that makes it easier to solve Killer Sudokus",

"source": "Created by Sascha Mann, Jeremy Walker, and BethanyG for the Julia track on Exercism.",

"source_url": "https://github.com/exercism/julia/pull/413"

}

import java.util.ArrayList;

import java.util.List;

public class KillerSudokuHelper {

// Method to be called when no numbers are to be excluded.

public List<List<Integer>> combinationsInCage(Integer cageSum, Integer cageSize) {

// Call the main method with an empty exclude list.

return combinationsInCage(cageSum, cageSize, new ArrayList<>());

}

// Main method that includes to exclude list in the parameters.

public List<List<Integer>> combinationsInCage(Integer cageSum, Integer cageSize, List<Integer> exclude) {

// The range of valid numbers for a standard Sudoku puzzle.

List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));

numbers.removeAll(exclude);

return findCombinations(numbers, cageSum, cageSize, 0, new ArrayList<>());

}

// Helper method to recursively find the combinations.

private List<List<Integer>> findCombinations(List<Integer> numbers, Integer cageSum, Integer cageSize,

Integer start,

List<Integer> current) {

List<List<Integer>> results = new ArrayList<>();

if (cageSize == 0) {

// Base case: if the current combination sums up to the cage sum, add it to the results.

if (sum(current) == cageSum) {

results.add(new ArrayList<>(current));

}

return results;

}

for (int i = start; i < numbers.size(); i++) {

// Choose the number at the current position.

current.add(numbers.get(i));

// Explore further with the chosen number.

results.addAll(findCombinations(numbers, cageSum, cageSize - 1, i + 1, current));

// Un-choose the number for backtracking.

current.remove(current.size() - 1);

}

return results;

}

private int sum(List<Integer> list) {

int sum = 0;

for (int number : list) {

sum += number;

}

return sum;

}

}

[2aaa8f13-11b5-4054-b95c-a906e4d79fb6]

description = "Trivial 1-digit cages -> 1"

[4645da19-9fdd-4087-a910-a6ed66823563]

description = "Trivial 1-digit cages -> 2"

[07cfc704-f8aa-41b2-8f9a-cbefb674cb48]

description = "Trivial 1-digit cages -> 3"

[22b8b2ba-c4fd-40b3-b1bf-40aa5e7b5f24]

description = "Trivial 1-digit cages -> 4"

[b75d16e2-ff9b-464d-8578-71f73094cea7]

description = "Trivial 1-digit cages -> 5"

[bcbf5afc-4c89-4ff6-9357-07ab4d42788f]

description = "Trivial 1-digit cages -> 6"

[511b3bf8-186f-4e35-844f-c804d86f4a7a]

description = "Trivial 1-digit cages -> 7"

[bd09a60d-3aca-43bd-b6aa-6ccad01bedda]

description = "Trivial 1-digit cages -> 8"

[9b539f27-44ea-4ff8-bd3d-c7e136bee677]

description = "Trivial 1-digit cages -> 9"

[0a8b2078-b3a4-4dbd-be0d-b180f503d5c3]

description = "Cage with sum 45 contains all digits 1:9"

[2635d7c9-c716-4da1-84f1-c96e03900142]

description = "Cage with only 1 possible combination"

[a5bde743-e3a2-4a0c-8aac-e64fceea4228]

description = "Cage with several combinations"

[dfbf411c-737d-465a-a873-ca556360c274]

description = "Cage with several combinations that is restricted"

plugins {

id "java"

}

repositories {

mavenCentral()

}

dependencies {

testImplementation platform("org.junit:junit-bom:5.10.0")

testImplementation "org.junit.jupiter:junit-jupiter"

testImplementation "org.assertj:assertj-core:3.15.0"

}

test {

useJUnitPlatform()

testLogging {

exceptionFormat = "full"

showStandardStreams = true

events = ["passed", "failed", "skipped"]

}

}

import java.util.ArrayList;

import java.util.List;

public class KillerSudokuHelper {

List<List<Integer>> combinationsInCage(Integer cageSum, Integer cageSize, List<Integer> exclude) {

throw new UnsupportedOperationException("Delete this statement and write your own implementation.");

}

List<List<Integer>> combinationsInCage(Integer cageSum, Integer cageSize) {

throw new UnsupportedOperationException("Delete this statement and write your own implementation.");

}

}

import org.junit.jupiter.api.BeforeEach;

import org.junit.jupiter.api.Disabled;

import org.junit.jupiter.api.DisplayName;

import org.junit.jupiter.api.Test;

import java.util.List;

import static org.assertj.core.api.Assertions.assertThat;

public class KillerSudokuHelperTest {

private KillerSudokuHelper helper;

@BeforeEach

void setUp() {

helper = new KillerSudokuHelper();

}

@Test

@DisplayName("Trivial 1-digit cages -> 1 to 9")

public void testTrivialOneDigitCages() {

for (int n = 1; n <= 9; n++) {

List<List<Integer>> expected = List.of(List.of(n));

assertThat(helper.combinationsInCage(n, 1)).isEqualTo(expected);

}

}

@Test

@Disabled("Remove to run test")

@DisplayName("Cage with sum 45 contains all digits 1:9")

public void testCageWithSum45ContainsAllDigits() {

List<List<Integer>> expected = List.of(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));

assertThat(helper.combinationsInCage(45, 9)).isEqualTo(expected);

}

@Test

@Disabled("Remove to run test")

@DisplayName("Cage with only 1 possible combination")

public void testCageWithOnlyOnePossibleCombination() {

List<List<Integer>> expected = List.of(List.of(1, 2, 4));

assertThat(helper.combinationsInCage(7, 3)).isEqualTo(expected);

}

@Test

@Disabled("Remove to run test")

@DisplayName("Cage with several combinations")

public void testCageWithSeveralCombinations() {

List<List<Integer>> expected = List.of(

List.of(1, 9),

List.of(2, 8),

List.of(3, 7),

List.of(4, 6)

);

assertThat(helper.combinationsInCage(10, 2)).isEqualTo(expected);

}

@Test

@Disabled("Remove to run test")

@DisplayName("Cage with several combinations that is restricted")

public void testCageWithSeveralCombinationsThatIsRestricted() {

List<List<Integer>> expected = List.of(

List.of(2, 8),

List.of(3, 7)

);

assertThat(helper.combinationsInCage(10, 2, List.of(1, 4))).isEqualTo(expected);

}

}

include 'practice:killer-sudoku-helper'