經典數獨題，2014年的時候用當年ACM的數獨模板交過一次，RE（估計是MLE），2022再用一樣代碼交，AC了而且速度比96.66%的CPP代碼快
用Python又做了一遍，純DFS，判斷當前局面的方法借鑒了Discussion中的簡潔寫法（用set）
Python版：
1 #37
2 #Runtime: 351 ms
3 #Memory Usage: 13.5 MB
4
5 class Solution(object):
6
7 possible = set(str(i) for i in range(1, 10))
8
9 def findEmptyCell(self):
10 for r in range(len(self.board)):
11 for c in range(len(self.board[0])):
12 if self.board[r][c] == '.':
13 return r, c, False
14 return -1, -1, True
15
16
17 def checkBoard(self, r, c):
18 return self.possible - self.getBox(r, c) - self.getRow(r, c) - self.getCol(r, c)
19
20
21 def getBox(self, r, c):
22 res = set()
23 for i in range(r // 3 * 3, r // 3 * 3 + 3):
24 res.update(self.board[i][c // 3 * 3 : c // 3 * 3 + 3])
25 return res
26
27
28 def getRow(self, r, c):
29 return set(self.board[r])
30
31
32 def getCol(self, r, c):
33 return set([row[c] for row in self.board])
34
35
36 def DFS(self):
37 r, c, fin = self.findEmptyCell()
38 if fin:
39 return True
40 candidate_nums = self.checkBoard(r, c)
41 if not candidate_nums:
42 return False
43 for num in candidate_nums:
44 self.board[r][c] = num
45 if self.DFS():
46 return True
47 self.board[r][c] = '.'
48 return False
49
50
51 def solveSudoku(self, board):
52 """
53 :type board: List[List[str]]
54 :rtype: None Do not return anything, modify board in-place instead.
55 """
56 self.board = board
57 self.DFS()
C++版：
1 #37
2 #Runtime: 7 ms
3 #Memory Usage: 13 MB
4
5 class Solution {
6 public:
7 #define INF 0x7fffffff
8 #define maxn 330
9 #define maxm 740
10
11 int l[maxn*maxm],r[maxn*maxm],u[maxn*maxm],d[maxn*maxm],ch[maxn*maxm],s[maxn];
12 int ans[10][10],adj[maxm][maxn];
13 int head, n, m;
14
15 void remove(const int &c){
16 l[r[c]]=l[c];
17 r[l[c]]=r[c];
18 for(int i=d[c];i!=c;i=d[i]){
19 for(int j=r[i];j!=i;j=r[j]){
20 u[d[j]]=u[j];
21 d[u[j]]=d[j];
22 s[ch[j]]--;
23 }
24 }
25 }
26
27 void resume(const int &c){
28 for(int i=d[c];i!=c;i=d[i]){
29 for(int j=r[i];j!=i;j=r[j]){
30 s[ch[j]]++;
31 u[d[j]]=j;
32 d[u[j]]=j;
33 }
34 }
35 l[r[c]]=c;
36 r[l[c]]=c;
37 }
38
39 int Build(){
40 int i,j,pre,cur,st;
41 head=0;
42 for(j=head;j<n;j++){
43 r[j]=j+1;
44 l[j+1]=j;
45 }
46 l[head]=j;
47 r[j]=head;
48 //column
49 for(j=1;j<=n;j++){
50 pre=j;
51 s[j]=0;
52 for(i=1;i<=m;i++){
53 if(adj[i][j]){
54 cur=n*i+j;
55 ch[cur]=j;
56 s[j]++;
57 d[pre]=cur;
58 u[cur]=pre;
59 pre= cur;
60 }
61 }
62 cur=j;
63 d[pre]=cur;
64 u[cur]=pre;
65 if(!s[j])return 0;
66 }
67 //row
68 for(i=1;i<=m;i++){
69 pre=st=-1;
70 for(j=1;j<=n;j++){
71 if(adj[i][j]){
72 cur=i*n+j;
73 if(pre!=-1){
74 r[pre]=cur;
75 l[cur]=pre;
76 }
77 else
78 st=cur;
79 pre=cur;
80 }
81 }
82 if(st!=-1){
83 cur=st;
84 r[pre]=cur;
85 l[cur]=pre;
86 }
87 }
88 return 1;
89 }
90
91 bool DFS(){
92 if(r[head]==head)return true;
93 int c,i,j;
94 int ss=INF;
95 for(int t=r[head];t!=head;t=r[t]){
96 if(s[t]<ss){
97 ss=s[t];
98 c=t;
99 }
100 }
101 remove(c);
102 for(i=d[c];i!=c;i=d[i]){
103 int t1=(i-1)/n;
104 int n1=(t1+8)/9;
105 int k1=t1%9;
106 if(!k1)k1=9;
107 int x=(n1+8)/9;
108 int y=n1%9;
109 if(!y)y=9;
110 ans[x][y]=k1;
111 for(j=r[i];j!=i;j=r[j])remove(ch[j]);
112 if(DFS())return true;
113 for(j=l[i];j!=i;j=l[j])resume(ch[j]);
114 }
115 resume(c);
116 return false;
117 }
118
119 void solveSudoku(vector<vector<char> > &board) {
120 memset(adj, 0, sizeof(adj));
121 for(int i = 1; i <= 9; i++){
122 for(int j = 1; j <= 9; j++){
123 int tmp = 9 * (i - 1) + j;
124 if(board[i - 1][j - 1] == '.'){
125 for(int k = 1; k <= 9; k++){
126 adj[9*(tmp-1)+k][tmp]=1;
127 adj[9*(tmp-1)+k][81+(i-1)*9+k]=1; //row
128 adj[9*(tmp-1)+k][162+(j-1)*9+k]=1; //col
129 adj[9*(tmp-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k]=1; //grid
130 }
131 }
132 else{
133 int k = board[i - 1][j - 1] - '0';
134 adj[9*(tmp-1)+k][tmp]=1;
135 adj[9*(tmp-1)+k][81+(i-1)*9+k]=1; //row
136 adj[9*(tmp-1)+k][162+(j-1)*9+k]=1; //col
137 adj[9*(tmp-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k]=1; //grid
138 }
139 }
140 }
141 m=729;
142 n=324;
143 Build();
144 if(DFS()) {
145 for(int i = 1; i <= 9; i++){
146 for(int j = 1; j <= 9; j++){
147 board[i - 1][j - 1] = ans[i][j] + '0';
148 }
149 }
150 }
151 }
152 };