新浪博客

4 阶Latin 方问题

2009-01-15 12:29阅读：

http://blog.sina.cn/dpool/blog/u/1449786103

问题描述：
一个4 阶Latin 方是一个4×4 的方格，在它的每个方格内填入1,2,3 或者4，并使得每个数字在每行、每列都恰好出现一次。用回溯法求出所有第一行为1,2,3,4 的4阶Latin 方。将每个解的第2-4 行的数字从左到右写成一个序列。例如图中的Latin 方对应于解：<3,4,1,2,4,3,2,1,2,1,4,3>。
4 <wbr>阶Latin <wbr>方问题
算法实现：
#include <iostream.h>
int Latin[4][4];
int count = 0;
int IsOK(int r, int c, int v)
{
for(int i=0; i<r; i++)
if(Latin[i][c] == v)
return 0;
for(int j=0; j<c; j++)
if(Latin[r][j] == v)
return 0;
return 1;
}
void BackTrace(int l)
{
if(l == 17)
{//得到一组可行解

cout<<'可行解'<<++count<<': <';
for(int i=1; i<4; i++)
{
for(int j=0; j<4; j++)
{
cout<<Latin[i][j]<<', ';
}
}
cout<<'>'<<endl<<endl;
}
else
{
int r = (l-1)/4;
int c = (l-1)%4;
for(int j=1; j<=4; j++)
{
if(IsOK(r, c, j))
{
Latin[r][c] = j;
BackTrace(l+1);
}
}
}
}
void main()
{
for(int i=0; i<4; i++)
{
Latin[0][i] = i+1;
}
BackTrace(5);
cout<<'可行解总数：'<<count<<endl;
}

说明：上述代码是用于求解第一行为1234的拉丁方，共有24个可行解。如果要得到4阶拉丁方的所有可行解，只需在主函数中调用BackTrace(1)，最终结果有576个。

我的更多文章

下载客户端阅读体验更佳

APP专享