home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / misc / volume40 / magicsqr / part01 < prev    next >
Encoding:
Text File  |  1993-10-10  |  27.9 KB  |  765 lines

  1. Newsgroups: comp.sources.misc
  2. From: bert@netcom.com (Roberto Sierra)
  3. Subject: v40i004:  magicsquare - NxN Magic Square Solver, Part01/01
  4. Message-ID: <1993Oct11.013714.17142@sparky.sterling.com>
  5. X-Md4-Signature: 0ee26c7808e4df3afe3f9053ef457ade
  6. Keywords: ANSI C program computes solutions to NxN Magic Square Problem
  7. Sender: kent@sparky.sterling.com (Kent Landfield)
  8. Organization: Tempered MicroDesigns
  9. Date: Mon, 11 Oct 1993 01:37:14 GMT
  10. Approved: kent@sparky.sterling.com
  11.  
  12. Submitted-by: bert@netcom.com (Roberto Sierra)
  13. Posting-number: Volume 40, Issue 4
  14. Archive-name: magicsquare/part01
  15. Environment: ANSI-C
  16.  
  17. rqureshi@girtab.usc.edu (Rauf) wrote:
  18. >  I was wondering if any of the esteemed reader of this group
  19. >  could answer my question or show me a way to find it.
  20. >
  21. >  How you can write the integers from 1 to 36, in a big square with
  22. >  36 small squares in it, such that the sum of the numbers in diagonal,
  23. >  column or rows is same. with no repitition of numbers.
  24. >
  25. >  I know how to do it for squares of order 5X5, 7X7,... but this 6X6 is
  26. >  a bit tricky for me.
  27.  
  28. [*Long* reply with C code to follow -- be forwarned!!]
  29.  
  30. I love puzzles, so this seemed an ideal problem to tackle last
  31. night while eating cold spaghetti with the headphones blaring.
  32. Unfortunately, after much puzzling and a ream of scratch paper
  33. consumed, I couldn't come up with a direct approach to solving
  34. the problem for abitrary NxN cases, nor could I answer the specific
  35. 6x6 question posed.
  36.  
  37. What I *was* able to do fairly rapidly (being a programmer and
  38. not a mathematician by trade) was to hack out an exhaustive search
  39. program in C which finds the solutions to the NxN problem if you throw
  40. enough CPU cycles at the problem.  I'm fairly certain that if you
  41. ran this program overnight, or perhaps for a day or two you'd get
  42. the answers you want.  [Warning: the algorithm is probably of
  43. exponential order, so don't try anything too large early on
  44. unless you have unlimited access to a Cray!].
  45.  
  46. The code is actually not too bad.  For 3x3 and 4x4 cases, it
  47. generates the solutions quite rapidly (or at least faster than
  48. the *worst* algorithm I could conceive of).  It starts taking
  49. more time for 5x5 and 6x6 and so on.  Still, there's a recursive
  50. pruning algorithm that does a pretty good job in reducing the
  51. number of cases tested.
  52.  
  53. What would definitely help would be to understand the properties
  54. of these squares in more detail.  I have some hunches about the
  55. basics of these beasts, but not enough to trust to code.
  56.  
  57. For example, I suspect that all odd-sized squares have fairly
  58. simple solutions in which the 'middle' number in the sequence
  59. must be located at the center of the square.  For 3x3 squares,
  60. the 5 goes in the middle.  For 5x5 square, I'm pretty sure the
  61. 13 has to go in the middle -- it makes 'sense' that way.  For
  62. even-sized squares (4x4, 6x6, etc.), there are a lot more
  63. solutions, and they are much weirder, since there is a greater
  64. degree of freedom to where values are placed.
  65.  
  66. Also, I suspect that all of the solutions for a given square size
  67. have the same sum, but have no proof of this phenomenon.  For example,
  68. the 3x3 solution (and rotations thereof) adds up to 15.  All of
  69. the 4x4 solutions add up to 34.  I'm not sure what the 5x5
  70. solutions should add up to, but I have a hunch the magic number
  71. is 65 (the middle number '13' times the order '5') -- yet to
  72. be verified, so don't quote me.
  73.  
  74. Again, these are only vague hunches... no firm conclusions.
  75.  
  76.  
  77. I actually had some code that was already pretty close to what
  78. I needed, so it only took a few hours to whack it into shape.
  79. You should be able to get this to run on any machine with an ANSI-
  80. compliant C compiler.  There's instructions for how to fire the
  81. thing up embedded in the code and a detailed description of the
  82. algorithm.
  83.  
  84. One nice thing about the code is that you can tell the program
  85. to look for cases only exhibiting a certain sum value, which
  86. will limit the number of cases tested by orders of magnitude.
  87. For example, it takes a couple of minutes on a Sun to come up
  88. with the first 4x4 solution unless you tell it that the 4x4 
  89. sum is 34 (all solutions add to 34), in which case you'll
  90. get the same answer back in about a second!!  If you know
  91. what the magic number is for larger systems, 5x5, 6x6 and
  92. 7x7 and so on, then that'll help a great deal.  The problem
  93. is, I don't know what the magic numbers are, or even if all
  94. of the solutions share the same sum.
  95.  
  96. If anyone can come up with a better algorithm, let me know,
  97. I'd be interested in hearing about it.  I know I could do
  98. a better job if I spent more time on it and understood the
  99. properties of these 'magic' squares better.  The nice thing
  100. about having an exhaustive search program lying around is
  101. that you don't have to know too much about the underlying
  102. nature of the problem.  Just leave your system running the
  103. next time you go home for spaghetti.  :-)
  104.  
  105.  
  106.    Roberto Sierra
  107.    Tempered MicroDesigns
  108.    San Francisco, CA
  109. ------
  110. #! /bin/sh
  111. # This is a shell archive.  Remove anything before this line, then feed it
  112. # into a shell via "sh file" or similar.  To overwrite existing files,
  113. # type "sh file -c".
  114. # Contents:  MagicSquare.c
  115. # Wrapped by kent@sparky on Sun Oct 10 20:34:47 1993
  116. PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH
  117. echo If this archive is complete, you will see the following message:
  118. echo '          "shar: End of archive."'
  119. if test -f 'MagicSquare.c' -a "${1}" != "-c" ; then 
  120.   echo shar: Will not clobber existing file \"'MagicSquare.c'\"
  121. else
  122.   echo shar: Extracting \"'MagicSquare.c'\" \(22090 characters\)
  123.   sed "s/^X//" >'MagicSquare.c' <<'END_OF_FILE'
  124. X/*
  125. X**  MagicSquare.c   --    Find solutions to the Magic Squares problem.
  126. X**            Roberto Sierra    7/25/93  v1.0
  127. X**
  128. X**  Description:
  129. X**    This program finds all the possible ways that the integers
  130. X**    1 through N^2 can be arranged in an NxN square so that the
  131. X**    sum of any row, column, or diagonal is identical.  By default,
  132. X**    the program prints the first solution it finds.  You can
  133. X**    use command line options to have all solutions printed or
  134. X**    merely counted.  The program allows the square to be any
  135. X**    size from 1x1 (trivial case) to 10x10.  WARNING: the time
  136. X**    required by the algorithm blows up sharply as the dimensions
  137. X**    increase.
  138. X**
  139. X**    The code makes no attempt to eliminate symmetrical solutions,
  140. X**    so the number of distinct solutions will be much lower than
  141. X**    the number of solutions reported by the program.
  142. X**
  143. X**
  144. X**  Usage:
  145. X**    MagicSquare [-ac] n [sum]
  146. X**
  147. X**    n    The dimensions of the square (the length of a side).
  148. X**        Must be an integer value in the range 1<=n<=10.
  149. X**    sum    Optional sum constraint.  By default, the program
  150. X**        will find arrangements matching any sum that appears along
  151. X**        all rows, columns and diagonals.  By specifying a specific
  152. X**        sum, only those solutions which match that specific sum
  153. X**        will be searched for and reported.  This should speed up
  154. X**        the program quite significantly.  The sum value, if
  155. X**        supplied, must be an integer in the proper range --
  156. X**        [FYI -- n*(n+1)/2 <= sum <= n*(2n^2-n+1)/2]
  157. X**    -a    Find (and print) ALL solutions.
  158. X**    -c    Count all solutions, but do not print them.  Overrides -a.
  159. X**
  160. X**    The output is sent to stdout.  All error messages are
  161. X**    sent to stderr.  If a problem arises, -1 is returned.
  162. X**
  163. X**
  164. X**  Examples:
  165. X**
  166. X**    MagicSquare 3        ## Show a 3x3 solution
  167. X**    3x3 board...
  168. X**    sum=15
  169. X**      2  7  6
  170. X**      9  5  1
  171. X**      4  3  8
  172. X**
  173. X**    MagicSquare -c 3    ## Count all 3x3 solutions
  174. X**    3x3 board...
  175. X**    ...there are 8 solutions.
  176. X**
  177. X**    MagicSquare 4 34    ## Show a 4x4 solution whose sum is 34
  178. X**    4x4 square...
  179. X**    sum = 34
  180. X**      1 14  8 11
  181. X**     15  4 10  5
  182. X**     12  7 13  2
  183. X**      6  9  3 16
  184. X**
  185. X**    MagicSquare -a 4 10    ## Show all 4x4 solutions whose sum is 10
  186. X**    4x4 square...
  187. X**    ...there are 0 solutions whose sum is 10
  188. X**
  189. X**
  190. X**  Build Instructions:
  191. X**    You'll need an ANSI C compiler (or the willingness to edit
  192. X**    the program a bit).  If you've got Gnu C, then you can
  193. X**    compile and load the program as follows:
  194. X**
  195. X**        gcc MagicSquare.c -ansi -o MagicSquare
  196. X**
  197. X**    [If you're using MPW on the Mac, define '-d MPW' on the
  198. X**    compile line so that background processing will occur.]
  199. X**
  200. X**
  201. X**  Algorithm:
  202. X**    A brute-force approach would be to attempt to find all possible
  203. X**    ways that N^2 integers can be arranged within an NxN square,
  204. X**    compute the row/column/diagonal sums for each position, and
  205. X**    report only those arrangments which have equal sums all around.
  206. X**    The problem is that N^2 integers can be arranged in (N^2)!
  207. X**    ways, which blows up rapidly as N increases.  For N=2,
  208. X**    only 24 positions need be tested.  For N=3, some 362,880
  209. X**    positions exist (still relatively reasonable).  However,
  210. X**    for N=4, roughly 2x10^13 possible positions exist and the
  211. X**    numbers get much worse beyond that.  In addition, the cost of
  212. X**    computing row/column/diagonal sums for each position will
  213. X**    gobble up lots of CPU time.
  214. X**
  215. X**    Although the approach I've taken is still fairly simplistic
  216. X**    and still blows up quite sharply as the size of the square
  217. X**    grows, it's not quite on the order of (N^2)!  [I wouldn't
  218. X**    hazard to guess what the actual order is...].  Fortunately,
  219. X**    I already had a piece of recursive code which I was able to
  220. X**    hack into shape in the space of an evening to do the job, so
  221. X**    I'm quite satisfied with the result for that reason alone.
  222. X**    [FYI -- The other code computed solutions to the Eight Queens
  223. X**    chess problem in an extremely rapid, straightforward manner.]
  224. X**
  225. X**    The algorithm makes no assumptions about the nature of these
  226. X**    'magic' squares, and therefore is able to find ALL possible
  227. X**    solutions.  A better algorithm would exploit the specific
  228. X**    nature of the magic these squares exhibit.
  229. X**
  230. X**    My algorithm is as follows:
  231. X**    (1)  If the user has supplied a constraining sum, perform
  232. X**         step 3, otherwise perform step 2 instead.
  233. X**    (2)  Along the 'forward' diagonal, recursively generate
  234. X**         all possible ways that N integers can be arranged
  235. X**         along the diagonal.  For each position, record the
  236. X**         sum of the diagonal and use it as the 'target' for
  237. X**         the remainder of the algorithm.  Go on to step 4.
  238. X**    (3)  If a constraining sum has been supplied by the user,
  239. X**         then along the 'forward' diagonal, recursively generate
  240. X**         all possible ways that N integers that add up to the
  241. X**         target sum can be arranged.  Go on to step 4.
  242. X**    (4)  Now that the 'target' sum value has been computed
  243. X**         and a set of diagonal values are in place, pivot on
  244. X**         the value in the top-left corner and recursively
  245. X**         generate all possible ways that the remaining (N^2)-N
  246. X**         integers can be arranged such that the sum of the row
  247. X**         matches the target.  Stop the recursion at the first
  248. X**         point that we know we're at a dead end (for instance,
  249. X**         if the row sum exceeds the target sum or there are
  250. X**         no numbers left which are small enough to do the job).
  251. X**    (5)  Once the top row has been generated, pivot on the
  252. X**         same top-left value and recursively generate a column
  253. X**         from the remaining set of integers such that the
  254. X**         column sum matches the target.  Once again, stop
  255. X**         the recursion at any point where it is clear that
  256. X**         the sum won't match the target or the necessary
  257. X**         integers are unavailable.
  258. X**    (6)  Repeat steps 4 and 5 on successive diagonal pivots
  259. X**         until all rows and columns have been generated.
  260. X**    (7)  Lastly, when all rows and columns have been generated
  261. X**         with matching sums, check that the sum of the reverse
  262. X**         diagonal also matches.  If so, print the board layout
  263. X**         as a solution and continue in this manner until all
  264. X**         possible solutions have been found (-a or -c option).
  265. X**
  266. X**    Note:
  267. X**    The loops are structured to try smaller numbers first
  268. X**    and the larger numbers later.  I experimented with flipping
  269. X**    the allocation order around and discovered that it typically
  270. X**    takes *much* longer to find the first solution if the larger
  271. X**    numbers are allocated first.  I guess this is because there
  272. X**    is more low-level recursion going on with low numbers last.
  273. X**
  274. X**    The initial code was somewhat ugly in the way that
  275. X**    the sums were computed and the way that unique integers
  276. X**    were tracked.  Hopefully I'll be able to spend another
  277. X**    evening putting in some better code to make these 'inner
  278. X**    loops' significantly faster.
  279. X**
  280. X**
  281. X**  Contact:
  282. X**    For queries regarding this program, or to obtain source
  283. X**    for the Eight Queens chess program mentioned, contact
  284. X**    the author at any of the following addresses:
  285. X**
  286. X**        Roberto Sierra
  287. X**        bert@netcom.com   (preferred address)
  288. X**        73557.2101@compuserve.com
  289. X**
  290. X**        Tempered MicroDesigns
  291. X**        P.O. Box 170638
  292. X**        San Francisco, CA  94117
  293. X**
  294. X**
  295. X**  Fine Print:
  296. X**    This program is in the public domain and can be used for
  297. X**    any purpose whatsoever, including commercial application.
  298. X**    [I'd like to hear what you do with it, though.]
  299. X**    Absolutely no warranty or liability is implied or extended
  300. X**    by the author.
  301. X**
  302. X**
  303. X**  Modification History:
  304. X**    PRS  7/25/93  v1.0 -- Original ANSI C version.  Inefficient.
  305. X**
  306. X*/
  307. X
  308. X
  309. X#include <stdio.h>                /* Need standard I/O functions */
  310. X#include <stdlib.h>                /* Need exit() routine interface */
  311. X#include <string.h>                /* Need strcmp() interface */
  312. X#ifdef    MPW                    /* Macintosh MPW ONLY */
  313. X#include <CursorCtl.h>                /* Need cursor control interfaces */
  314. X#endif
  315. X
  316. X#define MAXSIZE     10                /* Maximum size of square */
  317. X#define MAXVALUE    (MAXSIZE * MAXSIZE)     /* Maximum integer value */
  318. X
  319. X                        /* ONE of these must be #define'd */
  320. X#define    ORIG_SCAN                /* Select original 'uniqueness' method */
  321. X#undef    LUT_SCAN                /* Faster scanner -- limited to 5x5 max */
  322. X
  323. X
  324. X
  325. X
  326. X/******************************/
  327. X/****    GLOBAL VARIABLES   ****/
  328. X/******************************/
  329. X
  330. Xint        n = 0;                /* Size of square */
  331. Xint        nsquare = 0;            /* Maximum integer value (n*n) */
  332. Xint        printing = 1;            /* TRUE if printing positions */
  333. Xint        findall = 0;            /* TRUE if finding all solutions */
  334. X
  335. Xunsigned long    solutions = 0;            /* Number of solutions found */
  336. Xint        board[MAXSIZE][MAXSIZE];    /* Shows current contents of board */
  337. Xint        targ = 0;            /* Target col/row/diagonal sum value */
  338. Xchar        *progname = 0;            /* The name of this program */
  339. Xchar        usage[] = {"usage: %s [-ac] n [sum]\n"};
  340. X                        /* Usage string */
  341. X
  342. X
  343. X/*******************/
  344. X/****    MACROS    ****/
  345. X/*******************/
  346. X
  347. X/*
  348. X**  ORIG_SCAN scanning method
  349. X**  This is a series of macros which scan through integers
  350. X**  such that no integer is ever used more than once.  Since
  351. X**  this stuff sits at the 'bottom' of the recursion, the loops
  352. X**  tend to slow everything down.  [This was the original scanning
  353. X**  method, and was the easiest to implement.]
  354. X*/
  355. X
  356. X#ifdef    ORIG_SCAN                /* Start of ORIG_SCAN implementation */
  357. X
  358. Xint    inuse[MAXVALUE+1];            /* Shows which numbers are in use */
  359. X
  360. X#define RESERVE(i)        (inuse[i] = i)    /* Mark value as in use */
  361. X#define RELEASE(i)        (inuse[i] = 0)    /* Mark value as not in use */
  362. X/* Looping primitives */
  363. X                        /* Loop through all values */
  364. X#define FOR_ALL(i)        for(i=1; i<=nsquare; ++i)
  365. X                        /* Find all available values */
  366. X#define FOR_AVAILABLE(i)    FOR_ALL(i) if (!inuse[i])
  367. X                        /* Find all available thru maximum */
  368. X#define FOR_AVAILABLE_RESTRICTED(i,high)    \
  369. X                for(i=1; i<=(high); ++i) if (!inuse[i])
  370. X
  371. Xvoid init_scan(void)                /* Initializes scanning variables */
  372. X{
  373. X    register int i;                /* Loop variable */
  374. X    FOR_ALL(i) RELEASE(i);            /* Release all values */
  375. X}                        /* End of init_scan() */
  376. X
  377. X#endif    /*ORIG_SCAN*/                /* End of ORIG_SCAN implementation */
  378. X
  379. X
  380. X
  381. X/*
  382. X**  LUT_SCAN scanning method
  383. X**  [not yet implemented]
  384. X*/
  385. X
  386. X#ifdef    LUT_SCAN                /* Start of LUT_SCAN implementation */
  387. X#error    LUT_SCAN not yet implemented.  Use ORIG_SCAN.
  388. X#endif    /*LUT_SCAN*/                /* End of LUT_SCAN implementation */
  389. X
  390. X
  391. X
  392. X
  393. X
  394. X/***********************/
  395. X/****    ROUTINES    ****/
  396. X/***********************/
  397. X
  398. X/* Internal prototypes */
  399. Xvoid    main(int argc,char **argv);            /*    Main program */
  400. Xvoid    free_diagonal(int i,int sum);            /*    Diagonal recursion */
  401. Xvoid    constrained_diagonal(int i,int sum);        /*    Diagonal to match constraint
  402. X*/
  403. Xvoid    row(int i);                    /*    Main row routine */
  404. Xvoid    column(int i);                    /*    Main column routine */
  405. Xvoid    row_recurse(int i,int j,int sum,int *p);    /*    Row recursion routine */
  406. Xvoid    col_recurse(int i,int j,int sum,int *p);    /*    Column recursion routine
  407. X*/
  408. Xvoid    final_check(void);                /*    Bottom level solution check */
  409. Xvoid    pboard(void);                    /*    Print a solution */
  410. X
  411. X
  412. X
  413. X
  414. X
  415. X/*---------------------------- main() -------------------------
  416. X**
  417. X**  The job of the main program is mostly to decode the command
  418. X**  line arguments and initialize all the arrays and variables
  419. X**  needed.  Then, the appropriate free or constrained diagonal
  420. X**  recursion routine is called.
  421. X*/
  422. X
  423. Xvoid main(int argc,char **argv)
  424. X{
  425. X    register int    i;                /* Loop variables */
  426. X    register char   *p;             /* Pointer to argument */
  427. X
  428. X#ifdef    MPW                    /* Macintosh MPW ONLY */
  429. X    InitCursorCtl(0);                /* Enable cursor control */
  430. X#endif
  431. X
  432. X    progname = argv[0];             /* The name of the program */
  433. X
  434. X    /****   DECODE COMMAND LINE ARGUMENTS   ****/
  435. X
  436. X    for (i=1; i<argc; ++i) {            /* Scan through arguments */
  437. X    p = argv[i];                /* Pointer to base of argument */
  438. X    if (*p == '-') {            /* Command line option? */
  439. X        while (*++p) {            /* Loop through characters */
  440. X        switch (*p) {            /* What is the character */
  441. X        case 'a':            /* '-a' option */
  442. X            findall = 1;        /* Set flag to find all solutions */
  443. X            break;
  444. X        case 'c':            /* '-c' option */
  445. X            printing = 0;        /* Counting, not printing */
  446. X            findall = 1;        /* Also forces findall option */
  447. X            break;
  448. X        default:            /* Illegal option */
  449. X            fprintf(stderr,"%s: Illegal option '%s'\n",progname,argv[i]);
  450. X            fprintf(stderr,usage,progname);
  451. X            exit(-1);
  452. X        }                /* End of switch */
  453. X        }                    /* End of loop */
  454. X    } else {                /* End of option test */
  455. X        if (n == 0) {            /* Is N unitialized? */
  456. X        if (sscanf(p,"%d",&n) != 1) {    /* Read N value */
  457. X            fprintf(stderr,"%s: '%s' is not an integer\n", progname, p);
  458. X            exit(-1);
  459. X        }
  460. X        if (n <= 0 || n > MAXSIZE) {    /* Range check */
  461. X            fprintf(stderr,"%s: 1st number, %d, not in proper range\n",
  462. X            progname, n);
  463. X            fprintf(stderr,"%s: should be in range 1..%d\n",progname,MAXSIZE);
  464. X        }
  465. X        } else if (targ == 0) {        /* Is target sum uninitialized? */
  466. X            int lowsum = n*(n+1)/2;        /* Sum of integers 1..N */
  467. X        int highsum = n*(2*n*n-n+1)/2;    /* Sum of integers N^2-N+1..N^2 */
  468. X        
  469. X        if (sscanf(p,"%d",&targ) != 1) {
  470. X            fprintf(stderr,"%s: '%s' is not an integer\n", progname, p);
  471. X            exit(-1);
  472. X        }
  473. X        if (targ < lowsum || targ > highsum) {
  474. X            fprintf(stderr,
  475. X            "%s: 2nd number, %d, not in proper range\n",
  476. X            progname, targ);
  477. X            fprintf(stderr,
  478. X                "%s: should be in the range %d..%d for a %dx%d square\n",
  479. X            progname, lowsum, highsum, n, n);
  480. X            exit(-1);
  481. X        }
  482. X        } else {                /* Too many arguments */
  483. X            fprintf(stderr,"%s: unexpected argument '%s'\n", progname, p);
  484. X        fprintf(stderr,usage,progname);
  485. X        exit(-1);
  486. X        }                    /* End of value if-then-else */
  487. X    }                    /* End of argument test */
  488. X    }                        /* End of argument scan loop */
  489. X    if (n == 0) {
  490. X    fprintf(stderr,"%s: parameter N is missing\n",progname);
  491. X    fprintf(stderr,usage,progname);
  492. X    exit(-1);
  493. X    }
  494. X
  495. X
  496. X    /*    INITIALIZATION    */
  497. X    nsquare = n*n;                /* This is the highest integer */
  498. X    init_scan();                /* Initialize scanning variables */
  499. X
  500. X    printf("%dx%d square...\n", n, n);
  501. X    fflush(stdout);                /* Force prompt to output */
  502. X    if (targ == 0) free_diagonal(0,0);        /* Begin unconstrained recursion */
  503. X    else constrained_diagonal(0,0);        /* Otherwise, use constrained sum */
  504. X
  505. X
  506. X    /*    REPORT NUMBER OF SOLUTIONS FOUND  */
  507. X    if (printing && solutions) putchar('\n');
  508. X    if (solutions == 1) {
  509. X    printf("...there is %ld solution", solutions);
  510. X    } else {
  511. X    printf("...there are %ld solutions", solutions);
  512. X    }
  513. X    if (targ) printf(" whose sum is %d", targ);
  514. X    printf("\n");
  515. X
  516. X    exit(0);                    /* No errors */
  517. X}                        /* End of main() */
  518. X
  519. X
  520. X
  521. X
  522. X/*---------------------- free_diagonal() -----------------------
  523. X**
  524. X**  This fills in the forward diagonal values and computes
  525. X**  the sum of the diagonal as it proceeds.  It is recursive
  526. X**  so that all possible combinations are attempted.  When
  527. X**  the diagonal is full, then row/column filling is performed.
  528. X*/
  529. X
  530. Xvoid free_diagonal(register int pivot, int sum)
  531. X{
  532. X    register int    x;                /* Value under test */
  533. X    register int    *p = &board[pivot][pivot];    /* Address of pivot point */
  534. X
  535. X    if (pivot++ == n) {                /* Stop recursion */
  536. X#ifdef    MPW                    /* Macintosh MPW ONLY */
  537. X    SpinCursor(1);                /* Enable background processing */
  538. X#endif
  539. X    targ = sum;                /* Set target sum for rows/columns */
  540. X    row(0);                    /* Begin row/column fill */
  541. X    targ = 0;                /* Reset to 'floating' sum */
  542. X    } else {                    /* Diagonal not full yet */
  543. X    FOR_AVAILABLE(x) {            /* For all available values... */
  544. X        *p = RESERVE(x);            /* Reserve value for pivot */
  545. X        free_diagonal(pivot,sum+x);        /* Recurse to next pivot */
  546. X        *p = RELEASE(x);            /* Release pivot value */
  547. X    }
  548. X    }
  549. X}                        /* End of free_diagonal() */
  550. X
  551. X
  552. X
  553. X
  554. X/*-------------------- constrained_diagonal() -------------------
  555. X**
  556. X**  This fills in the forward diagonal values in a constrained
  557. X**  fashion so that their sum is equal to that of the target
  558. X**  value supplied by the user.  It is recursive in nature so
  559. X**  that all possible combinations are attempted.  When the
  560. X**  diagonal is full, then row/column filling is started.
  561. X*/
  562. X
  563. Xvoid constrained_diagonal(register int pivot, int sum)
  564. X{
  565. X    register int    x;                /* Value under test */
  566. X    register int    *p = &board[pivot][pivot];    /* Address of pivot point */
  567. X    register int    range = targ - sum;        /* Range of possible values */
  568. X
  569. X    if (pivot++ == n) {                /* Stop recursion */
  570. X#ifdef    MPW                    /* Macintosh MPW ONLY */
  571. X    SpinCursor(1);                /* Enable background processing */
  572. X#endif
  573. X    if (sum == targ) row(0);        /* Begin row/column fill */
  574. X    } else {                    /* Diagonal not full yet */
  575. X    if (range>nsquare) range = nsquare;    /* Clip range to m    FOR_AVAILABLE_RESTRICTED(x,range) {    /* For all available <= range */
  576. X        *p = RESERVE(x);            /* Reserve value for pivot */
  577. X        constrained_diagonal(pivot,sum+x);    /* Recurse to next pivot */
  578. X        *p = RELEASE(x);            /* Release pivot value */
  579. X    }
  580. X    }
  581. X}                        /* End of constrained_diagonal() */
  582. X
  583. X
  584. X
  585. X
  586. X/*------------------------- row() ------------------------
  587. X**
  588. X**  row() is the top of the row recursion process.
  589. X**  The current sum of the specified row is computed.
  590. X**  Then the row recursion routine is called to fill
  591. X**  in the remaining slots with all possible values.
  592. X*/
  593. X
  594. Xvoid row(register int i)
  595. X{
  596. X    register int    j,sum=0;            /* Column index, row sum */
  597. X    register int    *p = &board[i][0];        /* Pointer to first item */
  598. X
  599. X    for (j=0; j<=i; ++j) {            /* For all columns thru pivot */
  600. X    sum += *p++;                /* Add values in row */
  601. X    }
  602. X    row_recurse(i,i+1,sum,p);            /* Begin row recursion */
  603. X}                        /* End of row() */
  604. X
  605. X
  606. X
  607. X/*----------------------- column() -----------------------
  608. X**
  609. X**  COLUMN is the top of the column recursion process.
  610. X**  The current sum of the specified column is computed.
  611. X**  Then the column recursion routine is called to fill
  612. X**  in the remaining slots with all possible values.
  613. X*/
  614. X
  615. Xvoid column(register int j)
  616. X{
  617. X    register int    i,sum=0;            /* Row index, column sum */
  618. X    register int    *p = &board[0][j];        /* Pointer to first item */
  619. X
  620. X    for (i=0; i<=j; ++i) {            /* For all rows thru pivot */
  621. X    sum += *p;                /* Add values in column */
  622. X    p += MAXSIZE;                /* Advance to next row */
  623. X    }
  624. X    col_recurse(j+1,j,sum,p);            /* Begin column recursion */
  625. X}                        /* End of column() */
  626. X
  627. X
  628. X
  629. X
  630. X
  631. X/*------------------- row_recurse() ----------------------
  632. X**
  633. X**  ROW_RECURSE is the row recursion routine.
  634. X**  This routine fills in the remaining items in a row
  635. X**  with all possible values so that the row sum does
  636. X**  not exceed the target sum.    If the target sum is
  637. X**  acheived exactly, then the row is accepted and column
  638. X**  recursion is initiated.
  639. X*/
  640. X
  641. Xvoid row_recurse(int i, int j, int sum, register int *p)
  642. X{
  643. X    register int    x;                /* Value under test */
  644. X    register int    range = targ - sum;        /* Range of possible values */
  645. X
  646. X    if (j++ == n) {                 /* Stop recursion */
  647. X#ifdef    MPW                    /* Macintosh MPW ONLY */
  648. X    SpinCursor(1);                /* Enable background processing */
  649. X#endif
  650. X
  651. X    if (range == 0) {            /* Accept row if sum is correct */
  652. X        if (i+1 == n) final_check();    /* Last row done, final checks */
  653. X        else column(i);            /* Otherwise, do column fill */
  654. X    }
  655. X    } else {                    /* Haven't reached bottom yet */
  656. X    if (range>nsquare) range = nsquare;    /* Clip range to maximum */
  657. X    FOR_AVAILABLE_RESTRICTED(x,range) {    /* For all available <= range */
  658. X        *p = RESERVE(x);            /* Reserve value at position */
  659. X        row_recurse(i,j,sum+x,p+1);        /* Recurse to next column */
  660. X        *p = RELEASE(x);            /* Release value from position */
  661. X    }
  662. X    }
  663. X}                        /* End of row_recurse() */
  664. X
  665. X
  666. X
  667. X
  668. X/*--------------------- col_recurse() -----------------------
  669. X**
  670. X**  COL_RECURSE is the column recursion routine.
  671. X**  This routine fills in the remaining items in a column
  672. X**  with all possible values so that the column sum does
  673. X**  not exceed the target sum.    If the target sum is
  674. X**  acheived exactly, then the recursion ceases and a
  675. X**  final check of the reverse diagonal is performed before
  676. X**  the solution can be accepted.
  677. X*/
  678. X
  679. Xvoid col_recurse(int i,int j, int sum, register int *p)
  680. X{
  681. X    register int    x;                /* Value under test */
  682. X    register int    range = targ - sum;        /* Range of possible values */
  683. X
  684. X    if (i++ == n) {                 /* Stop recursion */
  685. X    if (range == 0) {            /* Accept column if sum is correct */
  686. X        if (j+1 == n) final_check();    /* Last column done, final checks */
  687. X        else row(j+1);            /* Otherwise do next row fill */
  688. X    }
  689. X    } else {                    /* Haven't reached bottom yet */
  690. X    if (range>nsquare) range = nsquare;    /* Clip range to maximum */
  691. X    FOR_AVAILABLE_RESTRICTED(x,range) {    /* For all available <= range */
  692. X        *p = RESERVE(x);            /* Reserve value at position */
  693. X        col_recurse(i,j,sum+x,p+MAXSIZE);    /* Recurse to next row */
  694. X        *p = RELEASE(x);            /* Release value from position */
  695. X    }
  696. X    }
  697. X}                        /* End of col_recurse() */
  698. X
  699. X
  700. X
  701. X
  702. X/*--------------------- final_check() ---------------------
  703. X**
  704. X**  FINAL_CHECK tests the reverse diagonal sum.
  705. X**  This occurs at the bottom of all pivot, row and column recursion,
  706. X**  so if the sum is OK, then a new solution has been found.
  707. X*/
  708. X
  709. Xvoid final_check(void)
  710. X{
  711. X    register int    i, sum=0;            /* Loop variable, diagonal sum */
  712. X
  713. X    for(i=0; i<n; ++i) {            /* Loop through all rows (cols) */
  714. X    sum += board[i][n-i-1];            /* Add values along diagonal */
  715. X    }
  716. X    if (sum == targ) {                /* Diagonal sum matches desired? */
  717. X    ++solutions;                /* Congrats.  We have a solution */
  718. X    if (printing) pboard();         /* Print the solution if desired */
  719. X    if (!findall) exit(0);            /* Stop if only looking for first */
  720. X    }
  721. X}                        /* End of final_check() */
  722. X
  723. X
  724. X
  725. X
  726. X/*----------------------- pboard() ----------------------
  727. X**
  728. X**  This routines prints the board for a particular solution.
  729. X**
  730. X*/
  731. X
  732. Xvoid pboard(void)
  733. X{
  734. X    register int    i,j;            /* Rank/File indices */
  735. X
  736. X    if (findall) {                /* Print solution number */
  737. X    printf("\nSolution #%lu -- ",solutions);
  738. X    }
  739. X    printf("sum = %d\n",targ);            /* Print characteristic sum */
  740. X    for(i=0; i<n; ++i) {            /* Loop through all rows */
  741. X    for(j=0; j<n; ++j) {            /* Loop through all columns */
  742. X        printf(" %2d",board[i][j]);     /* Print values at each position */
  743. X    }                    /* End of column loop */
  744. X    putchar('\n');                /* Break line */
  745. X    }                        /* End of row loop */
  746. X    fflush(stdout);                /* Force solution to output */
  747. X}                        /* End of pboard() */
  748. X
  749. X
  750. X
  751. X
  752. X
  753. X/****    End of MagicSquare.c    ****/
  754. X
  755. END_OF_FILE
  756.   if test 22090 -ne `wc -c <'MagicSquare.c'`; then
  757.     echo shar: \"'MagicSquare.c'\" unpacked with wrong size!
  758.   fi
  759.   # end of 'MagicSquare.c'
  760. fi
  761. echo shar: End of archive.
  762. exit 0
  763.  
  764. exit 0 # Just in case...
  765.