前言
数独相信很多人都玩过，趣味性很强，十分的耐玩。可有没有程序员想过玩实现一个数独布局的算法呢？算法是个很有意思，很神奇的东西。
算法如下，需要预先给出几个固定的值，目前解决的一个最难的数独是大概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
