When solving Kakuro it is essential to know for a given integer X and a given number of elements N all the combinations of N non-repeating digits [1-9] that their sum equals to X.
For example, there is only one combination for creating the number 7 from 3 elements:
1+2+4
And there are 6 combinations for creating the number 15 from 4 elements:
1+2+3+9 1+2+4+8 1+2+5+7 1+3+4+7 1+3+5+6 2+3+4+6
Let’s generate a list of all the possible Xs and Ns, using SQL of course.
What makes it really easy is the not-so-popular SQL function POWERMULTISET (available since Oracle 10g).
It is a collection function that gets a nested table and returns a collection of collections containing all nonempty subsets of the input collection.
create type integer_ntt as table of integer
/
break on x on num_of_elements skip 1
select sum(b.column_value) x,
a.num_of_elements,
listagg(b.column_value,'+') within group(order by b.column_value) expr
from (select rownum id,
column_value combination,
cardinality(column_value) num_of_elements
from table(powermultiset(integer_ntt(1,2,3,4,5,6,7,8,9)))) a,
table(a.combination) b
where a.num_of_elements > 1
group by a.id,a.num_of_elements
order by x,num_of_elements,expr;
X NUM_OF_ELEMENTS EXPR
---------- --------------- --------------------
3 2 1+2
4 2 1+3
5 2 1+4
2+3
6 2 1+5
2+4
3 1+2+3
7 2 1+6
2+5
3+4
3 1+2+4
.
.
.
15 2 6+9
7+8
3 1+5+9
1+6+8
2+4+9
2+5+8
2+6+7
3+4+8
3+5+7
4+5+6
4 1+2+3+9
1+2+4+8
1+2+5+7
1+3+4+7
1+3+5+6
2+3+4+6
5 1+2+3+4+5
.
.
.
42 7 3+4+5+6+7+8+9
8 1+2+4+5+6+7+8+9
43 8 1+3+4+5+6+7+8+9
44 8 2+3+4+5+6+7+8+9
45 9 1+2+3+4+5+6+7+8+9
502 rows selected.
We can get a more user-friendly output by pivoting the results into a matrix, where one axis is X, the second axis is N, and each cell contains all the combinations for this X|N pair.
This can be done easily using the PIVOT operator (available since Oracle 11g):
break on x skip 1
col 2 format a4
col 3 format a6
col 4 format a8
col 5 format a10
col 6 format a12
col 7 format a14
col 8 format a16
col 9 format a18
select *
from (select sum(b.column_value) x,
a.num_of_elements,
listagg(b.column_value, '+') within group(order by b.column_value) expr
from (select rownum id,
column_value combination,
cardinality(column_value) num_of_elements
from table(powermultiset(integer_ntt(1,2,3,4,5,6,7,8,9)))) a,
table(a.combination) b
where a.num_of_elements > 1
group by a.id,
a.num_of_elements)
pivot (listagg(expr, chr(10)) within group (order by expr)
for num_of_elements in(2,3,4,5,6,7,8,9));
X 2 3 4 5 6 7 8 9
---------- ---- ------ -------- ---------- ------------ -------------- ---------------- ------------------
3 1+2
4 1+3
5 1+4
2+3
6 1+5 1+2+3
2+4
7 1+6 1+2+4
2+5
3+4
8 1+7 1+2+5
2+6 1+3+4
3+5
9 1+8 1+2+6
2+7 1+3+5
3+6 2+3+4
4+5
10 1+9 1+2+7 1+2+3+4
2+8 1+3+6
3+7 1+4+5
4+6 2+3+5
11 2+9 1+2+8 1+2+3+5
3+8 1+3+7
4+7 1+4+6
5+6 2+3+6
2+4+5
12 3+9 1+2+9 1+2+3+6
4+8 1+3+8 1+2+4+5
5+7 1+4+7
1+5+6
2+3+7
2+4+6
3+4+5
13 4+9 1+3+9 1+2+3+7
5+8 1+4+8 1+2+4+6
6+7 1+5+7 1+3+4+5
2+3+8
2+4+7
2+5+6
3+4+6
14 5+9 1+4+9 1+2+3+8
6+8 1+5+8 1+2+4+7
1+6+7 1+2+5+6
2+3+9 1+3+4+6
2+4+8 2+3+4+5
2+5+7
3+4+7
3+5+6
15 6+9 1+5+9 1+2+3+9 1+2+3+4+5
7+8 1+6+8 1+2+4+8
2+4+9 1+2+5+7
2+5+8 1+3+4+7
2+6+7 1+3+5+6
3+4+8 2+3+4+6
3+5+7
4+5+6
16 7+9 1+6+9 1+2+4+9 1+2+3+4+6
1+7+8 1+2+5+8
2+5+9 1+2+6+7
2+6+8 1+3+4+8
3+4+9 1+3+5+7
3+5+8 1+4+5+6
3+6+7 2+3+4+7
4+5+7 2+3+5+6
17 8+9 1+7+9 1+2+5+9 1+2+3+4+7
2+6+9 1+2+6+8 1+2+3+5+6
2+7+8 1+3+4+9
3+5+9 1+3+5+8
3+6+8 1+3+6+7
4+5+8 1+4+5+7
4+6+7 2+3+4+8
2+3+5+7
2+4+5+6
18 1+8+9 1+2+6+9 1+2+3+4+8
2+7+9 1+2+7+8 1+2+3+5+7
3+6+9 1+3+5+9 1+2+4+5+6
3+7+8 1+3+6+8
4+5+9 1+4+5+8
4+6+8 1+4+6+7
5+6+7 2+3+4+9
2+3+5+8
2+3+6+7
2+4+5+7
3+4+5+6
19 2+8+9 1+2+7+9 1+2+3+4+9
3+7+9 1+3+6+9 1+2+3+5+8
4+6+9 1+3+7+8 1+2+3+6+7
4+7+8 1+4+5+9 1+2+4+5+7
5+6+8 1+4+6+8 1+3+4+5+6
1+5+6+7
2+3+5+9
2+3+6+8
2+4+5+8
2+4+6+7
3+4+5+7
20 3+8+9 1+2+8+9 1+2+3+5+9
4+7+9 1+3+7+9 1+2+3+6+8
5+6+9 1+4+6+9 1+2+4+5+8
5+7+8 1+4+7+8 1+2+4+6+7
1+5+6+8 1+3+4+5+7
2+3+6+9 2+3+4+5+6
2+3+7+8
2+4+5+9
2+4+6+8
2+5+6+7
3+4+5+8
3+4+6+7
21 4+8+9 1+3+8+9 1+2+3+6+9 1+2+3+4+5+6
5+7+9 1+4+7+9 1+2+3+7+8
6+7+8 1+5+6+9 1+2+4+5+9
1+5+7+8 1+2+4+6+8
2+3+7+9 1+2+5+6+7
2+4+6+9 1+3+4+5+8
2+4+7+8 1+3+4+6+7
2+5+6+8 2+3+4+5+7
3+4+5+9
3+4+6+8
3+5+6+7
22 5+8+9 1+4+8+9 1+2+3+7+9 1+2+3+4+5+7
6+7+9 1+5+7+9 1+2+4+6+9
1+6+7+8 1+2+4+7+8
2+3+8+9 1+2+5+6+8
2+4+7+9 1+3+4+5+9
2+5+6+9 1+3+4+6+8
2+5+7+8 1+3+5+6+7
3+4+6+9 2+3+4+5+8
3+4+7+8 2+3+4+6+7
3+5+6+8
4+5+6+7
23 6+8+9 1+5+8+9 1+2+3+8+9 1+2+3+4+5+8
1+6+7+9 1+2+4+7+9 1+2+3+4+6+7
2+4+8+9 1+2+5+6+9
2+5+7+9 1+2+5+7+8
2+6+7+8 1+3+4+6+9
3+4+7+9 1+3+4+7+8
3+5+6+9 1+3+5+6+8
3+5+7+8 1+4+5+6+7
4+5+6+8 2+3+4+5+9
2+3+4+6+8
2+3+5+6+7
24 7+8+9 1+6+8+9 1+2+4+8+9 1+2+3+4+5+9
2+5+8+9 1+2+5+7+9 1+2+3+4+6+8
2+6+7+9 1+2+6+7+8 1+2+3+5+6+7
3+4+8+9 1+3+4+7+9
3+5+7+9 1+3+5+6+9
3+6+7+8 1+3+5+7+8
4+5+6+9 1+4+5+6+8
4+5+7+8 2+3+4+6+9
2+3+4+7+8
2+3+5+6+8
2+4+5+6+7
25 1+7+8+9 1+2+5+8+9 1+2+3+4+6+9
2+6+8+9 1+2+6+7+9 1+2+3+4+7+8
3+5+8+9 1+3+4+8+9 1+2+3+5+6+8
3+6+7+9 1+3+5+7+9 1+2+4+5+6+7
4+5+7+9 1+3+6+7+8
4+6+7+8 1+4+5+6+9
1+4+5+7+8
2+3+4+7+9
2+3+5+6+9
2+3+5+7+8
2+4+5+6+8
3+4+5+6+7
26 2+7+8+9 1+2+6+8+9 1+2+3+4+7+9
3+6+8+9 1+3+5+8+9 1+2+3+5+6+9
4+5+8+9 1+3+6+7+9 1+2+3+5+7+8
4+6+7+9 1+4+5+7+9 1+2+4+5+6+8
5+6+7+8 1+4+6+7+8 1+3+4+5+6+7
2+3+4+8+9
2+3+5+7+9
2+3+6+7+8
2+4+5+6+9
2+4+5+7+8
3+4+5+6+8
27 3+7+8+9 1+2+7+8+9 1+2+3+4+8+9
4+6+8+9 1+3+6+8+9 1+2+3+5+7+9
5+6+7+9 1+4+5+8+9 1+2+3+6+7+8
1+4+6+7+9 1+2+4+5+6+9
1+5+6+7+8 1+2+4+5+7+8
2+3+5+8+9 1+3+4+5+6+8
2+3+6+7+9 2+3+4+5+6+7
2+4+5+7+9
2+4+6+7+8
3+4+5+6+9
3+4+5+7+8
28 4+7+8+9 1+3+7+8+9 1+2+3+5+8+9 1+2+3+4+5+6+7
5+6+8+9 1+4+6+8+9 1+2+3+6+7+9
1+5+6+7+9 1+2+4+5+7+9
2+3+6+8+9 1+2+4+6+7+8
2+4+5+8+9 1+3+4+5+6+9
2+4+6+7+9 1+3+4+5+7+8
2+5+6+7+8 2+3+4+5+6+8
3+4+5+7+9
3+4+6+7+8
29 5+7+8+9 1+4+7+8+9 1+2+3+6+8+9 1+2+3+4+5+6+8
1+5+6+8+9 1+2+4+5+8+9
2+3+7+8+9 1+2+4+6+7+9
2+4+6+8+9 1+2+5+6+7+8
2+5+6+7+9 1+3+4+5+7+9
3+4+5+8+9 1+3+4+6+7+8
3+4+6+7+9 2+3+4+5+6+9
3+5+6+7+8 2+3+4+5+7+8
30 6+7+8+9 1+5+7+8+9 1+2+3+7+8+9 1+2+3+4+5+6+9
2+4+7+8+9 1+2+4+6+8+9 1+2+3+4+5+7+8
2+5+6+8+9 1+2+5+6+7+9
3+4+6+8+9 1+3+4+5+8+9
3+5+6+7+9 1+3+4+6+7+9
4+5+6+7+8 1+3+5+6+7+8
2+3+4+5+7+9
2+3+4+6+7+8
31 1+6+7+8+9 1+2+4+7+8+9 1+2+3+4+5+7+9
2+5+7+8+9 1+2+5+6+8+9 1+2+3+4+6+7+8
3+4+7+8+9 1+3+4+6+8+9
3+5+6+8+9 1+3+5+6+7+9
4+5+6+7+9 1+4+5+6+7+8
2+3+4+5+8+9
2+3+4+6+7+9
2+3+5+6+7+8
32 2+6+7+8+9 1+2+5+7+8+9 1+2+3+4+5+8+9
3+5+7+8+9 1+3+4+7+8+9 1+2+3+4+6+7+9
4+5+6+8+9 1+3+5+6+8+9 1+2+3+5+6+7+8
1+4+5+6+7+9
2+3+4+6+8+9
2+3+5+6+7+9
2+4+5+6+7+8
33 3+6+7+8+9 1+2+6+7+8+9 1+2+3+4+6+8+9
4+5+7+8+9 1+3+5+7+8+9 1+2+3+5+6+7+9
1+4+5+6+8+9 1+2+4+5+6+7+8
2+3+4+7+8+9
2+3+5+6+8+9
2+4+5+6+7+9
3+4+5+6+7+8
34 4+6+7+8+9 1+3+6+7+8+9 1+2+3+4+7+8+9
1+4+5+7+8+9 1+2+3+5+6+8+9
2+3+5+7+8+9 1+2+4+5+6+7+9
2+4+5+6+8+9 1+3+4+5+6+7+8
3+4+5+6+7+9
35 5+6+7+8+9 1+4+6+7+8+9 1+2+3+5+7+8+9
2+3+6+7+8+9 1+2+4+5+6+8+9
2+4+5+7+8+9 1+3+4+5+6+7+9
3+4+5+6+8+9 2+3+4+5+6+7+8
36 1+5+6+7+8+9 1+2+3+6+7+8+9 1+2+3+4+5+6+7+8
2+4+6+7+8+9 1+2+4+5+7+8+9
3+4+5+7+8+9 1+3+4+5+6+8+9
2+3+4+5+6+7+9
37 2+5+6+7+8+9 1+2+4+6+7+8+9 1+2+3+4+5+6+7+9
3+4+6+7+8+9 1+3+4+5+7+8+9
2+3+4+5+6+8+9
38 3+5+6+7+8+9 1+2+5+6+7+8+9 1+2+3+4+5+6+8+9
1+3+4+6+7+8+9
2+3+4+5+7+8+9
39 4+5+6+7+8+9 1+3+5+6+7+8+9 1+2+3+4+5+7+8+9
2+3+4+6+7+8+9
40 1+4+5+6+7+8+9 1+2+3+4+6+7+8+9
2+3+5+6+7+8+9
41 2+4+5+6+7+8+9 1+2+3+5+6+7+8+9
42 3+4+5+6+7+8+9 1+2+4+5+6+7+8+9
43 1+3+4+5+6+7+8+9
44 2+3+4+5+6+7+8+9
45 1+2+3+4+5+6+7+8+9
43 rows selected.
That’s really quite cool Oren. I really enjoyed the talk at UKOUG Tech16 where you demonstrated this. I’d never come across powermultiset, thank you.
Thanks Martin 🙂