Kakuro Helper using SQL Query with PowerMultiSet and Pivot

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.

2 Comments

  1. 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.

    • Oren Nakdimon

      Thanks Martin :)

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>