今天突發奇想，想做一個智能拼圖游戲來給哄女友。
需要實現這些功能
第一圖片自定義
第二宮格自定義，當然我一開始就想的是3*3 4*4 5*5，沒有使用3*5這樣的宮格。
第三要實現自動拼圖的功能，相信大家知道女人耍游戲都不是很厲害，所以這個自動拼圖功能得有。
其他什么暫停、排行就不寫了！
現在重點問題出來了
要實現自動拼圖功能似乎要求有點高哦！計算機有可不能像人一樣只能：
先追究下本質
拼圖游戲其實就是排列問題：
排列有這么一個定義：在一個1,2,...,n的排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。
再來一個定義：交換一個排列中的兩個數，則排列的奇偶性發生改變。
以上定義都摘自《高等代數》。
拼圖排列必須是偶排列。這個在我參考文獻中可以找到。
所以我的只能拼圖是這樣實現的！
后續在寫
參考：http://en.wikipedia.org/wiki/Fifteen_puzzle
自動拼圖：
首先自動拼圖應該有一定的規則，根據我拼圖的經驗，要完成拼圖，不同區域使用的拼圖規則是不同的，所以：
我的宮格圖分為了4個區域（假如宮格圖是n*n個格子）
第一個區域：x坐標范圍 0到n-2，y坐標范圍 0到n-3
第二個區域：x坐標n-1，y坐標范圍 0到n-3
第三個區域：x坐標范圍 0到n-3 ，y坐標范圍 n-2和n-1
第四個區域：x坐標范圍 n-2到n-1 ，y坐標范圍 n-2和n-1；即最后四格
每個區域按照各自區域的規則即可完成
Puzzle.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
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
|
import java.io.FileNotFoundException;import java.io.PrintStream;import java.io.UnsupportedEncodingException;import java.util.Random; public class Puzzle { private long step = 0; private int n = 6;// 宮格基數 private int[][] puzzle; private int resetBlock = 0;// //空白塊位置 private int whiteBlockX; private int whiteBlockY; //當前要準備移動的塊的坐標即復位塊 private int resetBlockX; private int resetBlockY; private boolean isPrint=false; public Puzzle() { init(); } public Puzzle(int n) { this.n = n; init(); } private void init() { puzzle = new int[n][n]; for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { puzzle[y][x] = x + y * n; } } whiteBlockX = n-1; whiteBlockY = n-1; int times = 100;// 打亂次數，必須是偶數 Random random = new Random(); while (times > 0) { int x0 = random.nextInt(n); int y0 = random.nextInt(n); int x1 = random.nextInt(n); int y1 = random.nextInt(n); if (x0 != x1 && y0!=y1) {// 保證是偶排序 if((x0==n-1&&y0==n-1)||(x1==n-1&&y1==n-1)){//最后一個不調換 continue; } times--; int t = puzzle[x0][y0]; puzzle[x0][y0] = puzzle[x1][y1]; puzzle[x1][y1] = t; } }// int[][] p = {{22,9 ,1 ,5 ,0 ,25 },{// 33,23,20,26,18,21},{// 6 ,16,17,10,34,31},{// 19,28,32,7 ,3 ,2},{// 11,4 ,12,14,27,24},{// 15,29,30,8 ,13,35}};// puzzle = p; } public void sort(){ for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { if (x == n - 1 && y == n - 1) {// 最后一個為空白, } else { reset(x, y); } } } } //把塊復位移動目標位置 private void reset(int targetX, int targetY) { // 找到復位塊當前的位置 initResetBlock(targetX, targetY); /* * 復位順序是從左到右，從上到下 * 移動方式 先上移動，再左移動 * 當前復位塊，它要復位的位置可分為 四種情況 * 1、不在最右邊一行也不是最下面兩行 * 2、最右邊一行 x=n-1，但不是下面兩行; * 3、最下面兩行 y=n-2，但不是最右邊一行; * 4、即使最右邊的一行也是最下面兩行 */ if(targetX < n-1 && targetY < n-2){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } resetBlockToTarget(targetX, targetY); }else if(targetX==n-1 && targetY < n-2){//第二種情況 if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } reset2(targetX, targetY); }else if(targetX < n-2 && targetY == n-2){// isPrint=true; reset3(targetX); return; }else{ initResetBlock(n-2, n-2); resetBlockToTarget(n-2, n-2); if(whiteBlockX<n-1){ whiteBlockRight(); } if(whiteBlockY<n-1){ whiteBlockDown(); } if(whiteBlockX==n-1&&whiteBlockY==n-1){ return; } } reset(targetX, targetY);//遞歸 } private void initResetBlock(int targetX,int targetY){ resetBlock = targetX + targetY * n; for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { if (puzzle[y][x] == resetBlock) {// x,y就是復位塊的位置 resetBlockX = x; resetBlockY = y; break; } } } } private void reset3(int targetX){// if(targetX>=2){// } initResetBlock(targetX, n-1); resetBlockToTarget(targetX, n-2); initResetBlock(targetX, n-2); resetBlockToTarget(targetX+1, n-2); l: while (!(whiteBlockX==targetX && whiteBlockY==n-1)) { if(whiteBlockY<n-1){ whiteBlockDown(); continue l; } if(whiteBlockX>targetX){ whiteBlockLeft(); continue l; } break; } whiteBlockUp(); swapWhiteBlockAndCurrentBlock(); if(puzzle[n-2][targetX]!=resetBlock||puzzle[n-1][targetX]!=(resetBlock+n)){//沒有復位成功// isPrint=true; swapWhiteBlockAndCurrentBlock(); reset3_0(); reset3(targetX); } } private void reset3_0(){ if(resetBlockX<n-1){ whiteBlockDown(); whiteBlockRight(); whiteBlockRight(); whiteBlockUp(); swapWhiteBlockAndCurrentBlock(); reset3_0(); return; } return; } private void reset2_3(){ if(whiteBlockX==resetBlockX && whiteBlockY==resetBlockY+1){ return;//滿足條件，退出遞歸 } //白塊可能在復位塊的：左方、左下、下方 if(whiteBlockY==resetBlockY){//左方 whiteBlockDown(); }else if(whiteBlockX < resetBlockX){//左下 whiteBlockRight(); }else { whiteBlockUp(); } reset2_3();//遞歸 } private void reset2_2(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//2、把復位塊移到目標位置正下方 return;//退出遞歸 } //復位塊可能位置，目標位置左方、正下方、左下方 if(resetBlockX==targetX){//正下方 上移 resetBlockUp(targetX, targetY); }else{//左方或左下方；先右移再上移 resetBlockRight(targetX, targetY); } reset2_2(targetX, targetY);//遞歸 } private void reset2(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } /* 1、如果白塊正好占了目標位置：如果復位塊正好在下方，交換及完成復位，如果下方不是復位塊，把白塊移開目標位置 * 2、把復位塊移到目標位置正下方 * 3、把白塊移動復位塊下方 * 4、按照規定的步驟復位 */ //第一步 if(whiteBlockX==targetX&& whiteBlockY==targetY){ if(whiteBlockX==resetBlockX&&whiteBlockY==resetBlockY+1){//復位塊在下方 swapWhiteBlockAndCurrentBlock(); return; }else{ whiteBlockDown(); } } //第二步 把復位塊移到目標位置正下方 reset2_2(targetX, targetY+1); //第三步 把白塊移動復位塊下方 reset2_3(); //第四步 按照規定的步驟復位 swapWhiteBlockAndCurrentBlock(); whiteBlockLeft(); whiteBlockUp(); whiteBlockRight(); whiteBlockDown(); whiteBlockLeft(); whiteBlockUp(); whiteBlockRight(); whiteBlockDown(); swapWhiteBlockAndCurrentBlock(); whiteBlockLeft(); whiteBlockUp(); whiteBlockUp(); whiteBlockRight(); swapWhiteBlockAndCurrentBlock(); } private void resetBlockToTarget(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } if(resetBlockY==targetY){//正左 resetBlockLeft(targetX, targetY); }else{//左下，下，右下 if(resetBlockX>=targetX){//右下||下；上移 if(resetBlockX==n-1){//復位塊在最右邊，先左移；方便上移時統一的采用白塊逆時針方式 resetBlockLeft(targetX, targetY); }else{ resetBlockUp(targetX, targetY); } }else{//左下；右移 resetBlockRight(targetX, targetY); } } resetBlockToTarget(targetX, targetY);//遞歸 } private void resetBlockRight(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } if(resetBlockX==n-1){//復位塊在最右邊了，無法右移，直接退出 return; }// System.out.println("resetBlockRight"); if(whiteBlockY<resetBlockY){//上方 if(whiteBlockY<resetBlockY-1){//上方多行 whiteBlockDown(); }else{//上方一行 if(whiteBlockX<resetBlockX+1){//左上和正上 whiteBlockRight(); }else{//右上 whiteBlockDown(); } } }else if(whiteBlockY==resetBlockY){//同一行 if(whiteBlockX<resetBlockX){//左方 if(whiteBlockY==n-1){//到底了，只能往上 whiteBlockUp(); }else{ whiteBlockDown(); } }else{//右方 if(whiteBlockX==resetBlockX+1){ swapWhiteBlockAndCurrentBlock(); return;//退出遞歸 }else{ whiteBlockLeft(); } } }else{//下方 if(whiteBlockX <= resetBlockX){//左下、下 whiteBlockRight(); }else{//右下 whiteBlockUp(); } } resetBlockRight(targetX, targetY);//遞歸 } private void resetBlockLeft(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } if(resetBlockX==0){//在左邊邊界 復位塊無法左移，直接退出遞歸 return; }// System.out.println("resetBlockLeft"); if(whiteBlockY<resetBlockY){//上方 if(whiteBlockY<resetBlockY-1){//上方多行 whiteBlockDown(); }else{//上方一行 if(whiteBlockX==resetBlockX){//上方 if(whiteBlockX==n-1){//最右邊，白塊無法右移，只能左移 whiteBlockLeft(); }else{ if(resetBlockY==n-1){//復位塊在最低端，白塊不能順時針移動 whiteBlockLeft(); }else{ whiteBlockRight(); } } }else if(whiteBlockX>resetBlockX){//右上方 if(resetBlockY==n-1){//復位塊在最低端，白塊不能順時針移動 whiteBlockLeft(); }else{ whiteBlockDown(); } }else{//左上方 whiteBlockDown(); } } }else if(whiteBlockY==resetBlockY){//左方、右方 if(whiteBlockX<resetBlockX){//左方 if(whiteBlockX==resetBlockX-1){//左邊一格 swapWhiteBlockAndCurrentBlock();//退出遞歸 return; }else{ whiteBlockRight(); } }else{//右方 if(whiteBlockY==n-1){//到底了，不能下移。只能上移 whiteBlockUp(); }else{ whiteBlockDown(); } } }else{//左下、下方、右下 if(whiteBlockX<resetBlockX){//左下 if(whiteBlockX==resetBlockX-1){ whiteBlockUp(); }else{ whiteBlockRight(); } }else{//下方、右下 whiteBlockLeft(); } } resetBlockLeft(targetX, targetY);//遞歸 } private void resetBlockUp(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動 return;//退出遞歸 } if(resetBlockY==0){//復位塊到頂了，無法上移 return; }// System.out.println("resetBlockUp"); if (whiteBlockY < resetBlockY) {//上方 if(whiteBlockY < resetBlockY - 1){//上方多行 whiteBlockDown(); }else{//上方一行 if(whiteBlockX == resetBlockX){//白塊和復位塊在同一列（豎列） 白塊和復位塊直接交換位置 swapWhiteBlockAndCurrentBlock();//退出遞歸 return; }else{ if(whiteBlockX<resetBlockX){//白塊在復位塊的左邊；白塊右移 whiteBlockRight(); }else{//白塊在復位塊的右邊；白塊左移 whiteBlockLeft(); } } } } else if (whiteBlockY == resetBlockY) {//白塊和復位塊同一行；白塊上移 if(whiteBlockX<resetBlockX){//正左 if(whiteBlockX<resetBlockX-1){//正左多格 whiteBlockRight(); }else{//正左一格 if(whiteBlockY==n-1){//到底了 whiteBlockUp(); }else { if(resetBlockX==n-1){//復位塊在最右邊，無法逆時針,只有順指針移動白塊 whiteBlockUp(); }else{ whiteBlockDown(); } } } }else{//正右 whiteBlockUp(); } }else{//白塊在復位塊下方，白塊需要饒過復位塊上移,白塊逆時針繞到白塊上面 //三種情況：左下，下，右下 if(whiteBlockX<=resetBlockX){//左下，下；白塊右移 if(resetBlockX==n-1){//復位塊在最右邊，無法逆時針,只有順指針移動白塊 if(whiteBlockX==resetBlockX){//正下方 whiteBlockLeft(); }else{//左下方 whiteBlockUp(); } }else{ whiteBlockRight(); } }else{//右下；白塊上移 whiteBlockUp(); } } resetBlockUp(targetX, targetY);//遞歸 } //白塊和復位塊交換位置 private void swapWhiteBlockAndCurrentBlock(){ step++; int tempX = whiteBlockX,tempY = whiteBlockY; int temp = puzzle[whiteBlockY][whiteBlockX]; puzzle[whiteBlockY][whiteBlockX] = puzzle[resetBlockY][resetBlockX]; puzzle[resetBlockY][resetBlockX] = temp; whiteBlockX = resetBlockX; whiteBlockY = resetBlockY; resetBlockX = tempX; resetBlockY = tempY; println("swap"); } private void whiteBlockDown(){ step++; int temp = puzzle[whiteBlockY][whiteBlockX]; puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY+1][whiteBlockX]; puzzle[whiteBlockY+1][whiteBlockX] = temp; whiteBlockY++; println("↓"); } private void whiteBlockUp(){ step++; int temp = puzzle[whiteBlockY][whiteBlockX]; puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY-1][whiteBlockX]; puzzle[whiteBlockY-1][whiteBlockX] = temp; whiteBlockY--; println("↑"); } private void whiteBlockLeft(){ step++; int temp = puzzle[whiteBlockY][whiteBlockX]; puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY][whiteBlockX-1]; puzzle[whiteBlockY][whiteBlockX-1] = temp; whiteBlockX--; println("←"); } private void whiteBlockRight(){ step++; int temp = puzzle[whiteBlockY][whiteBlockX]; puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY][whiteBlockX+1]; puzzle[whiteBlockY][whiteBlockX+1] = temp; whiteBlockX++; println("→"); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("resetBlock=("+resetBlock+","+resetBlockX+","+resetBlockY+")\n"); if(puzzle!=null){ int len = String.valueOf(n*2-1).length(); for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { if(x>0){ sb.append(","); } sb.append(_str(String.valueOf(puzzle[y][x]), len)); } sb.append("\n"); } sb.append("---------------------------------------"); }else{ sb.append("puzzle is null"); } return sb.toString(); } private String _str(String str,int len){ str=str==null?"":str; if(str.length()<len){ return _str(str+" ", len); } return str; } private void println(String str){ if(isPrint){ System.out.println(str); System.out.println(this); } } public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {// System.setOut(new PrintStream("e:/puzzle.txt","UTF-8")); Puzzle p = new Puzzle(); System.out.println(p); try { p.sort(); } catch (Exception e) { e.printStackTrace(); System.out.println("Exception:"); }finally{ System.out.println(p); } }} |
以上所述就是本文的全部內容了，希望大家能夠喜歡。
