Killer Sudoku Helper
List every way a killer sudoku cage can be filled: the sets of different digits 1 to 9, of the cage’s size, that add up to its sum, leaving out digits already used.
Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.
// FILE: killer_sudoku_helper.nomi
//# The digit combinations a killer sudoku cage of a given size and sum can
//# hold.
/// Every set of `size` different digits from 1 to 9, none of them in
/// `exclude`, that adds up to `sum`. Each combination is in increasing order,
/// and the combinations are in lexicographic order.
//! assert combinations(10, 2, exclude: [1, 4]) == [[2, 8], [3, 7]]
//
pub fn combinations(sum: Int, size: Int, exclude: List<Int> = []) -> List<List<Int>>
1..=9
|> Iter.reject(&(&1 in exclude))
|> Iter.combinations(size)
|> Iter.filter(fn combination -> Iter.sum(combination) == sum)
|> Iter.to_list()
end
// FILE: killer_sudoku_helper_test.nomi
import killer_sudoku_helper.combinations
test "Trivial 1-digit cages"
subtests 1..=9, digit
assert combinations(digit, 1) == [[digit]]
end
end
test "Cage with sum 45 contains all digits 1:9"
assert combinations(45, 9) == [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
end
test "Cage with only 1 possible combination"
assert combinations(7, 3) == [[1, 2, 4]]
end
test "Cage with several combinations"
assert combinations(10, 2) == [[1, 9], [2, 8], [3, 7], [4, 6]]
end
test "Cage with several combinations that is restricted"
assert combinations(10, 2, exclude: [1, 4]) == [[2, 8], [3, 7]]
endok Trivial 1-digit cages (9 cases)
ok Cage with sum 45 contains all digits 1:9
ok Cage with only 1 possible combination
ok Cage with several combinations
ok Cage with several combinations that is restricted
test result: ok. 13 passed, 0 failed
How it’s written
Section titled “How it’s written”combinations(sum, size, exclude:)takes the excluded digits as a parameter that defaults to[], since most canonical cases exclude none. It filters them out of1..=9, takes every choice ofsizeof the rest withIter.combinations, and keeps those that add up tosum.Iter.combinationskeeps the source’s order and walks the choices in lexicographic order of position, so from increasing digits each combination is increasing and the list is in lexicographic order, the order the canonical data writes, with no sort. Nine digits give at most 126 choices, so checking each sum costs nothing worth pruning.- The nine one-digit cages are one
subtestsover1..=9. The canonical data names each case by its digit, and a row renders as its digit, so the rows need no description column. The four other cases are plain tests.