问题描述：
如图所示，一个4阶Latin方是一个4X4的方格，在它的每个方格内填入1,2,3或4，并使得每个数字在每行、每列都恰好出现一次。用回溯法求出所有第一行为1,2,3,4的所有4阶Latin方。将每个解的第2行到第4行的数字从左到右写成一个序列。如图中的解是<3,4,1,2,4,3,2,1,2,1,4,3>。
| 1 | 2 | 3 | 4 |
| 3 | 4 | 1 | 2 |
| 4 | 3 | 2 | 1 |
| 2 | 1 | 4 | 3 |
本打算随便弄几行代码应付上去，没想到最后给编出来了。回溯算法思想以及实现过程都不是太难。
个人觉得比较重要的部分是递归函数中的for循环，即分别对每个小格每种颜色都做一次尝试，成功就尝试下一个格，否则就换一种颜色，再不行（即这一个格不能涂上合适的颜色）就直接退出递归程序，回到上一层递归。
程序清单：
#include<iostream> #define MAX 4 using std::cin; using std::cout; using std::endl; bool LatinCheck(int x[MAX][MAX],int k,int row,int line) { for(int i=0;i<row;i++) if(x[i][line] == k) return false; for(int i=0;i<line;i++) if(x[row][i] == k) return false; return true; } void LatinMartix(int x[MAX][MAX],int row,int line) { if((row==4)&&(line==4)) return; for(int color=0;color<4;color++) { if(LatinCheck(x,color,row,line)) { x[row][line] = color; if(line<3) LatinMartix(x,row,line+1); else if((line == 3)&&(row!=3)) LatinMartix(x,row+1,0); } } if((line==3)&&(row==3)) { for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { cout << x[i][j]+1 << " "; } } cout << endl; return; } } int main() { int x[MAX][MAX]={0,1,2,3}; LatinMartix(x,1,0); return 0; }
原文：http://www.cnblogs.com/xh-wildgoose/p/4992712.html