今天突發(fā)奇想，想做一個智能拼圖游戲來給哄女友。
需要實現(xiàn)這些功能
第一圖片自定義
第二宮格自定義，當(dāng)然我一開始就想的是3*3 4*4 5*5，沒有使用3*5這樣的宮格。
第三要實現(xiàn)自動拼圖的功能，相信大家知道女人耍游戲都不是很厲害，所以這個自動拼圖功能得有。
其他什么暫停、排行就不寫了！
現(xiàn)在重點問題出來了
要實現(xiàn)自動拼圖功能似乎要求有點高哦！計算機(jī)有可不能像人一樣只能：
先追究下本質(zhì)
拼圖游戲其實就是排列問題：
排列有這么一個定義：在一個1,2,...,n的排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。逆序數(shù)為偶數(shù)的排列稱為偶排列；逆序數(shù)為奇數(shù)的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數(shù)是4，為偶排列。
再來一個定義：交換一個排列中的兩個數(shù)，則排列的奇偶性發(fā)生改變。
以上定義都摘自《高等代數(shù)》。
拼圖排列必須是偶排列。這個在我參考文獻(xiàn)中可以找到。
所以我的只能拼圖是這樣實現(xiàn)的！
后續(xù)在寫
參考：http://en.wikipedia.org/wiki/Fifteen_puzzle
自動拼圖：
首先自動拼圖應(yīng)該有一定的規(guī)則，根據(jù)我拼圖的經(jīng)驗，要完成拼圖，不同區(qū)域使用的拼圖規(guī)則是不同的，所以：
我的宮格圖分為了4個區(qū)域（假如宮格圖是n*n個格子）
第一個區(qū)域：x坐標(biāo)范圍 0到n-2，y坐標(biāo)范圍 0到n-3
第二個區(qū)域：x坐標(biāo)n-1，y坐標(biāo)范圍 0到n-3
第三個區(qū)域：x坐標(biāo)范圍 0到n-3 ，y坐標(biāo)范圍 n-2和n-1
第四個區(qū)域：x坐標(biāo)范圍 n-2到n-1 ，y坐標(biāo)范圍 n-2和n-1；即最后四格
每個區(qū)域按照各自區(qū)域的規(guī)則即可完成
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;// 宮格基數(shù) private int[][] puzzle; private int resetBlock = 0;// //空白塊位置 private int whiteBlockX; private int whiteBlockY; //當(dāng)前要準(zhǔn)備移動的塊的坐標(biāo)即復(fù)位塊 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;// 打亂次數(shù)，必須是偶數(shù) 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)){//最后一個不調(diào)換 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); } } } } //把塊復(fù)位移動目標(biāo)位置 private void reset(int targetX, int targetY) { // 找到復(fù)位塊當(dāng)前的位置 initResetBlock(targetX, targetY); /* * 復(fù)位順序是從左到右，從上到下 * 移動方式 先上移動，再左移動 * 當(dāng)前復(fù)位塊，它要復(fù)位的位置可分為 四種情況 * 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就是復(fù)位塊的位置 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)){//沒有復(fù)位成功// 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;//滿足條件，退出遞歸 } //白塊可能在復(fù)位塊的：左方、左下、下方 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、把復(fù)位塊移到目標(biāo)位置正下方 return;//退出遞歸 } //復(fù)位塊可能位置，目標(biāo)位置左方、正下方、左下方 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、如果白塊正好占了目標(biāo)位置：如果復(fù)位塊正好在下方，交換及完成復(fù)位，如果下方不是復(fù)位塊，把白塊移開目標(biāo)位置 * 2、把復(fù)位塊移到目標(biāo)位置正下方 * 3、把白塊移動復(fù)位塊下方 * 4、按照規(guī)定的步驟復(fù)位 */ //第一步 if(whiteBlockX==targetX&& whiteBlockY==targetY){ if(whiteBlockX==resetBlockX&&whiteBlockY==resetBlockY+1){//復(fù)位塊在下方 swapWhiteBlockAndCurrentBlock(); return; }else{ whiteBlockDown(); } } //第二步 把復(fù)位塊移到目標(biāo)位置正下方 reset2_2(targetX, targetY+1); //第三步 把白塊移動復(fù)位塊下方 reset2_3(); //第四步 按照規(guī)定的步驟復(fù)位 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){//復(fù)位塊在最右邊，先左移；方便上移時統(tǒng)一的采用白塊逆時針方式 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){//復(fù)位塊在最右邊了，無法右移，直接退出 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){//在左邊邊界 復(fù)位塊無法左移，直接退出遞歸 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){//復(fù)位塊在最低端，白塊不能順時針移動 whiteBlockLeft(); }else{ whiteBlockRight(); } } }else if(whiteBlockX>resetBlockX){//右上方 if(resetBlockY==n-1){//復(fù)位塊在最低端，白塊不能順時針移動 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){//復(fù)位塊到頂了，無法上移 return; }// System.out.println("resetBlockUp"); if (whiteBlockY < resetBlockY) {//上方 if(whiteBlockY < resetBlockY - 1){//上方多行 whiteBlockDown(); }else{//上方一行 if(whiteBlockX == resetBlockX){//白塊和復(fù)位塊在同一列（豎列） 白塊和復(fù)位塊直接交換位置 swapWhiteBlockAndCurrentBlock();//退出遞歸 return; }else{ if(whiteBlockX<resetBlockX){//白塊在復(fù)位塊的左邊；白塊右移 whiteBlockRight(); }else{//白塊在復(fù)位塊的右邊；白塊左移 whiteBlockLeft(); } } } } else if (whiteBlockY == resetBlockY) {//白塊和復(fù)位塊同一行；白塊上移 if(whiteBlockX<resetBlockX){//正左 if(whiteBlockX<resetBlockX-1){//正左多格 whiteBlockRight(); }else{//正左一格 if(whiteBlockY==n-1){//到底了 whiteBlockUp(); }else { if(resetBlockX==n-1){//復(fù)位塊在最右邊，無法逆時針,只有順指針移動白塊 whiteBlockUp(); }else{ whiteBlockDown(); } } } }else{//正右 whiteBlockUp(); } }else{//白塊在復(fù)位塊下方，白塊需要饒過復(fù)位塊上移,白塊逆時針繞到白塊上面 //三種情況：左下，下，右下 if(whiteBlockX<=resetBlockX){//左下，下；白塊右移 if(resetBlockX==n-1){//復(fù)位塊在最右邊，無法逆時針,只有順指針移動白塊 if(whiteBlockX==resetBlockX){//正下方 whiteBlockLeft(); }else{//左下方 whiteBlockUp(); } }else{ whiteBlockRight(); } }else{//右下；白塊上移 whiteBlockUp(); } } resetBlockUp(targetX, targetY);//遞歸 } //白塊和復(fù)位塊交換位置 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); } }} |
以上所述就是本文的全部內(nèi)容了，希望大家能夠喜歡。
