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)2 + 1 and sort the elements of [A ... B] by the picked floats. We keep the first N2 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)2 + 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.
1Are we allowed to generate random numbers between A and B until they sum correctly and are unique? – lirtosiast – 2015-10-01T19:53:02.003
Just to check,
A
,B
, andN
can be negative? – xnor – 2015-10-01T19:54:06.677@xnor No. That would be an invalid input and as I said, you don't have to care about invalid inputs. – mınxomaτ – 2015-10-01T19:54:49.650
@minxomat You should clarify then, you say "integers", which includes negatives. – xnor – 2015-10-01T19:55:21.980
@ThomasKwa If that is the best solution you can come up with, sure. (Lame! :P) – mınxomaτ – 2015-10-01T19:55:29.617
@minxomat What about 0 inputs? Are those valid? – xnor – 2015-10-01T19:58:08.217
@xnor Added a clarification in the header. – mınxomaτ – 2015-10-01T20:01:21.000
2minxomat, I'm not saying it's the best solution I can come up with, I'm saying it may be the shortest possible. – lirtosiast – 2015-10-01T20:02:59.427
@ThomasKwa Yes, it would technically win. But clever answers are usually more popular than easy answers :) – mınxomaτ – 2015-10-01T20:36:20.823
A simple random algorithm would find the solution in a finite (albeit very large) time almost surely. This should probably be ruled out explicitly in the challenge
– Luis Mendo – 2015-10-02T00:12:23.3433@LuisMendo You have to generate a sample output according to the task. If you can manage this within your lifetime with a brute-force approach, I'd be impressed. :-). I could rule it out, but it would be too fuzzy, since the most popular solution (which is GA) still involves randomness. Also I don't want to change the rules when someone might work on a solution already. – mınxomaτ – 2015-10-02T00:15:05.490
1@minxomat All your three arguments are very good points :-) – Luis Mendo – 2015-10-02T00:17:24.273