#include <stdio.h>
int s[16]={0},f[16]={0},c=0;
int j1(){return s[0]+s[1]+s[2]+s[3]==34;}int j2(){return s[0]+s[4]+s[5]+s[6]==34;}
int j3(){return s[4]+s[7]+s[8]+s[9]==34;}int j4(){return s[3]+s[8]+s[10]+s[6]==34;}
int j5(){return s[1]+s[7]+s[10]+s[11]==34;}int j6(){return s[5]+s[10]+s[12]+s[13]==34;}
int j7(){return s[2]+s[8]+s[12]+s[14]==34;}
int j(){return s[6]+s[11]+s[14]+s[15]==34&&s[3]+s[9]+s[13]+s[15]==34&&s[0]+s[7]+s[12]+s[15]==34;}
void print(){printf("%2d %2d %2d %2d\n",s[0],s[1],s[2],s[3]);printf("%2d %2d %2d %2d\n",s[4],s[7],s[8],s[9]);
printf("%2d %2d %2d %2d\n",s[5],s[10],s[12],s[13]);printf("%2d %2d %2d %2d\n",s[6],s[11],s[14],s[15]);}
void search(int pos){int i;
switch(pos){case 4:if(!j1())return; break;case 7:if(!j2())return; break;case 10:if(!j3())return; break;
case 11:if(!j4())return; break;case 12:if(!j5())return; break;case 14:if(!j6())return; break;case 15:if(!j7())return; break;
case 16:if(!j())return; print(); printf("\n"); ++c; return;}
for(i=0;i<16;++i)if(!f[i]){f[i]=1;s[pos]=i+1;search(pos+1);f[i]=0;}}
main(){search(0);printf("%d通り\n",c);}

ラインの判定は全て埋めたあとではなく、各ラインが埋まったらすぐに判定する。
なるべく早くに多くのラインを判定できるよう埋め方を工夫する。