洛谷P1784 数独 题解

题目概述给定一个数独求最终填好的数独。保证有唯一解。思路拆分数独的要求有三个:行列九宫格无重复数字。我们只用dfs搜索每一个点就行了。由于整个数独可以划分为9个九宫格在处理九宫格时我们可以将其看作一个整体如下图1,11,21,32,22,22,33,13,23,3分析每个九宫格对应的下标后我们就可以发现若当前点坐标为i,j则它位于c[i/3][j/3]这个九宫格内。至于查重就更简单了把c开到三维第三维存数据。行、列处理很简单此处不再多说核心代码注释#includebits/stdc.husingnamespacestd;inta[10][10];boolh[10][10];//处理行booll[10][10];//处理列boolc[5][5][10];//处理九宫格vectorpairint,intb;boolcheck(intr,intx,inti){return!h[r][i]!l[x][i]!c[r/3][x/3][i];//检查当前位置是否可行}voiddfs(intidx){if(idx(int)b.size())//递归终止条件{for(inti0;i9;i){for(intj0;j9;j){couta[i][j] ;//输出}coutendl;}exit(0);//注意此处要直接退出不能用return,否则dfs会继续搜索其他分支}intrb[idx].first;intxb[idx].second;for(inti1;i9;i){if(check(r,x,i)){a[r][x]i;h[r][i]l[x][i]c[r/3][x/3][i]true;//假设填这个数dfs(idx1);a[r][x]0;h[r][i]l[x][i]c[r/3][x/3][i]false;//回溯}}}intmain(){for(inti0;i9;i){for(intj0;j9;j){cina[i][j];if(a[i][j]!0){h[i][a[i][j]]l[j][a[i][j]]c[i/3][j/3][a[i][j]]true;}else{b.push_back({i,j});}}}dfs(0);return0;}