#include<stdio.h>
#include<time.h>
#define STAGE 4
const int AVERAGE = STAGE * (STAGE * STAGE + 1 ) / 2;
const int NUMBER = STAGE * STAGE;
bool CUR_STATE[NUMBER] = {0};
static int Total = 0;
void Show( FILE * fp, int *p )
{
int i,j;
fprintf( fp, "Case %d\n" , Total + 1 );
for(i = 0; i < STAGE; ++i){
for( j =0; j < STAGE; ++j)
fprintf( fp, "%5d", *(p + i * STAGE + j) );
fprintf( fp, "\n" );
}
fprintf( fp,"\n" );
}
bool Check( int *p,int m, int n, int t )
{
int i,j;
for( i = 0; i < m; ++i)
for( j = 0; j < STAGE; ++j)
if( t == *(p + i * STAGE + j)) return false;
for( j = 0; j < n; ++j)
if( t == *(p + m * STAGE + j)) return false;
return true;
}
void Find( FILE* fp, int *p, int m, int n )
{
int sum,i,j,t,k;
if( m == STAGE - 1 && n == STAGE - 1)
{
for( i =0,sum =0; i < STAGE - 1; ++i)
sum += *(p + m * STAGE + i);
if( sum >= AVERAGE) return;
*(p + m * STAGE +n) = AVERAGE - sum;
for( i = 0, sum = 0; i < STAGE; ++i)
sum += *( p + i * STAGE +n);
if( sum != AVERAGE) return;
for( i = 0, sum = 0; i < STAGE; ++i)
sum += *(p + i * STAGE + i);
if(sum != AVERAGE) return;
Show( fp, p );
Total++;
}
else if( n == STAGE - 1)
{
for( j =0, sum =0; j < STAGE - 1; ++j)
sum += *( p + m * STAGE + j);
t = AVERAGE - sum;
if(t < 1 || t > NUMBER) return;
if( CUR_STATE[t-1] == false/*Check(p, m, n, t)*/){
CUR_STATE[t-1] = true;
*(p + m * STAGE +n) = t;
//if(m < 2){printf(" %d,%d,%d",m,n,t);Show(p);}
if( m == STAGE - 2)
Find( fp, p, m + 1, 1);
else
Find( fp, p, m + 1, 0);
CUR_STATE[t-1] = false;
}
}
else if( m == STAGE - 1)
{
for( i = 0, sum =0; i < STAGE - 1; ++i)
sum += *( p + i * STAGE + n);
t = AVERAGE - sum;
if(t < 1 || t > NUMBER) return;
if( !CUR_STATE[t-1]/*Check(p,m,n,t)*/)
{
CUR_STATE[t-1] = true;
*(p + m * STAGE + n) = t;
//if( n == 0)
//{
// for( i = 0, sum =0; i < STAGE; ++i)
// sum += *( p + i * STAGE + STAGE - 1 - i);
// if(sum != AVERAGE)
// { CUR_STATE[t-1] = false; return;}
//}
Find( fp, p, m , n +1);
CUR_STATE[t-1] = false;
}
}
else if( m == STAGE - 2 && n == 0)
{
for( t = 1; t <= NUMBER; ++t)
{
if( !CUR_STATE[t-1] ){
CUR_STATE[t-1] = true;
*(p+ m * STAGE ) = t;
for( sum = 0, i = 0; i < STAGE - 1; ++i)
sum += *(p + i * STAGE);
j = AVERAGE - sum;
if( j < 1 || j > NUMBER) { CUR_STATE[t-1] = false;continue;}
if( !CUR_STATE[j-1]){
CUR_STATE[j-1] = true;
*(p + ( m + 1) * STAGE) = j;
for( sum = j, i = 0; i < STAGE - 2; ++i)//sum 初始为左下角的数
sum += *(p + i * STAGE + STAGE - 1 - i);
k = AVERAGE - sum;
if( k < 1 || k > NUMBER) { CUR_STATE[t-1] = false; CUR_STATE[j-1] = false;continue;}
if( !CUR_STATE[k-1]){
CUR_STATE[k-1] = true;
*( p + m * STAGE + 1) = k;
Find( fp, p, m, n + 2);
CUR_STATE[k-1] = false;
}
CUR_STATE[j-1] = false;
}
CUR_STATE[t-1] = false;
}
}
}
else
{
for( t = 1; t <= NUMBER; ++t)
{
if(!CUR_STATE[t-1]/*Check( p, m, n, t)*/){
CUR_STATE[t-1] = true;
*(p + m * STAGE + n) = t;
Find( fp, p, m, n+1 );
CUR_STATE[t-1] = false;
}
}
}
}
int main()
{
int Cube[NUMBER] = {0};
FILE *fp = fopen( "Result.txt", "wt" );
if( fp == NULL )
return -1;
int start = time( 0 );
Find( fp, Cube,0,0 );
fprintf( fp, "总用时%d ms\n", time( 0 ) - start );
fclose( fp );
printf( "总用时%d ms \n", time( 0 ) - start );
return 0;
}
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
