Kakuro Combinations

Question

Kakuro Combinations

Because I can't do mental arithmetic, I often struggle with the Kakuro Puzzle, which requires the victim to repeatedly work out which distinct numbers in the range 1 to 9 (inclusive) sum to another number in range 1 to 45 when you know how many numbers there are. For example, if you may want to know how to get 23 from 3 numbers, the only answer is 6 + 8 + 9. (This is the same idea as Killer Sudoku if you are familiar with that).

Sometimes you will have other information, such as that the number 1 cannot be present, thus to achieve 8 in just 2 numbers, you can only use 2 + 6 and 3 + 5 (you can't use 4 + 4, because they are not distinct). Alternatively, it may be that you have already found a 3 in the solution, and so something like 19 in 3 numbers must be 3 + 7 + 9.

Your task is to write a program that lists all the possible solutions to a given problem, in a strict order, in a strict layout.

Input

Your solution can receive the inputs as a single ASCII string either through stdin, a command line argument, an argument to a function, a value left on the stack, or whatever madness your favourite esoteric language employs. The string is in the form

number_to_achieve number_of_numbers_required list_of_rejected_numbers list_of_required_numbers

The first 2 arguments are typical base-10 non-negative non-zero integers in the ranges 1 to 45 and 1 to 9 respectively (using a decimal point would be invalid input), the two lists are just digits strung together with no delimitation in no particular order without repetition, or '0' if they are empty lists. There can be no shared digits between the lists (except for 0). The delimiters are single spaces.

Output

Your output must start with a line that contains the number of possible solutions. Your program must print out line-break delimited solutions sorted by each increasingly significant digit, where each digit is placed at the position it would be if you listed the numbers from 1 to 9. The examples below will hopefully make this clearer.

If an invalid input is provided I do not care what your program does, though I'd rather it didn't zero my boot sector.

Examples

For this example input

19 3 0 0

The expected output would be

Note the spaces in place of each "missing" number, these are required; I'm not bothered about spaces which don't have a number after them (such as the missing 9s above). You can assume that whatever you are printing to will use a mono-space font. Note also the ordering, whereby solutions with a smaller smallest digit are listed first, and then those with a smallest next smallest digit, etc.

Another example, based on that above

19 3 57 9

The expected output would be

2
 2     89
   4 6  9

Note that every result contains a 9, and no result contains a 5 or 7.

If there are no solutions, for example

20 2 0 0

Then you should just output a single line with a 0 on it.

I've intentionally made the parsing of the input part of the fun of this question. This is code-golf, may the shortest solution win.

\$\begingroup\$ +1 esp. for "... I'd rather it didn't zero my boot sector." \$\endgroup\$
– Michael Easter
Aug 2, 2014 at 2:15 — Michael Easter, Aug 2, 2014 at 2:15

Community · Accepted Answer · 2020-06-17 09:04:33Z

JavaScript (E6) 172 180 275 296

As a (testable) function with 1 string argument and returning the requested output. To have a real output change return with alert(), same byte count, but beware, the alert font is not monospace.

F=i=>{
  [t,d,f,m]=i.split(' ');
  for(l=0,r='',k=512;--k;!z&!h&!o&&(++l,r+=n))
    for(z=n='\n',h=d,o=t,b=i=1;i<=9;b+=b)
      z-=~(b&k?(--h,o-=i,n+=i,f):(n+=' ',m)).search(i++);
  return l+r
}

Test In FireFox or FireBug console

console.log(['19 3 0 0','19 3 57 9','19 3 57 4','20 2 0 0'].map(x=>'\n'+x+'\n' +F(x)).join('\n'))

Test output:

Ungolfed

F=i=>{
  [target, digits, forbidden, mandatory]=i.split(' ')
  
  result = '', nsol=0
  for (mask = 0b1000000000; --mask > 0;)
  {
    cdigits = digits
    ctarget = target
    bit = 1
    numbers = ''
    for (digit = 9; digit > 0; bit += bit, digit--)
    {
      
      if (bit & mask)
      {
        if (forbidden.search(digit)>=0) break;
        cdigits--;
        ctarget -= digit;
        numbers = digit + numbers;
      }
      else
      {
        if (mandatory.search(digit)>=0) break;
        numbers = ' '+numbers;
      }
    }
    if (ctarget==0 && cdigits == 0)
    {
        result += '\n'+numbers
        nsol++
    }
  }
  return nsol + result
}

Community · Accepted Answer · 2020-06-17 09:04:33Z

GolfScript, 88 characters

~[[]]10,:T{{1$+}+%}/\{\0+`-!}+,\{0`+\`&!}+,\{\,=}+,\{\{+}*=}+,.,n@{1T>''*T@-{`/' '*}/n}/

A straight-forward implementation in GolfScript. Takes input from STDIN or stack.

