用C怎么生成5＊5的矩阵，要求每行每列都填入1到5，而且每行每列不能重复数字，符合要求的矩阵有多少个，算法是什么？

用C怎么生成5＊5的矩阵，要求每行每列都填入1到5，而且每行每列不能重复数字，符合要求的矩阵有多少个，算法是什么？实在做不出来了，求援于牛人，要程序，能发到小弟邮箱最好：[e-mail]

7 个解决方案

#1

#include <stdio.h>

int mat[5][5];
int row_flag[5];
int col_flag[5];
int solution = 0;
void solve(int i, int j)
{
    int k;
    if (i == 5)
    {
        ++solution;
        return;
    }
    if (j == 5)
    {
        solve(i+1, 0);
        return;
    }
    for (k = 0; k < 5; ++k)
    {
        int f = 1 << k;
        if ((row_flag[i] & f) == 0 && (col_flag[j] & f) == 0)
        {
            mat[i][j] = k;
            row_flag[i] |= f;
            col_flag[j] |= f;
            solve(i, j + 1);
            row_flag[i] ^= f;
            col_flag[j] ^= f;
        }
    }
}
int main()
{
    solve(0, 0);
    printf("%d\n", solution);
    return 0;
}

#2

每行每列都不重复显然是一个5阶拉丁方
一共有5!种

#3

用回溯法,类似于八皇后,1楼不错啊

#4

引用 2 楼 shellcoder 的回复:

每行每列都不重复显然是一个5阶拉丁方
一共有5!种

答案显然不小于 5！ *  4！。

对于给定一组解，按列变换会产生 5！种不同的解。
对于这5！种解，对每组解后4行按行变换，产生4！组解。

所以解的个数是 5！*4！ * （4个a，3个bcde 16个字符组成的一个符合要求的4阶矩阵的解的个数）

基于这个原理，1 楼的算法复杂度可以降低5！*4！ =  2880倍。

其实我觉得这更像一个概率题，用笔划一划应该能算出结果。

#5

引用 4 楼 gumbour 的回复:

引用 2 楼 shellcoder 的回复:
每行每列都不重复显然是一个5阶拉丁方
一共有5!种


答案显然不小于 5！ *  4！。

对于给定一组解，按列变换会产生 5！种不同的解。
对于这5！种解，对每组解后4行按行变换，产生4！组解。

所以解的个数是 5！*4！ * （4个a，3个bcde 16个字符组成的一个符合要求的4阶矩阵的解的个数）

基于这个原理，1 楼的算法复杂度可以降低5！*4！ =  2880倍。

其实我觉得这更像一个概率题，用笔划一划应该能算出结果。

做一次行变换,再做一次列变换,有可能复合起来是恒等变换.

#6

引用 5 楼 baihacker 的回复:

引用 4 楼 gumbour 的回复:
引用 2 楼 shellcoder 的回复:
每行每列都不重复显然是一个5阶拉丁方
一共有5!种


答案显然不小于 5！ *  4！。

对于给定一组解，按列变换会产生 5！种不同的解。
对于这5！种解，对每组解后4行按行变换，产生4！组解。

所以解的个数是 5！*4！ * （4个a，3个bcde 16个字符组成的一个符合要求的4阶矩阵的解的个数）

基于这个原理，1 楼的算法复杂度可以降低5！*4！ =  2880倍。

其实我觉得这更像一个概率题，用笔划一划应该能算出结果。


做一次行变换,再做一次列变换,有可能复合起来是恒等变换.

假设有
11 12 13 14 15
21 X X X X
31 X X X X
41 X X X X
51 X X X X
对列进行任意变换，一共5！种，但是每一种 11所在的列顺序都是
11
21
31
41
51
所以对
21
31
41
51
4行进行任意行变换，会产生4！种组合，同时不会对列的5！种有任意影响。 
也就是说对5列和下面4行进行变换时独立事件，应该是乘法关系。

#7

把楼上的算法改了改，用N-1的结果* N！ * （N-1）！ 
两种算法对1，2，3，4，5都一样。
6阶的结果用快速算法是result = 812851200， 7阶估计要溢出了
原始的算法10分钟还没出结果，我先睡了，明天再看。



#include <stdio.h>

#define lll 5

#if 1

int mat[10][10];
int row_flag[10];
int col_flag[10];
int solution = 0;

void solve(int i, int j)
{
    int k;
    if (i == lll)
    {
        ++solution;
        return;
    }
    if (j == lll)
    {
        solve(i+1,0);
        return;
    }
    for (k = 0; k < lll; ++k)
    {
        int f = 1 << k;
        if ((row_flag[i] & f) == 0 && (col_flag[j] & f) == 0)
        {
            mat[i][j] = k;
            row_flag[i] |= f;
            col_flag[j] |= f;
            solve(i, j + 1);
            row_flag[i] ^= f;
            col_flag[j] ^= f;
        }
    }
}
int main()
{
    solve(0, 0);
    printf("result = %d\n", solution);
    return 0;
}

#else

int mat[10][10]={
0,1,2,3,4,5,6,7,8,9,
1,0,0,0,0,0,0,0,0,0,
2,0,0,0,0,0,0,0,0,0,
3,0,0,0,0,0,0,0,0,0,
4,0,0,0,0,0,0,0,0,0,
5,0,0,0,0,0,0,0,0,0,
6,0,0,0,0,0,0,0,0,0,
7,0,0,0,0,0,0,0,0,0,
8,0,0,0,0,0,0,0,0,0,
9,0,0,0,0,0,0,0,0,0};
int row_flag[10]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x100,0x200};
int col_flag[10]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x100,0x200};
int solution = 0;

void solve(int i, int j)
{
    int k;
    if (i == lll)
    {
++solution;
        return;
    }
    if (j == lll)
    {
        solve(i+1, 1);
        return;
    }
    for (k = 0; k < lll; ++k)
    {
        int f = 1 << k;
        if ((row_flag[i] & f) == 0 && (col_flag[j] & f) == 0)
        {
            mat[i][j] = k;
            row_flag[i] |= f;
            col_flag[j] |= f;
            solve(i, j + 1);
            row_flag[i] ^= f;
            col_flag[j] ^= f;
        }
    }
}
int main()
{
    solve(1, 1);
for (int i=2;i<lll;i++)
solution = solution *i*i;
solution *= lll;
    printf("result = %d\n", solution);
    return 0;
}
#endif