home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / vrac / tpchal_1.zip / RG.C < prev    next >
C/C++ Source or Header  |  1994-05-26  |  2KB  |  63 lines
  1. /* solve.c -- find solution to simple programming challenge
  2. **
  3. **  public domain by Ray Gardner   5/94
  4. **
  5. ** Find a 9-digit number, using all digits 1 thru 9 (once each),
  6. ** such that the first n digits are divisible by n, for n <= 9.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <setjmp.h>
  12.  
  13. jmp_buf env;
  14.  
  15. long RetVal;
  16.  
  17. void try(long n, int k, char *digits)   /* recursive solver */
  18. {
  19.       int i;
  20.  
  21.       for (i = 1; i < 10; ++i)            /* look thru remaining digits   */
  22.       {
  23.             if (digits[i] != '*')         /* if not already used          */
  24.             {
  25.                   long nn = n * 10 + i;   /* next candidate               */
  26.  
  27.                   if (nn % k == 0)        /* passes divisibility test?    */
  28.                   {
  29.                         if (k == 9)       /* if 9 digits, we're done      */
  30.                         {
  31.                               RetVal = nn;
  32.                               longjmp(env, -1);
  33.                         }
  34.                         else              /* else extend partial solution */
  35.                         {
  36.                               digits[i] = '*';        /* flag used digit  */
  37.                               try(nn, k+1, digits);   /* solve            */
  38.                               digits[i] = i + '0';    /* unflag digit     */
  39.                         }
  40.                   }
  41.             }
  42.       }
  43. }
  44.  
  45. int main(void)
  46. {
  47.       char digits[11];
  48. #ifdef TEST
  49.       int I;
  50.  
  51.       for (I = 0; I < 1000; ++I)
  52.       {
  53. #endif
  54.             strcpy(digits, "0123456789");
  55.             if (0 == setjmp(env))
  56.                   try(0L, 1, digits);     /* initial state */
  57. #ifdef TEST
  58.       }
  59. #endif
  60.       printf("Number = %lu\n", RetVal);
  61.       return 0;
  62. }
  63.