Skip to content

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]]
end
  • combinations(sum, size, exclude:) takes the excluded digits as a parameter that defaults to [], since most canonical cases exclude none. It filters them out of 1..=9, takes every choice of size of the rest with Iter.combinations, and keeps those that add up to sum.
  • Iter.combinations keeps 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 subtests over 1..=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.