/* Programmer : Maya Ahmed
* File: checkfranklin.c
* This file contains the program to check whether a given
* square is a Franklin square. That is, it checks whether
* the row sums, column sums, bent diagonal sums add to the
* common magic sum, the half-rows and half-columns add to
* one-half the magic sum, the 2x2 subsquares add to
* one-half the magic sum for n=8 and one-fourth the magic
* sum for n=16.
* Date: 11 March 2002
*/
/*
Reference: Maya Ahmed, "How many squares are there, Mr.
Franklin?: Constructing and Enumerating Franklin Squares",
Amer. Math. Monthly, Vol. 111, 2004, 394--410.
*/
/* (C) GPL, Maya Ahmed, 2005.
* This is free program without any warranty, you may use/modify
* this program but keep this notice intact and must re-distribute the
* orignal source unmodified with all distributions.
* Email: maya.ahmed(at)gmail.com
* HTTP: http://www.math.ucdavis.edu/~maya
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*========================================================*/
typedef struct /* the struct of a vector */
{
int size;
int* values;
}vector;
void print_vector(vector*c); /* print to screen */
void print_vector_to_file(vector* c,FILE* output);
vector* create_malloc_vector(int* size);
void free_malloc_vector(vector* a);
/*
=============== get_vector_from_file =============================
This function gets a vector from a file.
*/
vector* get_vector_from_file(int* size)
{
int i;
vector* a;
a = create_malloc_vector(size);
for(i=0; i< *size; i++)
{
scanf("%d", &a ->values[i] );
}/* reading the vector a */
return a;
}/* end of get_vector_from_file function */
/*===================print_vector=============================
This function prints a vector on to the screen.
*/
void print_vector (vector* c)
{
int i;
printf("[ ");
for(i=0; i < c -> size ; i++)
printf("%d ", c -> values[i]);
printf("]\n");
}/* end of print_vector function */
/*============= create_malloc_vector =================*/
vector* create_malloc_vector(int* size)
{
int i;
vector* a = (vector*)malloc(sizeof(vector));
a -> size = *size;
a -> values = (int*)malloc(sizeof(int)*(*size));
if(a == 0)
{
printf("Out of memory, exiting program\n");
exit(0);
}
if(a->values == 0)
{
printf("Out of memory, exiting program\n");
exit(0);
}
for(i=0; i < a->size; i++)
a->values[i] = 0;
return a;
}/* end of create_malloc_vector function */
/*============= free_malloc_vector ==================*/
void free_malloc_vector(vector* a)
{
a->size = 0;
free(a->values);
free(a);
}/* end of free_malloc_vector_function */
/*============ functions to create row and column sums========= */
int first_row_sum(int n, vector* a)
{
int first_row_sum = 0;
int i;
for(i=0; i < n; i++)
first_row_sum = first_row_sum + a->values[i];
return first_row_sum;
}/* end of create_first_row_sum function */
int create_row_sum(vector* a, int j, int n)
{
int i;
int sum= 0;
for(i=0;i<n;i++)
sum = sum + a->values[(j*n)+i];
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int create_col_sum(vector* a , int j, int n)
{
int i;
int sum = 0;
for(i=0;i<n;i++)
sum = sum + a->values[(i*n)+j];
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
/*=========== functions to create bent diagonal sums =============*/
int left_bent_diag_sum(vector*a, int j, int n)
{
int i;
int sum = 0;
for(i=0;i<(n/2);i++)
sum = sum+ a->values[(i*n)+i+j]; /*first half of left_bent_diagonal*/
for(i=(n/2);i<n;i++)
sum = sum+ a->values[(i*n)+(n-i)-1+j] ; /*second half of left_bent_diagonal*/
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int broken_left_bent_diag_sum(vector* a, int k, int n)
{
int i;
int sum = 0;
for(i=0;i<(n/2)-1-k;i++)
sum = sum+a->values[(i*n)+i+(n/2)+1+k]; /* first half of bent_diagonal */
for(i=0; i< 1+k; i++)
sum = sum+ a->values[(n/2-1-k+i)*n+i]; /* first half of bent_diagonal */
for(i=0;i<(n/2)-1-k;i++)
sum = sum+ a->values[((n-i-1)*n)+i+(n/2)+1+k]; /* second half of bent_diagonal */
for(i=0; i< 1+k; i++)
sum= sum+ a->values[((n-(n/2-1-k+i)-1)*n)+i]; /* second half of bent_diagonal */
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int right_bent_diag_sum(vector*a, int j, int n)
{
int i;
int sum = 0;
for(i=0;i<(n/2);i++)
sum = sum+ a->values[((i+1)*n)-(i+1)-j]; /* first half of bent_diagonal */
for(i=(n/2);i<n;i++)
sum= sum+ a->values[((i+1)*n)-(n-i)-j]; /* first half of bent_diagonal */
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int broken_right_bent_diag_sum(vector* a, int k, int n)
{
int i;
int sum=0;
for(i=0;i<k+1;i++)
sum = sum+a->values[i*n+k-i]; /* first half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum= sum+a->values[i*n+(n-i)+k];
for(i=0;i<k+1;i++)
sum=sum+a->values[((n-1-i)*n)+k-i]; /* second half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum= sum+ a->values[(n-i-1)*n+(n-i)+k];
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int top_bent_diag_sum(vector* a, int j, int n)
{
int i;
int sum=0;
for(i=0;i<(n/2);i++)
sum = sum+ a->values[(i+j)*n + i]; /* first half of bent_diagonal */
for(i=(n/2);i>0;i--)
sum = sum+ a->values[((i-1+j)*n)+(n-i)] ; /* first half of bent_diagonal */
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int broken_top_bent_diag_sum(vector*a, int k, int n)
{
int i;
int sum=0;
for(i=0;i<k+1;i++)
sum = sum+ a->values[(n-k-1+i)*n + i] ; /* first half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum = sum+ a->values[(i-(k+1))*n + i];
for(i=0;i<k+1;i++)
sum = sum+ a->values[(n-k-1+i)*n+(n-i-1)]; /* second half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum = sum+ a->values[(i-(k+1))*n + (n-i-1)];
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int bottom_bent_diag_sum(vector*a, int j, int n)
{
int i;
int sum = 0;
for(i=0;i<(n/2);i++)
sum = sum+ a->values[n*(j-(i+1)) + i] ; /* first half of bent_diagonal */
for(i=0; i< (n/2); i++)
sum = sum+ a->values[n*(j-(i+1)) +(n-i-1)] ; /* first half of bent_diagonal */
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int broken_bottom_bent_diag_sum(vector*a, int k, int n)
{
int i;
int sum = 0;
for(i=0;i<k+1;i++)
sum = sum+ a->values[(k-i)*n+i] ; /* first half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum = sum+ a->values[(n-1-(i-k-1))*n+i] ;
for(i=0;i<k+1;i++)
sum = sum+ a->values[(k-i)*n +(n-i-1)] ; /* first half of bent_diagonal */
for(i=k+1;i<n/2;i++)
sum = sum+ a->values[(n-1-(i-k-1))*n+n-i-1];
if(sum == first_row_sum(n, a))
return 1;
else
return 0;
}
/*============== functions to create half-row and half-column sums ==========*/
int create_half_row_sum(vector* a, int j,int n) /*j th row, kth element */
{
int i;
int sum = 0;
for(i=0;i<n/2;i++)
sum = sum+ a->values[(j*n)+i];
if(2*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int create_half_col_sum(vector*a, int j,int n) /*j th col, kth element */
{
int i;
int sum = 0;
for(i=0;i<n/2;i++)
sum = sum+ a->values[i*n+j] ;
if(2*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
/*========= functions to compute 2x2 sub-squares sums ===========*/
int create_2x2_squares_sum(vector* a, int i,int j, int n) /*i th row, jth column */
{
int k,l,m;
int sum = 0;
for(l=0;l<2;l++){
for(k=0;k<2;k++)
sum = sum+ a->values[(i+l)*n+j+k] ;
}
if(n==8)
m=2;
if(n==16)
m=4;
if(m*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int create_broken_2x2_side_square_sum(vector*a, int i, int j, int n)
/* ith row , j th column */
{
int l,k,m;
int sum = 0;
for(l=0;l<n-j;l++){
for(k=0;k<2;k++)
sum = sum+ a->values[(i+k)*n+l+j] ;
}
for(l=0;l<2-(n-j);l++){
for(k=0;k<2;k++)
sum = sum+ a->values[(i+k)*n +l] ;
}
if(n==8)
m=2;
if(n==16)
m=4;
if(m*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int create_broken_2x2_bottom_square_sum(vector* a, int i, int j, int n)
/* ith row j th column */
{
int l,k,m;
int sum = 0;
for(l=0;l<n-i;l++){
for(k=0;k<2;k++)
sum = sum+a->values[(i+l)*n+k+j] ;
}
for(l=0;l<2-(n-i);l++){
for(k=0;k<2;k++)
sum = sum+ a->values[l*n +j+k] ;
}
if(n==8)
m=2;
if(n==16)
m=4;
if(m*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
int create_broken_2x2_bottom_and_side_square_sum(vector* a, int i, int j, int n)
/* ith row , jth column */
{
int k, l,m;
int sum = 0;
for(l=0;l<n-i;l++){
for(k=0;k<n-j;k++)
sum = sum+ a->values[(i+l)*n+j+k] ;
for(k=0;k<2-(n-j);k++)
sum = sum+ a->values[(i+l)*n+k] ;
}
for(l=0;l<2-(n-i);l++){
for(k=0;k<n-j;k++)
sum = sum+ a->values[l*n+j+k] ;
for(k=0;k<2-(n-j);k++)
sum = sum+ a->values[l*n+k] ;
}
if(n==8)
m=2;
if(n==16)
m=4;
if(m*sum == first_row_sum(n, a))
return 1;
else
return 0;
}
/*=====Function to check whether the square is a Franklin square ===========*/
void check_square(int n)
{
int i,j;
int check;
int size;
vector* a;
size = n*n;
a = get_vector_from_file(&size);
for(i=1; i<n; i++) /* Create row equations */
{
check = create_row_sum(a,i,n);
if(check == 0)
printf("Not a Franklin square, %d row sum does not match up \n", i+1);
}
for(i=0; i<n; i++) /* Create column equations */
{
check = create_col_sum(a,i,n);
if(check == 0)
printf("Not a Franklin square, %d column sum does not match up \n", i+1);
}
for(i=0; i<= (n/2); i++){ /* Create left_diagonal equations */
check = left_bent_diag_sum(a,i,n); /*create_left_bent_diagonal */
if(check == 0)
printf("Not a Franklin square, %d left_diagonal sum does not match up \n", i+1);
}
for(i=0; i< (n/2)-1; i++){ /*Create broken left_diagonal equations*/
check = broken_left_bent_diag_sum(a,i,n); /*create_left_bent_diagonal*/
if(check == 0)
printf("Not a Franklin square, %d broken_left_diagonalsum does not match up \n", i+1);
}
for(i=0; i<= (n/2); i++){
check = right_bent_diag_sum(a,i,n); /*create_right_bent_diagonal */
if(check == 0)
printf("Not a Franklin square, %d right_bend_diagonal sum does not match up \n", i+1);
}
for(i=0; i< (n/2)-1; i++){ /*Create broken right_diagonal equations*/
check = broken_right_bent_diag_sum(a,i,n); /*create_right_bent_diagonal*/
if(check == 0)
printf("Not a Franklin square, %d broken_right_bend_diagonal sum does not match up \n", i+1);
}
for(i=0; i<= (n/2); i++){
check = top_bent_diag_sum(a,i,n); /* create_top_diagonal*/
if(check == 0)
printf("Not a Franklin square, %d top_bend_diagonal sum does not match up \n", i+1);
}
for(i=0; i< (n/2)-1; i++){ /* Create broken top_diagonal equations*/
check = broken_top_bent_diag_sum(a,i,n); /* create_right_bent_diagonal*/
if(check == 0)
printf("Not a Franklin square, %d broken_top_diagonal sum does not match up \n", i+1);
}
for(i=n; i>= (n/2); i--){
check = bottom_bent_diag_sum(a,i,n); /* create_bottom_bent_diagonal*/
if(check == 0)
printf("Not a Franklin square, %d bottom_bend_diagonal sum does not match up \n", i+1);
}
for(i=0; i<(n/2)-1; i++){
check = broken_bottom_bent_diag_sum(a,i,n);
if(check == 0)
printf("Not a Franklin square, %d broken_bottom_bend_diagonal sum does not match up \n", i+1);
}
for(i=0; i<n; i++) /*Create half row equations */
{
check = create_half_row_sum(a,i,n);
if(check == 0)
printf("Not a Franklin square, %d half_row sum does not match up \n", i+1);
}
for(i=0; i<n; i++) /* Create col equations */
{
check = create_half_col_sum(a,i,n);
if(check == 0)
printf("Not a Franklin square, %d half_column sum does not match up \n", i+1);
}
for(i=0; i<= (n-2); i++) /*quarter squares*/
{
for(j=0; j<=(n-2) ; j++){
check = create_2x2_squares_sum(a,i,j,n);
if(check == 0)
printf("Not a Franklin square, %d quarter_sqaure sum does not match up \n", i+1);
}}
for(i=0; i<=(n-2); i++) /*Create broken quarter side square equations*/
{
for(j=(n-2+1);j<n;j++){
check = create_broken_2x2_side_square_sum(a,i,j,n);
if(check == 0)
printf("Not a Franklin square, %d broken_square sum does not match up \n", i+1);
}}
for(j=0; j<=(n-2); j++) /* Create broken quarter bottom square equations*/
{
for(i=(n-2+1);i<n;i++){
check = create_broken_2x2_bottom_square_sum(a,i,j,n);
if(check == 0)
printf("Not a Franklin square, %d broken_bottom_square sum does not match up \n", i+1);
}}
for(i=n-2+1;i<n; i++)
/*Create broken quarter bottom and side square equations*/
{
for(j=n-2+1;j<n;j++){
check = create_broken_2x2_bottom_and_side_square_sum(a,i,j,n);
if(check == 0)
printf("Not a Franklin square, %d broken_bottom_and_side square sum does not match up \n", i+1);
}}
}/* end of check_square function */
/*====================================================*/
int main( )
{
int n; /* nxn is size of square */
int size; /* size of vector */
scanf("%d",&n);
size = n*n;
printf("Starting test.........\n");
check_square(n);
printf("End of test: If you had no error messages, then Whoopee!\nYou have a Franklin square.\n");
return 0;
}/* end of main */