题目描述
数独是一种传统益智游戏,你需要把一个9 × 9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
样例
输入样例:
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例:
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
算法1
(暴力枚举)
一般的做法:
1.每次随机挑个空白格子
2.枚举这个格子可以填哪些数
3.dfs
优化
1.优化搜索顺序,可以优先选择决策比较少的格子
每次判断当前格子可以放哪些数,我们可以用row[i], col[j], cell[i][j]
int
型数$2^9 -1$表示当前行列,小方格可以放哪些数。
用lowbit运算,计算int
型数中有几个1。
用map数组,可以返回当前的int
数 对应的九宫格数是多少, 比如int
型数 1000 = 8,map[1 << i] = i
表示3可以选择。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 9;
int ones[1 << N], map[1 << N];
int row[N], col[N], cell[3][3];
char str[100];
inline int lowbit(int x){
return x & -x;
}
void init(){
for (int i = 0; i < N; i ++) row[i] = col[i] = (1 << N) - 1;
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 3; j ++)
cell[i][j] = (1 << N) - 1;
}
inline int get(int x, int y){
return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt){
if (!cnt) return true;
int minv = 10;
int x, y;
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
if (str[i * 9 + j] == '.'){
int t = ones[get(i, j)];
if (t < minv){
minv = t;
x = i, y = j;
}
}
for (int i = get(x, y); i; i -= lowbit(i)){//找出x行y列里int数中的1
int t = map[lowbit(i)];//经过lowbit运算后,还需要进一步map
row[x] -= 1 << t;
col[y] -= 1 << t;
cell[x / 3][y / 3] -= 1 << t;
str[x * 9 + y] = '1' + t;
if (dfs(cnt - 1)) return true;
row[x] += 1 << t;
col[y] += 1 << t;
cell[x / 3][y / 3] += 1 << t;
str[x * 9 + y] = '.';
}
return false;
}
int main(){
for (int i = 0; i < N; i ++) map[1 << i] = i;
for (int i = 0; i < 1 << N; i ++){
int s = 0;
for (int j = i; j; j -= lowbit(j)) s ++;
ones[i] = s;
}
while (cin >> str, str[0] != 'e'){
init();
int cnt = 0;//cnt表示当前空着多少个数需要填写
for (int i = 0, k = 0; i < N; i ++)
for (int j = 0; j < N; j ++, k ++) //k表示当前枚举到样例中字符串第几个格子
if (str[k] != '.'){
int t = str[k] - '1';
row[i] -= 1 << t;
col[j] -= 1 << t;
cell[i / 3][j / 3] -= 1 << t;
}else cnt ++;
dfs(cnt);
cout << str << endl;
}
return 0;
}