数独

ACM

本文将由浅入深的讲解数独的求解。

题目

poj2676 Sudoku
poj2918 Tudoku
爱数社面试题目，今天终于可以解决了，居然还是最简单的数独类型，当年太智障了。

题意

题解

运用深度优先搜索就行了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 10;
int mp[maxn][maxn];
int T;
bool stat1[maxn][maxn];//行的9个数字
bool stat2[maxn][maxn];//列的9个数字
bool stat3[maxn][maxn];//小块的9个数字
int sx, sy;
bool judge(int x, int y, int number)
{
    if(stat1[x][number] || stat2[y][number]) return false;
    if(stat3[3*int(x/3)+int(y/3)][number]) return false;
    return true;
}
bool dfs(int x, int y, int number){
    if(x == 9 && y == 0) return true;
    if(mp[x][y] != -1){
        if(dfs(int(x+int(y/8)), y==8?0:y+1, 1)) return true;
        return false;
    }
    for(int k=number; k<=9; k++){
        if(judge(x, y, k)){
            mp[x][y] = k;
            stat1[x][k] = stat2[y][k] = stat3[3*int(x/3)+int(y/3)][k] = true;
            if(dfs(int(x+(y==8?1:0)), y==8?0:y+1, 1)) return true;
            else{
                mp[x][y] = -1;
                stat1[x][k] = stat2[y][k] = stat3[3*int(x/3)+int(y/3)][k] = false;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d", &T);
    string number;
    int row = 0;
    for(int i=0; i<T; i++)
    {
        memset(stat1, 0, sizeof(stat1));
        memset(stat2, 0, sizeof(stat2));
        memset(stat3, 0, sizeof(stat3));
        row = 0;
        for(int m=0; m<9; m++){
            cin>>number;
            for(int j=0; j<9; j++){
                if(number[j] == '0'){
                    mp[row][j] = -1;
                }
                else{
                    mp[row][j] = number[j] - '0';
                }
            }
            row++;
        }
        bool flag_start = false;
        for(int j=0; j<9; j++){
            for(int k=0; k<9; k++){
                if(mp[j][k] == -1&&!flag_start){
                    sx = j, sy = k;
                    flag_start = true;
                    continue;
                }
                stat1[j][mp[j][k]] = true;
                stat2[k][mp[j][k]] = true;
                stat3[(j/3)*3+(k/3)][mp[j][k]] = true;
            }
        }
        for(int j=1; j<=9; j++){
            //printf("%d %d", sx, sy);
            if(dfs(sx, sy, j)){
                break;
            }
        }
        for(int j=0; j<9; j++){
            for(int k=0; k<9; k++){
                printf("%d", mp[j][k]);
            }
            printf("\n");
        }
    }
    return 0;
}

16·16的数独

运用的是跳舞链这种数据结构，当然还有的题解是运用了合理的寻找的策略，优先寻找那些选择个数少的格子，从而减小深度优先搜索的复杂度。
1309 - Sudoku

还没有完成的题目，只需要很小的剪枝就可以了。
poj3074

下面的代码是跳舞链来实现的，网上有很多这方面的教程，希望有时间多学一学吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// LA2659 Sudoku
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxr = 5000;
const int maxn = 2000;
const int maxnode = 20000;
// 行编号从1开始，列编号为1~n，结点0是表头结点; 结点1~n是各列顶部的虚拟结点
struct DLX {
  int n, sz; // 列数，结点总数
  int S[maxn]; // 各列结点数
  int row[maxnode], col[maxnode]; // 各结点行列编号
  int L[maxnode], R[maxnode], U[maxnode], D[maxnode]; // 十字链表
  int ansd, ans[maxr]; // 解
  void init(int n) { // n是列数
    this->n = n;
    // 虚拟结点
    for(int i = 0 ; i <= n; i++) {
      U[i] = i; D[i] = i; L[i] = i-1, R[i] = i+1;
    }
    R[n] = 0; L[0] = n;
    sz = n + 1;
    memset(S, 0, sizeof(S));
  }
  void addRow(int r, vector<int> columns) {
    int first = sz;
    for(int i = 0; i < columns.size(); i++) {
      int c = columns[i];
      L[sz] = sz - 1; R[sz] = sz + 1; D[sz] = c; U[sz] = U[c];
      D[U[c]] = sz; U[c] = sz;
      row[sz] = r; col[sz] = c;
      S[c]++; sz++;
    }
    R[sz - 1] = first; L[first] = sz - 1;
  }
  // 顺着链表A，遍历除s外的其他元素
  #define FOR(i,A,s) for(int i = A[s]; i != s; i = A[i]) 
  void remove(int c) {
    L[R[c]] = L[c];
    R[L[c]] = R[c];
    FOR(i,D,c)
      FOR(j,R,i) { U[D[j]] = U[j]; D[U[j]] = D[j]; --S[col[j]]; }
  }
  void restore(int c) {
    FOR(i,U,c)
      FOR(j,L,i) { ++S[col[j]]; U[D[j]] = j; D[U[j]] = j; }
    L[R[c]] = c;
    R[L[c]] = c;
  }
  // d为递归深度
  bool dfs(int d) {
    if (R[0] == 0) { // 找到解
      ansd = d; // 记录解的长度
      return true;
    }
    // 找S最小的列c
    int c = R[0]; // 第一个未删除的列
    FOR(i,R,0) if(S[i] < S[c]) c = i;
    remove(c); // 删除第c列
    FOR(i,D,c) { // 用结点i所在行覆盖第c列
      ans[d] = row[i];
      FOR(j,R,i) remove(col[j]); // 删除结点i所在行能覆盖的所有其他列
      if(dfs(d+1)) return true;
      FOR(j,L,i) restore(col[j]); // 恢复结点i所在行能覆盖的所有其他列
    }
    restore(c); // 恢复第c列
    return false;
  }
  bool solve(vector<int>& v) {
    v.clear();
    if(!dfs(0)) return false;
    for(int i = 0; i < ansd; i++) v.push_back(ans[i]);
    return true;
  }
};
////////////// 题目相关
#include<cassert>
DLX solver;
const int SLOT = 0;
const int ROW = 1;
const int COL = 2;
const int SUB = 3;
// 行/列的统一编解码函数。从1开始编号
int encode(int a, int b, int c) {
  return a*256+b*16+c+1;
}
void decode(int code, int& a, int& b, int& c) {
  code--;
  c = code%16; code /= 16;
  b = code%16; code /= 16;
  a = code;
}
char puzzle[16][20];
bool read() {
  for(int i = 0; i < 16; i++)
    if(scanf("%s", puzzle[i]) != 1) return false;
  return true;
}
int main() {
  int kase = 0;
  while(read()) {
    if(++kase != 1) printf("\n");
    solver.init(1024);
    for(int r = 0; r < 16; r++)
      for(int c = 0; c < 16; c++) 
        for(int v = 0; v < 16; v++)
          if(puzzle[r][c] == '-' || puzzle[r][c] == 'A'+v) {
            vector<int> columns;
            columns.push_back(encode(SLOT, r, c));
            columns.push_back(encode(ROW, r, v));
            columns.push_back(encode(COL, c, v));
            columns.push_back(encode(SUB, (r/4)*4+c/4, v));
            solver.addRow(encode(r, c, v), columns);
          }
    vector<int> ans;
    assert(solver.solve(ans));
    for(int i = 0; i < ans.size(); i++) {
      int r, c, v;
      decode(ans[i], r, c, v);
      puzzle[r][c] = 'A'+v;
    }
    for(int i = 0; i < 16; i++)
      printf("%s\n", puzzle[i]);
  }
  return 0;
}

未解决的问题

本文标题:数独

文章作者:Babydragon

发布时间:2018-02-28, 10:15:15

最后更新:2018-03-23, 13:32:26

原始链接:http://baolintian.github.io/2018/02/28/数独/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. AC代码
  2. 2. 16·16的数独
  3. 3. 未解决的问题
{{ live2d() }}