前言
數獨相信很多人都玩過，趣味性很強，十分的耐玩。可有沒有程序員想過玩實現一個數獨布局的算法呢？算法是個很有意思，很神奇的東西。
算法如下，需要預先給出幾個固定的值，目前解決的一個最難的數獨是大概26個已知值的情況，理論上應該能解決任意已知值的數獨，不過不知道會不會迭代棧溢出……因為在26個已知值的情況下就迭代了3000多次了，囧~~~
結果顯示如下：
這是已知值:
|
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
|
1 1 21 4 8 1 5 51 6 11 7 71 8 32 1 12 2 62 4 43 5 93 7 83 8 44 7 95 8 76 1 36 6 86 7 46 8 67 3 77 6 47 7 18 3 38 6 79 3 49 4 69 7 39 8 2 |
（PS：如9 8 2表示第9行第二列的值是2）
將上面的數字保存到num.txt文件中,再把底下附的源代碼保存為Sudoku.java。
然后在cmd命令行模型下輸入：
|
1
2
|
javac Sudoku.java java Sudoku <num.txt |
即可得到結果。
這個解法是我之前看到八皇后排列問題的解法后結合應用的，在數獨中采用了這種解法，不過應該算是比較暴力的拆解，所以我后面命名成violentBreak。。。
雖然只是一個很小的事，但是能嘗試著用編程去解決日常遇到的事，突然覺得很開心，學以致用！
java源代碼：
|
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
|
import java.lang.System.*; import java.util.ArrayList; import java.util.Scanner; /**This class named Sudoku can auto calculate Sudoku but *you should input some nums which are already known. *For instance: *1 5 3 *2 4 7 *There two rows means [1][5]=3 [2][4]=7 *i.e. In row 1 col 5 is value:5 *you can write all known num into one txt file *and input into this program . *such as java Sudoku < num.txt */ /**代碼邏輯解析： * 1、建立一個9X9矩陣保存數獨正確的值 2、建立一個9X9列表，每個列表里保存著該位置，數獨可以填入的可能值 如ArrayList[1][1]={1,2,3}即1,1這個位置的數獨可能可以填入其中一個 當矩陣該位置已保存了正確值時，清空對應位置的ArrayList 3、當列表ArrayList里只有一個可能值時，那個值就是數獨的正確值，將該值填入數獨矩陣 并更新ArrayList PS：以上算法只能用于求困難級別的數獨，因為我在玩游戲的時候發現，每個時刻必定會有 一個數獨空位，是只能填入一個值的，所以這個算法才能運行 當一個數獨(即已知位置的值變少時)，可能會出現所有的空位都最起碼有兩個值時， 需要改進算法，通過代入來判斷這個數獨是否成立 4、于是后期我加入了暴力破解法，在上面的步驟執行后無法得出數獨，即使用暴力破解 * */ public class Sudoku{ //弄十的原因是為了好記憶，0,0不用，只用1-9的list private ArrayList<Integer>[][] availableNum=new ArrayList[10][10]; private int[][] correctNum=new int[10][10]; private Scanner scan=new Scanner(System.in); private int countNum=0; { for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ availableNum[i][j]=new ArrayList<>(); } } for(int row=1;row<10;row++){ for(int col=1;col<10;col++){ for(int i=1;i<10;i++) availableNum[row][col].add(new Integer(i)); } } //先都初始化為-1，即此時沒有填充數字 for(int i=0;i<10;i++) for(int j=0;j<10;j++) correctNum[i][j]=-1; } public Sudoku(){} //在對應數獨位置插入正確值 public void insert(int row,int col,int value){ correctNum[row][col]=value; availableNum[row][col]=null; delete(row,col,value); } //每插入一個數值，就刪除相應的行列和小框框3X3數獨里對應的ArrayList里可能的該值 public void delete(int row,int col,int value){ //delte row for(int i=1;i<10;i++){ if (availableNum[row][i]!=null) availableNum[row][i].remove(new Integer(value)); } //delete column for(int i=1;i<10;i++){ if (availableNum[i][col]!=null) availableNum[i][col].remove(new Integer(value)); } //delete box num int[] itsCenter=judgeCenterPos(row,col); for(int temp1=itsCenter[0]-1;temp1<=itsCenter[0]+1;temp1++) for(int temp2=itsCenter[1]-1;temp2<=itsCenter[1]+1;temp2++) if(availableNum[temp1][temp2]!=null){ availableNum[temp1][temp2].remove(new Integer(value)); } } //判斷插入的值時處于哪個小框框數獨里 public int[] judgeCenterPos(int row,int col){ int[] itsCenter=new int[2]; for(int centerRow=2;centerRow<9;centerRow+=3) for(int centerCol=2;centerCol<9;centerCol+=3){ if( Math.abs(row-centerRow)<=1 && Math.abs(col-centerCol)<=1 ){ itsCenter[0]=centerRow; itsCenter[1]=centerCol; return itsCenter; } } System.out.println("Some unchecked error was happened"); return itsCenter; } //判斷空格里所能填的數字是不是只能有一個,當返回-1時通過檢測報錯 public int[] judgeIfOnlyOne(){ for(int row=1;row<10;row++) for(int col=1;col<10;col++){ if(availableNum[row][col]!=null) if(availableNum[row][col].size()==1) return new int[]{row,col}; } return new int[]{-1,-1}; } // 判斷為唯一，但是空格里還有多于1個的數時，我們直接將哪個正確的值填入 public void insertIfCan(){ for(int row=1;row<=7;row+=3){ for(int col=1;col<=7;col+=3){ for(int z=1;z<10;z++){ int count=0; Integer temp=new Integer(z); int itemp=0,jtemp=0; outer: for(int i=row;i<row+3;i++){ for(int j=col;j<col+3;j++){ if(availableNum[i][j]!=null){ if(availableNum[i][j].contains(temp)){ count++; itemp=i; jtemp=j; if (count>1) break outer; } } } } if(count==1 && itemp!=0){ insert(itemp,jtemp,z); } } } } } //判斷數獨的矩陣是否填滿，沒有則繼續 public boolean judgeMatrixFull(){ for(int i=1;i<10;i++) for(int j=1;j<10;j++) if(correctNum[i][j]==-1) return false; return true; } //先輸入已知位置的數字 public void inputNumKnown(){ while(scan.hasNextInt()){ int row=scan.nextInt(); int col=scan.nextInt(); int value=scan.nextInt(); insert(row,col,value); delete(row,col,value); } } //打印數獨結果 public void printSudoku(){ printSudoku(correctNum); } public void printSudoku(int[][] arr){ System.out.println("Sudoku result:"); for(int i=1;i<10;i++){ for(int j=1;j<10;j++) System.out.print(arr[i][j]+" "); System.out.println(" "); } } public void printList(){ for(int i=1;i<10;i++) for(int j=1;j<10;j++){ System.out.print(i+" "+j+":"); if(availableNum[i][j]!=null) for(int z=0;z<availableNum[i][j].size();z++){ System.out.print(availableNum[i][j].get(z)+" "); } System.out.println(" "); } } //暴力破解 public void violentBreak(){ int i=1,j=1; outer: for(;i<10;i++) for(;j<10;j++) if(correctNum[i][j]!=-1) break outer; violentInsert(i,j,correctNum[i][j],correctNum); } public void violentInsert(int row,int col,int value,int[][] arr){ countNum++; int[][] tempMatrix=new int[10][10]; for(int i=1;i<10;i++) for(int j=1;j<10;j++) tempMatrix[i][j]=arr[i][j]; tempMatrix[row][col]=value; //不能insert的話說明填滿了 int[] insertPos=canInsert(tempMatrix); if(insertPos[0]==-1){ System.out.println("all insert is done.This is the last Sudoku:"); printSudoku(tempMatrix); return; } for(int val=1;val<=10;val++){ if(val==10){ tempMatrix=null; //讓JVM回收垃圾 //System.out.println("value=10 happened."); return; } if(judgeIfViolentInsert(insertPos[0],insertPos[1],val,tempMatrix)){ //System.out.println("insert happened."); violentInsert(insertPos[0],insertPos[1],val,tempMatrix); } } } public int[] canInsert(int[][] tempMatrix){ int[] pos={-1,-1}; for(int i=1;i<10;i++) for(int j=1;j<10;j++){ if(tempMatrix[i][j]==-1){ pos[0]=i; pos[1]=j; return pos; } } return pos; } public boolean judgeIfViolentInsert(int row,int col,int value,int[][] tempMatrix){ for(int j=1;j<10;j++) if(value==tempMatrix[row][j]) return false; for(int i=1;i<10;i++) if(value==tempMatrix[i][col]) return false; int[] itsCenter=judgeCenterPos(row,col); for(int temp1=itsCenter[0]-1;temp1<=itsCenter[0]+1;temp1++) for(int temp2=itsCenter[1]-1;temp2<=itsCenter[1]+1;temp2++) if(value==tempMatrix[temp1][temp2]) return false; return true; } //數獨開始運算的函數 public void start(){ int[] nextInsert=new int[2]; int count=0; this.inputNumKnown(); while(!judgeMatrixFull()){ nextInsert=judgeIfOnlyOne(); if(nextInsert[0]==-1){ this.insertIfCan(); count++; if(count==15){ System.out.println("Cannot fullfill this sodoku through finding the only one left."); System.out.println("count:"+count); break; } continue; } int value=availableNum[nextInsert[0]][nextInsert[1]].get(0); insert(nextInsert[0],nextInsert[1],value); } printSudoku(); //滿了就不用暴力破解了 if(judgeMatrixFull()) return; System.out.println("Now we should break this Sudoku by violent method."); violentBreak(); System.out.println("Recursion times:"+countNum); } public static void main(String[] args){ Sudoku test1=new Sudoku(); test1.start(); int[] a=new int[2]; System.out.println(a); System.out.println(a[0]); } } |
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
原文鏈接：http://blog.csdn.net/databatman/article/details/50726493