The code can be tested here.

Code with some comments:

### evaluate the input string
~                     

### build all possible combinations of 0...9
[[]]              # start with set of empty combination
10,:T             #
{                 # for 0..9
  {1$+}+%         #   copy each item of set and append current digit to this copy
}/                # end for

### only keep combination which the digits given as last argument (minus 0)
\{                # start of filter block
  \0+`            #   add zero to combination and make string out of it
  -!              #   subtract from last argument -> check argument contains any
                  #     excess characters
}+,               # end of filter block


### remove any combination which contains either 0 or any digit from 2nd last argument
\{                # start of filter block
  0`+             #   take argument and append 0
  \`              #   stringify combination
  &!              #   check if no characters are common
}+,               # end of filter block

### filter for correct length
\{                # start of filter block
  \,              #   calc length of combination
  =               #   check if equal to second argument
}+,               # end of filter block

### filter for correct sum
\{                # start of filter block
  \{+}*           #   sum all digits of combination
  =               #   compare with first argument
}+,               # end of filter block

### output
.,                # determine size of set
n                 # append newline
@{                # for each combination in set
  1T>''*          #   generate "123456789"
  T@-             #   generate anti-set of current combination  
  {`/' '*}/       #   replace (in the string) each digit within the 
                  #   anti-combination with a space characters
  n               #   append newline
}/                # end for

Martin Ender · Accepted Answer · 2014-08-01 21:24:11Z

Mathematica, 239 bytes

(I admit I started working on this while it was still in the sandbox.)

{t,n,a,b}=FromDigits/@StringSplit@i;Riffle[c=Cases[Union/@IntegerPartitions[t,n,Complement[r=Range@9,(d=IntegerDigits)@a]],k_/;(l=Length)@k==n&&(b==0||l[k⋂d@b]>0)];{(s=ToString)@l@c}~Join~((m=#;If[m~MemberQ~#,s@#," "]&/@r)&/@c),"\n"]<>""

Ungolfed

{t, n, a, b} = FromDigits /@ StringSplit@i;
Riffle[
  c = Cases[
    Union /@ IntegerPartitions[
      t, n, Complement[r = Range@9, (d = IntegerDigits)@a
       ]
      ],
    k_ /; (l = Length)@k == 
       n && (b == 0 || l[k ⋂ d@b] > 0)
    ];
  {(s = ToString)@l@c}~
   Join~((m = #; If[m~MemberQ~#, s@#, " "] & /@ r) & /@ c),
  "\n"] <> ""

It expects the input string to be stored in i.

It's fairly straightforward. First, input parsing. Then I use IntegerPartitions to figure out how I can split up the first number into the allowed numbers. Then I filter out all partitions that use duplicates or don't contain required numbers. And then for each solution I create a list from 1 to 9 and convert the present numbers into their string representation and the others into spaces. And then I concatenate everything.

Michael Easter · Accepted Answer · 2014-08-02 16:53:24Z

Groovy - 494 chars

Large, uninspired answer, but it uses Google Guava to generate the "power set".

Golfed:

@Grab(group='com.google.guava', module='guava', version='17.0')
m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])
j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}
d=1..9 as Set<Integer>
t=[]
com.google.common.collect.Sets.powerSet(d).each{x->
if(x.sum()==n&&x.size()==r&&x.disjoint(j)&&x.containsAll(q)) {
s="";for(i in 0..8){if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}};t<<s}
}
p={println it}
p t.size()
t.sort().reverse().each{p it}

Sample runs:

$ groovy K.groovy 19 3 0 0 
5
 2     89
  3   7 9
   4 6  9
   4  78 
    56 8 
$ groovy K.groovy 19 3 5 0 
4
 2     89
  3   7 9
   4 6  9
   4  78 
$ groovy K.groovy 19 3 5 9
3
 2     89
  3   7 9
   4 6  9
$ groovy K.groovy 20 2 0 0 
0

Ungolfed:

@Grab(group='com.google.guava', module='guava', version='17.0')

m=(args.join(" ")=~/(\d+) (\d+) (\d+) (\d+)/)[0]
i={it as int}
n=i(m[1])
r=i(m[2])

j=[]
m[3].each{if(i(it))j<<i(it)}
q=[]
m[4].each{if(i(it))q<<i(it)}

d=1..9 as Set<Integer>
t=[]

com.google.common.collect.Sets.powerSet(d).each{ x ->
    if(x.sum()==n && x.size()==r && x.disjoint(j) && x.containsAll(q)) {
        s=""
        for(i in 0..8) {
            if(x.contains(i+1)){s+=(i+1) as String}else{s+=" "}
        }
        t<<s
    }
}

p={println it}
p t.size()
t.sort().reverse().each{p it}

Stack Exchange Network

Kakuro Combinations