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

int n;
char*** f;

int x,y,z;
char proper;

void jacmat_iteration() {
  int x1, y1, z1;
  for(x1=0;x1<n;x1++) if(f[x1][y][z]==1) break;
  if(!proper && rand()%2==1) for(x1++;x1<n;x1++) if(f[x1][y][z]==1) break;
  for(y1=0;y1<n;y1++) if(f[x][y1][z]==1) break;
  if(!proper && rand()%2==1) for(y1++;y1<n;y1++) if(f[x][y1][z]==1) break;
  for(z1=0;z1<n;z1++) if(f[x][y][z1]==1) break;
  if(!proper && rand()%2==1) for(z1++;z1<n;z1++) if(f[x][y][z1]==1) break;
  f[x][y][z]++; f[x1][y1][z]++; f[x1][y][z1]++; f[x][y1][z1]++;
  f[x1][y][z]--; f[x][y1][z]--; f[x][y][z1]--;
  if((--f[x1][y1][z1])==-1) {
    x=x1; y=y1; z=z1;
    proper=0;
  } else proper=1;
}

void find_zero_cell() {
  do {
    x = (n-1)*(rand()/(RAND_MAX+0.0));
    y = (n-1)*(rand()/(RAND_MAX+0.0));
    z = (n-1)*(rand()/(RAND_MAX+0.0));
  } while(f[x][y][z]!=0);
}

void jacmat(int k) {
  for(;k>0;k--) {
    find_zero_cell();
    do { jacmat_iteration(); } while(!proper);
  }
}

void init() {
  f = (char***)(malloc(sizeof(char**)*n));
  for(x=0;x<n;x++) {
    f[x] = (char**)(malloc(sizeof(char*)*n));
    for(y=0;y<n;y++) {
      f[x][y] = (char*)(malloc(sizeof(char)*n));
      for(z=0;z<n;z++) f[x][y][z] = (y==((z+x)%n));
    }
  }
  proper=1;
}

void release() {
  for(x=0;x<n;x++) {
    for(y=0;y<n;y++) free(f[x][y]);
    free(f[x]);
  }
  free(f);
}

void print() {
  for(x=0;x<n;x++) {
    for(y=0;y<n;y++) {
      for(z=0;z<n;z++) if(f[x][y][z]==1) {
        printf("%4d",z+1);
        break;
      }
    }
    fputc('\n',stdout);
  }
}

int main(int argc, char** argv) {
  time_t t;
  int k;
  puts (
    "Jacobson-Matthews random Latin square generator, v. 1.0.\n"
    "Copyright (c) Stanislav Busygin, 2002.\n"
  );
  srand((unsigned) time(&t));
  if(argc>=3) {
    sscanf(*++argv,"%d",&n);
    init();
    sscanf(*++argv,"%d",&k);
    jacmat(k);
    print();
    release();
  } else puts (
    "Syntax: jacmat <n> <k>\n"
    "n: the order of Latin square\n"
    "k: the number of Jacobson-Matthews iterations\n"
  );
  return 0;
}