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

int t[4][4],wr[4][4],wc[4][4],ws[4][4];

void MLX(int n){ // n ar en numrering av rutorna
  int p,r,c;
  if(n==16) { //En losning hittad
    for(r=0;r<4;r++) {
      for(c=0;c<4;c++) printf("%c",(t[r][c]==-1)?'0':t[r][c]+'1');
      printf("\n");
    }
    exit(0);
  }
  r=n/4; 
  c=n%4;
  if(t[r][c]!=-1) MLX(n+1); //Redan ifylld
  else {
    //Testa varje siffra
    for(p=0;p<4;p++) if(!wr[r][p] && !wc[c][p] && !ws[(r/2)*2+(c/2)][p]) {
      t[r][c]=p;
      wr[r][p]=1; //Markera att siffran nu finns pa raden
      wc[c][p]=1; //Markera att siffran nu finns i kolumnen
      ws[(r/2)*2+(c/2)][p]=1;   //Markera att siffran nu finns i kvartsrutan

      MLX(n+1); //Ga till nasta ruta och fortsatt losa sudokun

      //Om vi kommer hit, betyder det att vi inte hittade 
      //nagon losning med denna siffra, eftersom annars skulle programmet 
      //ha avslutats. Alltsa maste vi aterstalla effekterna av siffran
      //innan vi valjer en ny siffra i for-loopen.
      wr[r][p]=0;
      wc[c][p]=0;
      ws[(r/2)*2+(c/2)][p]=0;
      t[r][c]=-1;
    }
  }
}

int main(){
  int a,b,err=0;
  char tt[5];
  for(a=0;a<4;a++) for(b=0;b<4;b++) {
    wr[a][b]=0;
    wc[a][b]=0;
    ws[a][b]=0;
  }
  for(a=0;a<4;a++) {
    printf("Rad %d ? ", a+1);
    scanf("%s",tt);
    for(b=0;b<4;b++) {
      if(tt[b]=='0') t[a][b]=-1;
      else {
	t[a][b]=tt[b]-'1';
	wr[a][t[a][b]]+=1;
	wc[b][t[a][b]]+=1;
	ws[(a/2)*2+(b/2)][t[a][b]]+=1;
      }
    }
  }
  MLX(0); //Los sudokun rekursivt
  return 0;
}