Dear jbchh,
My solutions are below. I wrote the programs in C, but they also compile
under C++. I adhered to the ISO standard to ensure that they'll run on
any platform. In a Unix-compatible environment, you can compile them
with the following instructions.
gcc border_fill.c -o border
gcc diagonal_fill.c -o diagonal
To run the programs, execute the following.
./border 4
./diagonal 6
In addition to writing explanatory material below, I have added inline
comments to each program. If you have trouble compiling or executing
these programs, or if you have any concerns at all about my answer,
don't hesitate to let me know with a Clarification Request.
Regards,
leapinglizard
Q1.
Initial Question
With the upper left corner fixed at 0, there are 15! = 2,004,310,016
ways to fill a 4-by-4 matrix. Although it would not take unreasonably
long to run two billion iterations of a routine that fills the matrix
and checks its submatrix sums, we can significantly reduce the size of
the search space. We observe that if three cells a, b, c of a submatrix
have been chosen such that
a+b+c < T
for some required total T, the fourth cell d is decided by
a+b+c+d = T
d = T-a-b-c.
The program below exploits this fact by filling the right and bottom
borders of the 4-by-4 matrix. Once these cells have been set,
the remainder of the matrix is strictly decided by the submatrix
requirement. Our program only has to check whether the matrix values are
unique and drawn from the range [1, N^2-1] for an N-by-N matrix. If we
imagine that the right and bottom borders of the matrix form a reversed
letter L --
. . . x
. . . x
. . . x
x x x x
-- then we first check the cell in the crook of the L.
. . . x
. . . x
. . X x
x x x x
If its value is unique and in the proper range, we check the cells to
the left. Once the row is complete, we move to the next row above.
. . . x
. . . x
x x x x
x x x x
The number of configurations we have to check is just the number of ways
there are to fill the right and bottom borders of a 4-by-4 matrix. Since
the four corners of the matrix constitute a 2-by-2 submatrix and the
top left corner is already 0, the remaining three corners must add up to
30. There are 19 combinations of unique integers in the range [1, 15] that
sum to 30, and 6 ways to order these combinations, for a total of 6*19 =
114 permutations. Once the corners have been set, two cells remain along
each border. Using the remaining 16-4 = 12 numbers, we can fill these in
12*11*10*9 = 11,880
ways, for a grand total of
114*11,880 = 1,354,320
configurations.
The only backtracking we have to do in our program is in the course of
selecting these 1.5 million border configurations, which is accomplished
by the depth-first recursive functions bottom() and right(). Once
a configuration has been found, the remaining values are verified
deterministically by the fill() function, which returns early if it finds
an invalid cell. Upon running our program, we learn that the number of
balanced 4-by-4 matrices with one fixed cell is 1272.
/*-------------------begin border_fill.c */
#include<stdlib.h>
#include<stdio.h>
int msg(char *s, int code) { /* error-message helper */
printf("%s\n", s);
return code;
}
int **mm, n, sum, max, *used, *stack, ix, fail;
int clear(int top) { /* resets used numbers */
while (top >= 0)
used[stack[top--]] = 0;
return 0;
}
int fill() { /* fills from bottom right corner */
int r, c, t, top = -1;
for (r = n-2; r > 0; r--) { /* assume bottom border is done */
for (c = n-2; c >= 0; c--) { /* assume right border is done */
t = sum - mm[r][c+1] - mm[r+1][c+1] - mm[r+1][c];
if (t < 0 || t > max || used[t])
return clear(top); /* attempt to form desired sum */
used[stack[++top] = mm[r][c] = t] = 1;
}
if (mm[r][0] + mm[r+1][0] + mm[r+1][n-1] + mm[r][n-1] != sum)
return clear(top); /* check backward at front of row */
}
if (mm[1][0] + mm[0][0] + mm[0][n-1] + mm[1][n-1] != sum)
return clear(top); /* in second row, check upward too */
for (c = n-2; c > 0; c--) { /* check top row */
t = sum - mm[0][c+1] - mm[1][c+1] - mm[1][c];
if (t < 0 || t > max || used[t])
return clear(top); /* attempt to form sum */
if (t + mm[0][c+1] + mm[n-1][c+1] + mm[n-1][c] != sum)
return clear(top); /* check upward */
used[stack[++top] = mm[0][c] = t] = 1;
}
if (sum-mm[0][1] != mm[0][0]+mm[1][0]+mm[1][1])
return clear(top); /* check backward and down */
if (sum-mm[0][1] != mm[0][0]+mm[n-1][0]+mm[n-1][1])
return clear(top); /* check backward and up */
ix++; /* if all is well, increment counter */
/* uncomment this block for silent enumeration
if (ix % 100 == 0)
printf("%d\n", ix);
return 0;
*/
printf("\n%5d. ", ix); /* print solution number */
for (c = 0; c < n; c++) /* display top row */
printf(" %2d", mm[0][c]);
printf("\n");
for (r = 1; r < n; r++) { /* display remaining rows */
printf(" ");
for (c = 0; c < n; c++)
printf(" %2d", mm[r][c]);
printf("\n");
}
return clear(top);
}
int right(int r) { /* fill right border */
int i;
if (r == n-1)
return fill();
for (i = 1; i <= max; i++) /* avoid top and bottom corners */
if (!used[i]) {
used[mm[r][n-1] = i] = 1;
right(r+1);
used[i] = 0;
}
return 0;
}
int bottom(int c) { /* fill bottom border */
int i;
if (c == n-1)
return right(1);
for (i = 1; i <= max; i++) /* avoid left and right corners */
if (!used[i]) {
used[mm[n-1][c] = i] = 1;
bottom(c+1);
used[i] = 0;
}
return 0;
}
int main(int argc, char *argv[]) {
int i, j, k;
if (argc != 2) /* must pass exactly one argument */
return msg("please specify N for an N-by-N matrix", 0);
n = atoi(argv[1]);
if (n%2 != 0 || n < 2 || n > 4) /* check for manageable size */
return msg("N must be an even number between 2 and 4, inclusive", 0);
mm = (int **) calloc(n, sizeof(int *));
for (i = 0; i < n; i++) /* allocate matrix */
mm[i] = (int *) calloc(n, sizeof(int));
ix = 0;
max = n*n-1; /* allocate stack and flag array */
stack = (int *) calloc(max, sizeof(int));
used = (int *) calloc(max, sizeof(int));
used[mm[0][0] = 0] = 1; /* set upper left corner to 0 */
sum = 2*n*n - 2;
printf("looking for %d-by-%d matrices with submatrix sums == %d\n",n,n,sum);
for (i = 1; i <= max; i++)
for (j = 1; j <= max; j++) { /* try two corner values */
if (i == j)
continue; /* compute the third corner */
if ((k = sum-i-j) <= 0 || k > max || k == i || k == j)
continue; /* check for valid range */
used[mm[0][n-1] = i] = 1; /* if sum is good, set corners */
used[mm[n-1][n-1] = j] = 1;
used[mm[n-1][0] = k] = 1;
bottom(1); /* start filling at bottom border */
used[i] = used[j] = used[k] = 0;
}
printf("found %d matrices\n", ix);
return 0;
}
/*-------------------end border_fill.c */
More Challenging Question
The 6-by-6 case does not use the same submatrix sum as the 4-by-4. We
can generalize the calculation of the 2-by-2 submatrix sum as follows. In
an N-by-N matrix, the N^2 values
0, 1, ..., N^2 - 2, N^2 - 1
have the sum
N^2 N^4 - N^2
--- * (N^2 - 1) = --------- .
2 2
The number of 2-by-2 submatrices is
N^2
(N/2)^2 = --- .
4
If the matrix is balanced, then each submatrix sum has the value of the
total matrix sum divided by the number of submatrices:
N^4 - N^2 4 N^2 - 1 2
--------- * --- = ------- * - = 2N^2 - 2 .
2 N^2 1 1
We confirm that for N = 4, this value is
2*4*4 - 2 = 32 - 2 = 30,
and for N = 6, the submatrix sums in a balanced matrix must be
2*6*6 - 2 = 72 - 2 = 70.
The program described above takes less than a second to find all balanced
4-by-4 matrices with one fixed cell, but it is far too slow to look for
balanced 6-by-6 matrices. Indeed, we have not had the patience to wait
for it to produce a single such matrix. To see why this is so, consider
the number of ways there are to choose the bottom and left borders of a
6-by-6 matrix. Once the corners have been set, four empty cells remain
along each border. Using the remaining 36-4 = 32 numbers, there are
32*31*30*29*28*27*26*25 = 424,097,856,000
ways to fill these. And that's without considering the permutations of
three corner values summing to 70, of which there are 612, for a total of
612 * 424,097,856,000 = 259,547,887,872,000
ways to fill the right and bottom borders. Valid configurations are
rather sparse in this space, leaving many iterations between each
balanced matrix.
To write a program that can solve the 6-by-6 case in reasonable time,
we used a depth-first recursion that mitigates backtracking by filling
the matrix in a more efficient order. As before, we rely on the fact
that deciding three cells of a submatrix decides the fourth. Instead
of blindly choosing values for the right and bottom borders, however,
we fill the matrix in diagonal stripes. The longest such diagonal runs
from the bottom left corner to the top right, consisting of exactly 6
cells. The remaining diagonals run parallel to it.
We start filling diagonals at the top left and proceeed toward the bottom
right. Since the top left corner is fixed at 0, we begin by choosing
two unique values in the range [1, 35].
x X . . . .
X . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
These choices decide the value of the fourth cell in the top left
submatrix. If it is not among the previously used numbers, we can set
it and proceed to the next diagonal.
x x . . . .
x X . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
After choosing a value for the leftmost cell in this diagonal, we have
obtained three values of a submatrix, thereby deciding the fourth.`
x x . . . .
x x . . . .
X X . . . .
. . . . . .
. . . . . .
. . . . . .
The middle cell in this diagonal has already been set. By choosing a
value for the rightmost cell, we once again force the fourth cell in
a submatrix.
x x X . . .
x x X . . .
x x . . . .
. . . . . .
. . . . . .
. . . . . .
We always set values two at a time by proceeding in this fashion. Another
advantage is that we eliminate many matrix configurations after filling
a small part of the upper left corner. Our first program, in comparison,
has to fill 14 cells of a 6-by-6 matrix before it gets around to checking
for validity. Our new program can in many cases recognize invalidity
and backtrack before it plunges so deeply into a fruitless part of the
state space.
Even with these improvements, it takes a non-trivial amount of time to
find all balanced 6-by-6 matrices with one fixed cell. After 3 hours and
15 minutes of real execution time on a 1.6 GHz Athlon CPU, we learn that
the number of matrices satisfying these conditions is 1,224,576.
/*-------------------begin diagonal_fill.c */
#include<stdlib.h>
#include<stdio.h>
int msg(char *s, int code) { /* error-message helper */
printf("%s\n", s);
return code;
}
int **mm, *used, n, max, sum, ix;
int dr[] = {0, 0, 1, 1}; /* vertical displacement */
int dc[] = {0, 1, 0, 1}; /* horizontal displacement */
int getsum(int r, int c) { /* computes sum rightward, downward */
int i, t = 0, tt;
for (i = 0; i < 4; i++) {
tt = mm[(r+dr[i]+n)%n][(c+dc[i]+n)%n];
if (tt != -1) /* check for sentinel value */
t += tt;
}
return t;
}
int min(int a, int b) { /* returns lesser of two integers */
if (a < b)
return a;
return b;
}
void diag(int r, int c, int di, int t_sum) {
int i, j, rem, rr, cc; /* diagonals stretch SW to NE */
if (di == 0) { /* first diagonal drawn at NW corner */
if (r < 0 || c == n) { /* last diagonal at SE corner */
if (r == n-2) { /* check for completion */
ix++;
/* uncomment this block for silent enumeration
if (ix % 100 == 0)
printf("%d\n", ix);
return;
*/
printf("\n%5d. ", ix); /* print solution number */
for (j = 0; j < n; j++) /* display top row */
printf(" %2d", mm[0][j]);
printf("\n");
for (i = 1; i < n; i++) {
printf(" "); /* display remaining rows */
for (j = 0; j < n; j++)
printf(" %2d", mm[i][j]);
printf("\n");
}
return;
}
if (c == n) { /* wrapping from right to bottom */
c = 2+r;
r = n-1;
}
else { /* wrapping from top to left */
r = c;
c = 0;
}
}
t_sum = getsum(r, c); /* compute sum rightward, downward */
if (t_sum > sum)
return;
}
if (di == 4) { /* have we gone around the submatrix? */
if (t_sum == sum)
diag(r-1, c+1, 0, -1); /* if so, move along diagonal */
return;
}
rr = (r+dr[di])%n; /* visit next cell in submatrix */
cc = (c+dc[di])%n;
if (mm[rr][cc] != -1) { /* cell already set? */
diag(r, c, di+1, t_sum); /* if so, move to next cell */
return;
}
rem = sum-t_sum; /* how much more to complete sum? */
if (di == 3) { /* last cell forces value */
if (rem <= max && !used[rem]) { /* check for valid range */
used[rem] = 1; /* mark */
mm[rr][cc] = rem; /* set */
diag(r-1, c+1, 0, -1); /* recurse */
mm[rr][cc] = -1; /* unset */
used[rem] = 0; /* unmark */
}
return;
}
if (t_sum >= sum) /* bail out if partial sum is invalid */
return;
for (i = min(rem, max); i > 0; i--) {
if (used[i]) /* seek unused values */
continue;
used[i] = 1; /* mark */
mm[rr][cc] = i; /* set */
diag(r, c, di+1, t_sum+i); /* recurse */
mm[rr][cc] = -1; /* unset */
used[i] = 0; /* unmark */
}
}
int main(int argc, char *argv[]) {
int i, j;
if (argc != 2) /* must pass exactly one argument */
return msg("please specify N for an N-by-N matrix", 0);
n = atoi(argv[1]);
if (n%2 != 0 || n < 2 || n > 6) /* check for manageable size */
return msg("N must be an even number between 2 and 6, inclusive", 0);
sum = 2*n*n - 2;
mm = (int **) calloc(n, sizeof(int *));
for (i = 0; i < n; i++) { /* allocate matrix */
mm[i] = (int *) calloc(n, sizeof(int));
for (j = 0; j < n; j++)
mm[i][j] = -1; /* initialize cells to sentinel */
}
used = (int *) calloc(n*n, sizeof(int));
max = n*n-1;
used[mm[0][0] = 0] = 1; /* set upper left corner to 0 */
ix = 0;
printf("looking for %d-by-%d matrices with submatrix sums == %d\n", n,n,sum);
diag(0, 0, 0, -1); /* start filling from top left */
printf("found %d matrices\n", ix);
return 0;
}
/*-------------------end diagonal_fill.c */
Q2.
This is a trick question. There is no need to write a program that
enumerates matrices of minimum discrepancy, since their total number
can be calculated directly with a simple formula. The "research-level"
exercise effectively makes the "initial" and "challenging" ones redundant.
Research-Level Question
Let us describe the construction of an N-by-N matrix of minimum
discrepancy such that N is odd and N >= 5. We are given N^2 values
0, 1, ..., N^2 - 2, N^2 - 1
with which to uniquely fill the N^2 cells of the matrix.
The smallest sum that can be formed by any four of these values is
0 + 1 + 2 + 3 = 6.
The greatest possible sum is
(N^2 - 4) + (N^2 - 3) + (N^2 - 2) + (N^2 - 1) = 4N^2 - 10.
Since the values in each sum do not overlap for N >= 5, and because a
matrix of such size can accommodate several 2-by-2 submatrices without
overlap, it is certainly possible to fill the matrix so that it contains
submatrices having each of these sums. The resulting discrepancy is
4N^2 - 10 - 6 = 4N^2 - 16.
For N = 5 and N = 7, this yields minimum discrepancies of
4*5*5 - 16 = 100 - 16 = 84
and
4*7*7 - 16 = 196 - 16 = 180,
respectively.
Now let us calculate the number of ways to form such a matrix if the
upper left corner is set to 0. We begin by observing that submatrices
consisting of the values
{0, 1, 2, 3}
and
{N^2 - 4, N^2 - 3, N^2 - 2, N^2 - 1}
are necessary in a matrix of minimum discrepancy. No other values can
form submatrices having sums 6 and N^2 - 10. These submatrices are also
sufficient, for once they have been placed, the remaining cells of the
matrix can take any values without affecting the smallest and largest
submatrix sums.
If the upper left corner is already 0, the submatrix of smallest sum must
be in one of four positions, with the values composing it arranged in one
of 3! = 6 ways. Suppose we have chosen one of these 4*6 = 24 possibilities.
0 1 . . .
2 3 . . .
. . . . .
. . . . .
. . . . .
We now wish to place one of the 4! = 24 submatrices of greatest sum
somewhere in the matrix. Of the N^2 possible locations for the upper
left corner of such a submatrix, four are occupied by the submatrix of
smallest sum. Thus, N^2 - 4 possible locations are left.
Once we have placed the submatrices of smallest and greatest sum, N^2 - 8
cells remain to be filled by the N^2 - 8 other values. This can be done
in (N^2 - 8)! ways.
In total, then, the number of possible configurations for an N-by-N
matrix of minimum discrepancy such that N is odd and N >= 5, with one
fixed cell, is the following.
24 * 24 * (N^2 - 4) * (N^2 - 8)!
= 576 * (N^2 - 4) * (N^2 - 8)!
For N = 5, this formula yields
576 * 21 * 355,687,428,096,000 = 4,302,395,130,249,216,000.
For N = 7, the value is
576 * 45 * 33,452,526,613,163,807,108,170,062,053,440,751,665,152,000,000,000
= 867,089,489,813,205,880,243,768,008,425,184,283,160,739,840,000,000,000.
To construct every such configuration would be a long and thankless chore. |
Clarification of Answer by
leapinglizard-ga
on
21 Dec 2004 03:30 PST
2)
I'm not sure you understand the meaning of the phrase "short notice".
However, I was quite sure I understood you to say that you did not
require solutions for the research-level questions. By the way,
research is something that takes months and years to complete, not
merely days or weeks.
1)
Here are new versions of border_fill and diagonal_fill that don't take
an argument on the command line, but prompt for the matrix size during
execution.
/*-------------------begin border_fill.c */
#include<stdlib.h>
#include<stdio.h>
int msg(char *s, int code) { /* error-message helper */
printf("%s\n", s);
return code;
}
int **mm, n, sum, max, *used, *stack, ix, fail;
int clear(int top) { /* resets used numbers */
while (top >= 0)
used[stack[top--]] = 0;
return 0;
}
int fill() { /* fills from bottom right corner */
int r, c, t, top = -1;
for (r = n-2; r > 0; r--) { /* assume bottom border is done */
for (c = n-2; c >= 0; c--) { /* assume right border is done */
t = sum - mm[r][c+1] - mm[r+1][c+1] - mm[r+1][c];
if (t < 0 || t > max || used[t])
return clear(top); /* attempt to form desired sum */
used[stack[++top] = mm[r][c] = t] = 1;
}
if (mm[r][0] + mm[r+1][0] + mm[r+1][n-1] + mm[r][n-1] != sum)
return clear(top); /* check backward at front of row */
}
if (mm[1][0] + mm[0][0] + mm[0][n-1] + mm[1][n-1] != sum)
return clear(top); /* in second row, check upward too */
for (c = n-2; c > 0; c--) { /* check top row */
t = sum - mm[0][c+1] - mm[1][c+1] - mm[1][c];
if (t < 0 || t > max || used[t])
return clear(top); /* attempt to form sum */
if (t + mm[0][c+1] + mm[n-1][c+1] + mm[n-1][c] != sum)
return clear(top); /* check upward */
used[stack[++top] = mm[0][c] = t] = 1;
}
if (sum-mm[0][1] != mm[0][0]+mm[1][0]+mm[1][1])
return clear(top); /* check backward and down */
if (sum-mm[0][1] != mm[0][0]+mm[n-1][0]+mm[n-1][1])
return clear(top); /* check backward and up */
ix++; /* if all is well, increment counter */
/* uncomment this block for silent enumeration
if (ix % 100 == 0)
printf("%d\n", ix);
return 0;
*/
printf("\n%5d. ", ix); /* print solution number */
for (c = 0; c < n; c++) /* display top row */
printf(" %2d", mm[0][c]);
printf("\n");
for (r = 1; r < n; r++) { /* display remaining rows */
printf(" ");
for (c = 0; c < n; c++)
printf(" %2d", mm[r][c]);
printf("\n");
}
return clear(top);
}
int right(int r) { /* fill right border */
int i;
if (r == n-1)
return fill();
for (i = 1; i <= max; i++) /* avoid top and bottom corners */
if (!used[i]) {
used[mm[r][n-1] = i] = 1;
right(r+1);
used[i] = 0;
}
return 0;
}
int bottom(int c) { /* fill bottom border */
int i;
if (c == n-1)
return right(1);
for (i = 1; i <= max; i++) /* avoid left and right corners */
if (!used[i]) {
used[mm[n-1][c] = i] = 1;
bottom(c+1);
used[i] = 0;
}
return 0;
}
int main() {
int i, j, k;
printf("please enter matrix size (2 or 4): ");
scanf("%d", &n);
if (n%2 != 0 || n < 2 || n > 4) /* check for manageable size */
return msg("N must be an even number between 2 and 4, inclusive", 0);
mm = (int **) calloc(n, sizeof(int *));
for (i = 0; i < n; i++) /* allocate matrix */
mm[i] = (int *) calloc(n, sizeof(int));
ix = 0;
max = n*n-1; /* allocate stack and flag array */
stack = (int *) calloc(max, sizeof(int));
used = (int *) calloc(max, sizeof(int));
used[mm[0][0] = 0] = 1; /* set upper left corner to 0 */
sum = 2*n*n - 2;
printf("looking for %d-by-%d matrices with submatrix sums == %d\n",n,n,sum);
for (i = 1; i <= max; i++)
for (j = 1; j <= max; j++) { /* try two corner values */
if (i == j)
continue; /* compute the third corner */
if ((k = sum-i-j) <= 0 || k > max || k == i || k == j)
continue; /* check for valid range */
used[mm[0][n-1] = i] = 1; /* if sum is good, set corners */
used[mm[n-1][n-1] = j] = 1;
used[mm[n-1][0] = k] = 1;
bottom(1); /* start filling at bottom border */
used[i] = used[j] = used[k] = 0;
}
printf("found %d matrices\n", ix);
return 0;
}
/*-------------------end border_fill.c */
/*-------------------begin diagonal_fill.c */
#include<stdlib.h>
#include<stdio.h>
int msg(char *s, int code) { /* error-message helper */
printf("%s\n", s);
return code;
}
int **mm, *used, n, max, sum, ix;
int dr[] = {0, 0, 1, 1}; /* vertical displacement */
int dc[] = {0, 1, 0, 1}; /* horizontal displacement */
int getsum(int r, int c) { /* computes sum rightward, downward */
int i, t = 0, tt;
for (i = 0; i < 4; i++) {
tt = mm[(r+dr[i]+n)%n][(c+dc[i]+n)%n];
if (tt != -1) /* check for sentinel value */
t += tt;
}
return t;
}
int min(int a, int b) { /* returns lesser of two integers */
if (a < b)
return a;
return b;
}
void diag(int r, int c, int di, int t_sum) {
int i, j, rem, rr, cc; /* diagonals stretch SW to NE */
if (di == 0) { /* first diagonal drawn at NW corner */
if (r < 0 || c == n) { /* last diagonal at SE corner */
if (r == n-2) { /* check for completion */
ix++;
/* uncomment this block for silent enumeration
if (ix % 100 == 0)
printf("%d\n", ix);
return;
*/
printf("\n%5d. ", ix); /* print solution number */
for (j = 0; j < n; j++) /* display top row */
printf(" %2d", mm[0][j]);
printf("\n");
for (i = 1; i < n; i++) {
printf(" "); /* display remaining rows */
for (j = 0; j < n; j++)
printf(" %2d", mm[i][j]);
printf("\n");
}
return;
}
if (c == n) { /* wrapping from right to bottom */
c = 2+r;
r = n-1;
}
else { /* wrapping from top to left */
r = c;
c = 0;
}
}
t_sum = getsum(r, c); /* compute sum rightward, downward */
if (t_sum > sum)
return;
}
if (di == 4) { /* have we gone around the submatrix? */
if (t_sum == sum)
diag(r-1, c+1, 0, -1); /* if so, move along diagonal */
return;
}
rr = (r+dr[di])%n; /* visit next cell in submatrix */
cc = (c+dc[di])%n;
if (mm[rr][cc] != -1) { /* cell already set? */
diag(r, c, di+1, t_sum); /* if so, move to next cell */
return;
}
rem = sum-t_sum; /* how much more to complete sum? */
if (di == 3) { /* last cell forces value */
if (rem <= max && !used[rem]) { /* check for valid range */
used[rem] = 1; /* mark */
mm[rr][cc] = rem; /* set */
diag(r-1, c+1, 0, -1); /* recurse */
mm[rr][cc] = -1; /* unset */
used[rem] = 0; /* unmark */
}
return;
}
if (t_sum >= sum) /* bail out if partial sum is invalid */
return;
for (i = min(rem, max); i > 0; i--) {
if (used[i]) /* seek unused values */
continue;
used[i] = 1; /* mark */
mm[rr][cc] = i; /* set */
diag(r, c, di+1, t_sum+i); /* recurse */
mm[rr][cc] = -1; /* unset */
used[i] = 0; /* unmark */
}
}
int main(int argc, char *argv[]) {
int i, j;
printf("please enter matrix size (2, 4, or 6): ");
scanf("%d", &n);
if (n%2 != 0 || n < 2 || n > 6) /* check for manageable size */
return msg("N must be an even number between 2 and 6, inclusive", 0);
sum = 2*n*n - 2;
mm = (int **) calloc(n, sizeof(int *));
for (i = 0; i < n; i++) { /* allocate matrix */
mm[i] = (int *) calloc(n, sizeof(int));
for (j = 0; j < n; j++)
mm[i][j] = -1; /* initialize cells to sentinel */
}
used = (int *) calloc(n*n, sizeof(int));
max = n*n-1;
used[mm[0][0] = 0] = 1; /* set upper left corner to 0 */
ix = 0;
printf("looking for %d-by-%d matrices with submatrix sums == %d\n", n,n,sum);
diag(0, 0, 0, -1); /* start filling from top left */
printf("found %d matrices\n", ix);
return 0;
}
/*-------------------end diagonal_fill.c */
|
