enum {S0=3, S1=S0*S0, S2=S1*S1};

static int _count(int num)
{
   int i, count = 0;
   for (i=0; i<S1; i++)
      if ((num & (1<<i)))
         count++;
   return count;
}

static int countzeros(int num)
{
   return _count(~num);
}

static void set_banned(unsigned short *banned, char *d, int j)
{
   if (d[j] != '0') {
      int jr = j / S1, jc = j % S1;
      int k, kr, kc, b = 1<<(d[j]-'1');
      for (k=0; k<S1; k++)
         banned[jr*S1+k] |= b, banned[k*S1+jc] |= b;
      for (kr=0; kr<S0; kr++)
         for (kc=0; kc<S0; kc++)
            banned[(kr+(jr/S0)*S0)*S1+kc+(jc/S0)*S0] |= b;
   }
}

static int bestindex(unsigned short *banned, char *d)
{
   int score, index, bestscore=S1, bestindex=-1;
   for (index=0; index<S2; index++)
      if (d[index]=='0' && (score = countzeros(banned[index]), score < bestscore))
         bestindex = index, bestscore = score;
   return bestindex;
}

static void recurse(char *d, unsigned short *in_banned, int index)
{
   unsigned short banned[S2];
   memcpy(banned, in_banned, sizeof(banned));
   if (index < 0)
      for (index = 0; index<S2; index++)
         set_banned(banned, d, index);
   else
      set_banned(banned, d, index);

   if (index = bestindex(banned, d), index == -1) {
      puts(d);
      return;
   }
   for (d[index]='0'+S1; d[index]>'0'; d[index]--)
      if (!(banned[index] & (1<<(d[index]-'1'))))
         recurse(d, banned, index);
}

int main(int argc, char *argv[])
{
   unsigned short banned[S2];
   memset(banned, 0, sizeof(banned));
   if (argc >= 2)
      recurse(argv[1], banned, -1);
   return 0;
}
// 100000100000000000000000000010000010000000000000000000000000000002000002003000003
// 010000000020000000030000000040000000050000000000000000000006789000000000000000000
// 003000051502006400007050000000630700200708006004021000000070800008100609170000500
// 006900070000010002800000000020000004000000001005006000000000060000002050010043000 (hard - one solution)
// 452619378371248965986573241794162583628435719135897624213754896849326157567981432