puzzle.c

   1 #include <stdio.h>
   2
   3 struct {
   4   int id;
   5   char x[4];
   6 } list[] = {
   7   {  0, {0,0,0,0} },
   8   { 11, {0,0,0,1} },
   9   { 13, {0,0,0,2} },
  10   { 11, {0,0,1,0} },
  11   {  3, {0,0,1,1} },
  12   { 15, {0,0,1,2} },
  13   { 13, {0,0,2,0} },
  14   { 16, {0,0,2,1} },
  15   {  4, {0,0,2,2} },
  16   { 11, {0,1,0,0} },
  17   {  6, {0,1,0,1} },
  18   { 21, {0,1,0,2} },
  19   {  3, {0,1,1,0} },
  20   {  9, {0,1,1,1} },
  21   { 18, {0,1,1,2} },
  22   { 15, {0,1,2,0} },
  23   { 22, {0,1,2,1} },
  24   { 19, {0,1,2,2} },
  25   { 13, {0,2,0,0} },
  26   { 21, {0,2,0,1} },
  27   {  7, {0,2,0,2} },
  28   { 16, {0,2,1,0} },
  29   { 17, {0,2,1,1} },
  30   { 23, {0,2,1,2} },
  31   {  4, {0,2,2,0} },
  32   { 20, {0,2,2,1} },
  33   { 10, {0,2,2,2} },
  34   { 11, {1,0,0,0} },
  35   {  3, {1,0,0,1} },
  36   { 16, {1,0,0,2} },
  37   {  6, {1,0,1,0} },
  38   {  9, {1,0,1,1} },
  39   { 22, {1,0,1,2} },
  40   { 21, {1,0,2,0} },
  41   { 17, {1,0,2,1} },
  42   { 20, {1,0,2,2} },
  43   {  3, {1,1,0,0} },
  44   {  9, {1,1,0,1} },
  45   { 17, {1,1,0,2} },
  46   {  9, {1,1,1,0} },
  47   {  1, {1,1,1,1} },
  48   { 14, {1,1,1,2} },
  49   { 18, {1,1,2,0} },
  50   { 14, {1,1,2,1} },
  51   {  5, {1,1,2,2} },
  52   { 15, {1,2,0,0} },
  53   { 18, {1,2,0,1} },
  54   { 23, {1,2,0,2} },
  55   { 22, {1,2,1,0} },
  56   { 14, {1,2,1,1} },
  57   {  8, {1,2,1,2} },
  58   { 19, {1,2,2,0} },
  59   {  5, {1,2,2,1} },
  60   { 12, {1,2,2,2} },
  61   { 13, {2,0,0,0} },
  62   { 15, {2,0,0,1} },
  63   {  4, {2,0,0,2} },
  64   { 21, {2,0,1,0} },
  65   { 18, {2,0,1,1} },
  66   { 19, {2,0,1,2} },
  67   {  7, {2,0,2,0} },
  68   { 23, {2,0,2,1} },
  69   { 10, {2,0,2,2} },
  70   { 16, {2,1,0,0} },
  71   { 22, {2,1,0,1} },
  72   { 20, {2,1,0,2} },
  73   { 17, {2,1,1,0} },
  74   { 14, {2,1,1,1} },
  75   {  5, {2,1,1,2} },
  76   { 23, {2,1,2,0} },
  77   {  8, {2,1,2,1} },
  78   { 12, {2,1,2,2} },
  79   {  4, {2,2,0,0} },
  80   { 19, {2,2,0,1} },
  81   { 10, {2,2,0,2} },
  82   { 20, {2,2,1,0} },
  83   {  5, {2,2,1,1} },
  84   { 12, {2,2,1,2} },
  85   { 10, {2,2,2,0} },
  86   { 12, {2,2,2,1} },
  87   {  2, {2,2,2,2} }
  88 };
  89
  90 int rect[8][8], hbound[8][8], vbound[8][8];
  91
  92 static void
  93 dump(void)
  94 {
  95   int x,y;
  96
  97   for (x=1; x<=6; x++)
  98     {
  99       for (y=1; y<=4; y++)
 100         printf(".%d. ", list[rect[x][y]].x[1]);
 101       putchar('\n');
 102       for (y=1; y<=4; y++)
 103         printf("%d.%d ", list[rect[x][y]].x[0], list[rect[x][y]].x[2]);
 104       putchar('\n');
 105       for (y=1; y<=4; y++)
 106         printf(".%d. ", list[rect[x][y]].x[3]);
 107       putchar('\n');
 108       putchar('\n');
 109     }
 110 }
 111
 112 static void
 113 fill(int x, int y, unsigned int mask)
 114 {
 115   int i,j;
 116
 117   i = 9*(3*hbound[x][y]+vbound[x][y]);
 118   for (j=0; j<9; i++, j++)
 119     if (!(mask & (1 << list[i].id)))
 120       {
 121         //      printf("place <%d,%d> %d\n", x, y, list[i].id);
 122         rect[x][y] = i;
 123         //      if (hbound[x][y] != list[i].x[0] ||
 124         //          vbound[x][y] != list[i].x[1]) puts("BUG!!!");
 125         hbound[x][y+1] = list[i].x[2];
 126         vbound[x+1][y] = list[i].x[3];
 127         if (x == 6)
 128           {
 129             if (vbound[x+1][y])
 130               continue;
 131             if (y == 4)
 132               {
 133                 if (hbound[x][y+1] != 2)
 134                   continue;
 135                 else
 136                   {
 137                     puts("Gotcha!!!");
 138                     dump();
 139                     fflush(stdout);
 140                     //    exit(0);
 141                     return;
 142                   }
 143               }
 144             fill(x,y+1,mask | (1 << list[i].id));
 145           }
 146         else if (y == 4)
 147           {
 148             if (hbound[x][y+1])
 149               continue;
 150             fill(x+1,1,mask | (1 << list[i].id));
 151           }
 152         else
 153           fill(x,y+1,mask | (1 << list[i].id));
 154       }
 155 }
 156
 157 int
 158 main(int argc, char **argv)
 159 {
 160   int x;
 161   for (x=1; x<=4; x++)
 162     vbound[1][x] = 1;
 163   fill(1,1,0);
 164   puts("No chance");
 165   return 0;
 166 }