回溯法解决Latin方格（每个数在每行每列只出现一次）

本文主要是介绍回溯法解决Latin方格（每个数在每行每列只出现一次），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

填入每一个数都是一层递归

使用k来把每一个数的二维数组坐标求出来：

    int row=(k-1)/n;int col=(k-1)%n;

完整代码： 

#include<iostream>
using namespace std;
const int N=1010;
int A[N][N],t[N];
int n,cnt;
bool judge(int row,int col)
{int t=A[row][col];//检查同一行有没有和它相等的值for(int j=0;j<n;j++)if(j!=col&&A[row][j]==t)return false;//检查同一列有没有相等的值for(int i=0;i<n;i++)if(i!=row&&A[i][col]==t)return false;return true;
}
void solve(int k)
{//从第0行0列开始,k=cnt+1//cnt从0开始，k从1开始
//    int row=cnt/n;
//    int col=cnt%n;int row=(k-1)/n;int col=(k-1)%n;for(int j=1;j<=n;j++){A[row][col]=j;if(judge(row,col)){if(k!=n*n){solve(k+1);}else if(k==n*n){if(A[0][0]==1&&A[0][1]==2&&A[0][2]==3){printf("--------找到一组解！-------\n");for(int p=0;p<n;p++){for(int q=0;q<n;q++)printf("%d ",A[p][q]);printf("\n");}cnt++;}}}A[row][col]=0;}
}
int main()
{cin>>n;solve(1);printf("共有%d组解\n",cnt);return 0;
}

运行结果(n=4，仅展示部分)：

这篇关于回溯法解决Latin方格（每个数在每行每列只出现一次）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---