home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 15 / CD_ASCQ_15_070894.iso / vrac / tpchal_1.zip / RG.C0 < prev    next >
Text File  |  1994-05-26  |  1KB  |  37 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. #include <stdio.h>
  9.  
  10. void try(long n, int k, char *digits)   /* recursive solver */
  11. {
  12.     int i;
  13.  
  14.     for ( i = 1; i < 10; ++i )      /* look thru remaining digits */
  15.     {
  16.         if ( digits[i] != '*' ) {   /* if not already used */
  17.             long nn = n * 10 + i;   /* next candidate */
  18.             if ( nn % k == 0 ) {    /* passes divisibility test? */
  19.                 if ( k == 9 ) {     /* if 9 digits, print solution */
  20.                     printf("%ld\n", nn);
  21.                 } else {            /* else extend partial solution */
  22.                     digits[i] = '*';        /* flag digit as used */
  23.                     try(nn, k+1, digits);   /* solve */
  24.                     digits[i] = i + '0';    /* unflag digit */
  25.                 }
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. int main(void)
  32. {
  33.     char digits[] = "0123456789";
  34.     try(0L, 1, digits);             /* initial state */
  35.     return 0;
  36. }
  37.