A square arrangement of numbers
1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4
is a 5 x 5 Latin Square because each whole number from 1 to 5 appears once and only once in each row and column.
Write a program that will compute the number of NxN Latin Squares whose first row is:
1 2 3 4 5.......N
Your program should work for any N from 2 to 7.
PROGRAM NAME: latin
INPUT FORMAT
One line containing the integer N.
SAMPLE INPUT (file latin.in)
5
OUTPUT FORMAT
A single integer telling the number of latin squares whose first row is 1 2 3 . . . N.
SAMPLE OUTPUT (file latin.out)
1344
I was wondering if anyone can tell me what can I do with this code to get the program to run less than 1s. I think I made all the necessary optimisations.
Code: Select all
#include<stdio.h>
int imar[8][8],imak[8][8],n,nf=1;
int smesti(int i,int j);
FILE *fin,*fout;
main()
{
int i,bbr;
fin=fopen("latin.in","r");
fscanf(fin,"%d",&n);
fclose(fin);
nf=1;
for(i=1;i<n;i++)
nf=nf*i;
for(i=1;i<=n;i++)
{
imar[i][i]=1;
imak[i][i]=1;
}
fout=fopen("latin.out","w");
bbr=smesti(2,2);
fprintf(fout,"%.0lf\n",(double)bbr*(double)nf);
fclose(fout);
return 0;
}
int smesti(int i,int j)
{
register int k,l,s=-1,priv;
register int brres=0;
if(j>n)
{
i++;
j=2;
}
if(i==n)
return 1;
for(k=1;k<=n;k++)
{
if(imar[i][k] || imak[j][k])
continue;
if(i==2 && k>=j && s!=-1)
brres+=s;
else
{
imar[i][k]=1;
imak[j][k]=1;
priv=smesti(i,j+1);
brres+=priv;
if(k>j)
s=priv;
}
imar[i][k]=0;
imak[j][k]=0;
}
return brres;
}