Group the Numbers With the Same Sum Your task is, given a square grid of digits (0-9), output one of the ways that the digits can be grouped such that:


Each digit is part of exactly one group
All groups have the same number of digits
All groups are bounded by one polygon-like shape (this means that every digit in the group is next to [left, right, up, down] at least one other digit of the same group, unless each group has 1 element).
All groups have the same sum


The input grid will always be a square:
You may choose any input method you would like (including supplying arguments to a function or method). In addition, the input will supply the number of groups that your program should group the digits into.

Example input:

Suppose your input format is stringOfDigits numberOfGroups.

An example input would be:

156790809 3


which would translate to (a grid of sqrt(9) * sqrt(9))

1 5 6
7 9 0
8 0 9


which you would have to divide into 3 groups, each of which should have 9 / 3 = 3 elements with the same sum.

Output:
Output should be the string of digits, with optional spaces and newlines for formatting, with each digit followed by a letter a-z indicating its group. There should be exactly numberOfTotalDigits / numberOfGroups elements in each group. You will never have to divide something into more than 26 groups.

Example output:

1a 5a 6b
7c 9a 0b
8c 0c 9b


Note that replacing all as with bs and bs with as is equally valid. As long as each group is denoted by a distinct letter, the output is valid.

In addition, I expect most programs to output something along the lines of this, because newlines/spaces are optional:

1a5a6b7c9a0b8c0c9b


In this case, adding all digits of group a, b, or c makes 15. In addition, all groups are bound by some polygon.

Invalid outputs:

1a 5a 6b
7c 9a 0c
8c 0b 9b


because the groups do not form polygons (specifically, the 6b is isolated and 0c is also lonely).

1a 5a 6b
7c 9a 0b
8c 0b 9b


because the group b has 4 elements while c only has 2.

Etc.

If there is no valid solution, your program may do anything (i.e. stop, crash, run forever) but if your program prints None when there is no valid solution, -15 to your score.

If there is more than one solution, you only have to print one, but -20 if your program prints all of them separated by some delimiter.

This is code golf, so shortest code (with bonuses) wins!
Pyth, 122 - 20 - 15 = 87
=Z/lzQ=ks^lz.5Jm]dUzL[-bk+bk?tb%bkb?hb%hbkb)FNJIgNZB~Jm+NksmybN;|jbS{msm+@zk@S*Z&lt;GQxsdkUzfqSsTUz^fqsmv@*ZzbY/smvdzQJQ&quot;None

Changes:

130 -&gt; 120: Switched to newline separated input.

120 -&gt; 134: Fixed a bug involving groups not of size equal to the side length of the matrix.

134 -&gt; 120: Prints all solutions, including ones equivalent under group renaming.

120 -&gt; 122: Fixed a bug where only paths would be generated, instead of all legal groups.


Test run:
pyth programs/sum_group.pyth &lt;&lt;&lt; '156790809
3'
1a5a6b7c9a0b8c0c9b
1a5a6c7b9a0c8b0b9c
1b5b6a7c9b0a8c0c9a
1b5b6c7a9b0c8a0a9c
1c5c6a7b9c0a8b0b9a
1c5c6b7a9c0b8a0a9b


pyth programs/sum_group.pyth &lt;&lt;&lt; '156790808
3'
None

pyth programs/sum_group.pyth &lt;&lt;&lt; '1111     
2'
1a1a1b1b
1a1b1a1b
1b1a1b1a
1b1b1a1a

Explanation:
Pyth code           (Pseudo)-Python code              Comments

(implicit)          z = input()                       z is the digit string
(implicit)          Q = eval(input())                 S is the number of groups
(implicit)          G = 'abcdefghijklmnopqrstuvwxyz'
=Z/lzQ              Z = len(z)/Q                      Z is the size of each group.
=ks^lz.5            k = int(len(z) ** .5)             k is the side length of the matrix.
Jm]dUz              J = map(lambda d:[d], range(len(z))) Locations are encoded as numbers.
L                   def y(b): return                  y will be the transition function.
 [-bQ                         [b-k,                   Move up - the row above is k less.
  +bQ                          b+k,                   Move down - the row below is k more.
  ?tb%bkb                      b-1 if b%k else b      Move left, unless at the left edge.
  ?hb%hbkb)                    b+1 if (b+1)%k else b] Move right, unless at right edge.
FNJ                 for N in J:                       This constructs the list of all
   IgNZB                       if N[Z-1]: break       Z-length connected groups.
   ~Jm+Nk                      J+=map(lambda k: N+[k],  Append to J the group of N +
      smybN                          sum(map(lambda b:  anything reachable from
                                     y(b),N)))        anywhere in N.
   ;                (end for)
|                   or                                Print first truthy thing between
 S{                 sorted(set(                       Unique elements in sorted order of
   ms               map(lambda b:sum(                 Map+sum over allowable combinations
     m+@zd          map(lambda d:z[d]+                Character in original digit string
       @S*Z&lt;GQ      sorted(G[:Q]*Z)[                  Repeated and sorted early alphabet
        xsbd        sum(b).index(d)],                 At index of number in sum of groups
      Uz                range(len(z)))                Over possible indexes.
   f                filter(lambda T:                  To generate allowable combinations, 
                                                      we will filter all groups of Q paths.
    qSsTUz          sorted(sum(T)) == range(len(z))   Ensure all locations are visited.
    ^                                                 Combinations of
     f              filter(lambda Y:                  Filter over connected Z-length groups
      qsm           equal(sum(map(lambda k:           Sum of the values of the group
         v@*ZzkY    eval((z*Z)[k]),Y)                 In the original digit string
       /smvbzQ      sum(map(lambda b:eval(b),z))/Q    must equal the sum of all values in z
                                                      divided by the number of groups.
      J             J                                 Filter over connected Z-length groups
     Q              Q                                 Combinations of length Q
 &quot;None              &quot;None&quot;                            If the above was empty, print &quot;None&quot;