今天突发奇想，想做一个智能拼图游戏来给哄女友。
需要实现这些功能
第一图片自定义
第二宫格自定义，当然我一开始就想的是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); } }} |
以上所述就是本文的全部内容了，希望大家能够喜欢。
