#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void init(int p[27], int m[9], int r1[9], int r2[9]);
void set(int m[9], int r1[9], int r2[9], int pa);
void pr(int m[9], int r1[9], int r2[9]);
int newp(int p[27], int n);
void reset(int p[27], int m[9], int r1[9], int r2[9]);
int ck(int m[9], int r1[9], int r2[9]);


main()
{
  srand(time(0));

  int m[9];
  int r1[9];
  int r2[9];
  int p[27];

  int suc[28];
  for(int i=0;i<=27;i++) suc[i]=0;

  for(int t=0;t<5000000;t++)
  {
    init(p,m,r1,r2);
  
    int n;
  
    for(n=1;n<=8;n++)
    {
      set(m,r1,r2,newp(p,n));
    }
  
  
    for(n=9;n<=27;n++)
    {
      set(m,r1,r2,newp(p,n));

      if(ck(m,r1,r2))
        break;

      reset(p,m,r1,r2);
    }
    for(int i=n;i<=27;i++)
    {
      suc[i]++;
    }

  }
  printf("\n");
  for(int i=0;i<=27;i++)
    printf("%2d %d\n",i,suc[i]);

}

int ck(int m[9], int r1[9], int r2[9])
{
  int ad;

  do
  {
    ad=0;
    for(int i=0;i<9;i++)
    {
      if(r1[i] && r2[i])
        if((!m[i]) || (!m[(i+1)%9]))
        {
          m[i]=m[(i+1)%9]=1;
          ad++;
        }
      if(r1[i] || r2[i])
        if(m[i] ^ m[(i+1)%9])
        {
          m[i]=m[(i+1)%9]=1;
          ad++;
        }
    }
  }
  while(ad>0);

  for(int i=0;i<9;i++)
    if(!m[i])
      return 0;
  return 1;
}

void reset(int p[27], int m[9], int r1[9], int r2[9])
{
  for(int i=0;i<9;i++)
  {
    m[i] = 0;
    r1[i] = 0;
    r2[i] = 0;
  }
  for(int pa=0;pa<27;pa++)
    if(p[pa])
      switch(pa/9)
      {
        case 0:
            m[pa%9]=1;
          break;
        case 1:
            r1[pa%9]=1;
          break;
        case 2:
            r2[pa%9]=1;
          break;
      }
}

int newp(int p[27], int n)
{
  int i = rand()%(27-n+1);
  int j = -1;
  for(;i>=0;i--)
  {
    j++;
    for(;p[j];j++)
      ;
  }
  p[j]=1;
  return j;
}

void pr(int m[9], int r1[9], int r2[9])
{
  for(int i=0;i<9;i++)
    printf("__");
  printf("\n");

  for(int i=0;i<9;i++)
    printf(" %s",r1[i]?"-":" ");
  printf("\n");

  for(int i=0;i<9;i++)
    printf("%s ",m[i]?"+":" ");
  printf("\n");

  for(int i=0;i<9;i++)
    printf(" %s",r2[i]?"-":" ");
  printf("\n");
}

void set(int m[9], int r1[9], int r2[9], int pa)
{
  switch(pa/9)
  {
    case 0:
        m[pa%9]=1;
      break;
    case 1:
        r1[pa%9]=1;
      break;
    case 2:
        r2[pa%9]=1;
      break;
  }
}

void init(int p[27], int m[9], int r1[9], int r2[9])
{
  for(int i=0;i<27;i++)
    p[i]=0;
  for(int i=0;i<9;i++)
  {
    m[i] = 0;
    r1[i] = 0;
    r2[i] = 0;
  }
}