又是我，又要更一道水题，就是关于dfs的数独问题。
这道题没有题面，反正就是给你一个没有补全的数独，要你输出以此为基础的任意一种正确数独。
好吧来分析一下。
一行不重复那么用一个数组vl[i][j]表示第i行j数字有没有用过
一列不重复那么用一个数组vr[i][j]表示第i列j数字有没有用过
还有要考虑同一单元格里不重复，此时设vid[i][j]表示单元格i号里面j数字有没有用过。
难点：
给出x，y如何知道处于那个单元格，这个推一下就行了
int get_id(int x, int y) { int l = ceil(1.0 * y / 3); int r = ceil(1.0 * x / 3); return (l - 1) * 3 + r; }
然后dfs，每个人都有不一样的dfs方式吧
大概框架就是 （满足）-》 exit
循环遍历看看该位置能放什么
放进去更新
拿出来回溯
#include <bits/stdc++.h> using namespace std; int g[10][10]; int vid[10][10]; //i ge li de shu zi j int vl[10][10], vr[10][10]; //l->line r->row; void in() { for (int i = 1;i <= 9;++i) { for (int j = 1;j <= 9;++j) { char c; cin >> c; if (isdigit(c)) { g[i][j] = c - ‘0‘; } } } } int get_id(int x, int y) { int l = ceil(1.0 * y / 3); int r = ceil(1.0 * x / 3); return (l - 1) * 3 + r; } void init() { for (int i = 1;i <= 9;++i) { for (int j = 1;j <= 9;++j) { int id = get_id(i, j); int num = g[i][j]; if (num) { vid[id][num] = 1; vl[i][num] = 1; vr[j][num] = 1; } } } } void print() { for (int i = 1;i <= 9;++i) { for (int j = 1;j <= 9;++j) { printf("%d ", g[i][j]); } printf("\n"); } } bool check() { for (int i = 1;i <= 9;++i) { for (int j = 1;j <= 9;++j) { if (g[i][j] == 0) { return 0; } } } return 1; } void dfs(int x, int y) { if (x == 10) { ++y; x = 1; if (y == 10) { if (check()) { print(); exit(0); } return; } } if (g[x][y]) { dfs(x + 1, y); } else { for (int n = 1;n <= 9;++n) { int id = get_id(x, y); if (vl[x][n] || vr[y][n] || vid[id][n]) { continue; } g[x][y] = n; vl[x][n] = vr[y][n] = vid[id][n] = 1; dfs(x + 1, y); g[x][y] = 0; vl[x][n] = vr[y][n] = vid[id][n] = 0; } } } int main() { freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); in(); init(); dfs(1, 1); }
//这里的输入就是 类似与 9 * * 1 * *8 * 3
...
*表示单元格元素未知。
原文：https://www.cnblogs.com/Sikonihigh/p/14394533.html