“Fill the Grid” Problem

Question

A challenge with simple rules but non-trivial algorithms. :-)

Task

Take input in the form of space-separated integers:

N A B S

Where N is the side length of a 2D square matrix filled with unique numbers (integers) between A and B inclusive. For each row and column in this matrix, the sum is always the same: S. (In other words, the matrix is a semi-magic square).

Note:

All numbers are positive. Exception is A, which can be 0.

Examples

For

3 1 10000 2015

a valid solution would be

For

8 1 300 500

a valid solution would be

Output

You output should be an ASCII table. Example for the first example above:

 384  159 1472
1174  499  342
 457 1357  201

Right-aligned integers padded by spaces. The width of each column is the width of the largest integer in that column.

Scoring

This is code-golf, so shortest code in bytes wins. Standard loopholes apply (especially about built-ins to solve this problem). You don't have to care about wrong or otherwise impossible inputs (including negative numbers). Please provide a sample output in your answer (mandatory) for the second example above.

Answer 1

CJam, 119 91 bytes

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?

This is a provably correct, non-deterministic approach.

On my desktop, the second test case generally finishes in less than 10 minutes.

The first case finishes instantly. Try it online in the CJam interpreter.

Sample run

$ cjam grid.cjam <<< '8 1 300 500'
77  66  37 47  56  46 86  85
63 102  70 72  49  54 81   9
62  69  58 57  71  17 48 118
64  65  67 87  53  44 80  40
73  60  55 89  51  76 84  12
68  59  28 78  74  38 50 105
61  75  52 43 125  83 42  19
32   4 133 27  21 142 29 112

Idea

Without time limits, we could just randomly generate squares until finding a valid square. This approach builds on that idea, adding two optimizations:

• Instead of pseudo-randomly generating square of side length N, we generate squares of side length N-1, add one column to form a N × (N-1) rectangle whose rows have sum S, then one row to form a square of side length N whose columns have sum S.

  Since the sum of the elements of all columns will be NS and the sum of the elements of the first N-1 rows is (N-1)S, the last row will also have sum S.

  However, this process may generate an invalid matrix, since there's no guarantee that all elements of the last row and column will be unique or fall in the range [A ... B].

• Picking a square of unique integers in [A ... B] and side length N-1 uniformly at random would take way too long. We somehow have to prioritize squares that have a higher chance of resulting in a valid square of side length N after applying the process detailed in the previous bullet point.

  Given that each row and column has to have a sum of S, its elements have an average of S/N. Thus, picking more elements close to that average should increase our chances.

  For each I in [A ... B], we pseudo-randomly pick a float between 0 and (I - S/N)² + 1 and sort the elements of [A ... B] by the picked floats. We keep the first N² numbers and place them in reading order in a square.

  Assuming a perfectly uniform distribution of all real numbers between 0 and (I - S/N)² + 1 in each step, all squares have a non-zero probability of being picked, meaning that the process will finish eventually.

Code

q~          e# Read all input from STDIN and evaluate it.
:M;         e# Save "S" in M and discard it from the stack.
),>:R;      e# Transform "A B" into [A ... B], save in R and discard.
(:L         e# Save "N - 1" in L and keep it on the stack.
{           e# If L is non-zero:
  {         e#   Do:
    R{      e#     For each I in R:
      ML)d/ e#       Compute M/Double(L+1).
      -Y#   e#       Subtract the result from I and square the difference.
      )mr   e#       Add 1 and pick a non-negative Double below the result.
    }$      e#     Sort the values of I according to the picks.
    L/      e#     Split the shuffled R into chunks of length L.
    L<      e#     Keep only the first L chunks.
    2{      e#     Do twice:
      {     e#       For each row of the  L x L array.
        M1$ e#       Push M and a copy of the row.
        :+- e#       Add the integers of the row and subtract their sum from M.
        +   e#       Append the difference to the row.
      }%    e#
      z     e#       Transpose rows and columns.
    }*      e#
    :U:+    e#     Save the result in U and concatenate its rows.
    __O|    e#     Push two copies. Deduplicate the second copy.
    =R*     e#     Push R if all elements are unique, an empty array otherwise.
    -       e#     Remove the result's elements from U's elements.
  }g        e#   If the resulting array is non-empty, repeat the loop.
  U{        e#   For each row in U:
    :s      e#     Convert its integers into strings.
    _:,     e#     Copy and replace each string with its length.
    :e>     e#     Compute the maximum length.
    f{      e#     For each integer, push the maximum length; then
      Se[   e#       Left-pad the integer with spaces to that length.
    }       e#
  }%        e#
  z         e#   Transpose rows with columns.
  Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.

Answer 2

Jelly, 19 18 bytes

S;§f⁵
r/œ!²}s€ÇÞṪG

Try it online!

Takes input via the command-line in the form A, B N S. Outputs the lexicographic ally first grid that fits

-1 byte thanks to Jonathan Allan!

On the one hand, it's short. On the other hand, it's incredibly inefficient. This generates

$$\frac {(B-A+1)!} {(B-A-N^2+1)!}$$

\$N\times N\$ squares to check. For example, if \$A = 1, B = 9, N = 3\$ (the example in TIO), this generates \$362880\$ \$3\times3\$ matrices to check are semi-magic. For the second test case, it generates 243427020732724848691170301000009788596908895057539171134817782742659530443034291592046861179091424965386457564096330026488754281163364761600000000000000000 \$8\times8\$ matrices.

Given enough time and memory, this would work on any input. However, on my computer, it runs out of memory for the second test case after 5 minutes

How it works

S;§f⁵ - Helper link. Takes a matrix M and outputs if it's semi-magic to S
S     - Column sums of M
  §   - Row sums of M
 ;    - Concatenate
   f⁵ - Keep only S

r/œ!²}s€ÇÞṪG - Main link. Takes [A, B] on the left and N on the right
r/           - Reduce [A, B] by range, yielding [A, A+1, ..., B-1, B]
     }       - To N:
    ²        -   Square
  œ!         - Generate all permutations of range(A, B) of length N²
       €     - Over each:
      s      -   Slice into NxN matrices
        ÇÞ   - Sort the matrices by the helper link
          ṪG - Take the last and format as a grid