//////////////////////////////////////////////////////////////////////////////
//
//  4. 在Ｎ行Ｎ列的数阵中, 数Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出现且仅
//  出现一次，这样的数阵叫Ｎ阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
//  编一程序，从键盘输入Ｎ值后，打印出所有不同的Ｎ阶拉丁方阵，并统计个数。
//
//        1  2  3  4  5
//        2  3  4  5  1
//        3  4  5  1  2
//        4  5  1  2  3
//        5  1  2  3  4
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#define  N  4

static int a[N][N], count;

bool legal(int row, int col)
{
    int i;
    for(i = 0; i < row; i++)
    {
        if(a[i][col] == a[row][col])
            return false;
    }
    for(i = 0; i < col; i++)
    {
        if(a[row][i] == a[row][col])
            return false;
    }
    return true;
}

void trial(int row, int col, FILE *fp)
{
    int i, j;
    if(row == N)
    {        
        printf("*********** %d **********\n", ++count);
        fprintf(fp, "*********** %d **********\n", count);
        for(i = 0; i < N; i++)
        {
            for(j = 0; j < N; j++)
            {
                printf("%5d", a[i][j]);
                fprintf(fp, "%5d", a[i][j]);
            }
            putchar(10);
            fputc(10, fp);
        }
    }
    for(i = 1; i <= N; ++i)
    {
        a[row][col] = i;
        if(legal(row, col))
            trial((row*N+col+1)/N, (row*N+col+1)%N, fp);
    }
}

void main()
{
    FILE *fp = fopen("latin.txt", "w");
    trial(0, 0, fp);
}

//////////////////////////////////////////////////////////////////////////////
//
// 11. 巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之
//     和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "math.h"

static used[21], link[21];
bool isprime(int a)
{
    for(int i = 2; i <= sqrt(a); i++)
    {
        if(!(a%i))
            return false;
    }
    return true;
}

void trace(int node)
{
    int i;
    if((node == 21) && isprime(link[20] + link[1]))
    {
        for(i = 1; i < 21; i++)
            printf("%4d", link[i]);
        putchar(10);
    }
    for(i = 1; i <= 20; i++)
    {
        if(!used[i])
        {
            link[node] = i;
            used[i] = 1;
            if(isprime(link[node]+link[node-1]))
                trace(node+1);
            used[i] = 0;
        }
    }
}

void main()
{
    trace(1);
}