Today I had a sudden idea to make a smart puzzle game for my girlfriend.
These functions need to be realized, the first is to customize the picture, and the second is to customize the grid. Of course, what I thought of at the beginning was 3*3 4*4 5*5, and I did not use a grid like 3*5.
The third is to realize the automatic puzzle function. I believe everyone knows that women are not very good at games, so this automatic puzzle function is necessary.
I won’t write about other suspensions and rankings!
Now the key question comes out. It seems that the requirements for realizing the automatic puzzle function are a bit high! Can computers be like humans and can only:
Let’s get to the essence first
A jigsaw puzzle is really just a matter of arrangement:
There is a definition of permutation: In an arrangement of 1, 2,...,n, if the front and back positions of a pair of numbers are in reverse order, that is, the front number is greater than the back number, then they are called a reverse order. The total number of reverse orders in a permutation is called the reverse order number of this permutation. The arrangement in which the reverse number is an even number is called an even arrangement; the arrangement in which the reverse number is an odd number is called an odd arrangement. For example, in 2431, 21, 43, 41, and 31 are in reverse order, and the reverse order is 4, which is an even arrangement.
Here's another definition: By exchanging two numbers in a permutation, the parity of the permutation changes.
The above definitions are all taken from "Advanced Algebra".
The puzzle arrangement must be an even arrangement. This can be found in my references.
So this is how my puzzle is implemented!
Will be writing later
Reference: http://en.wikipedia.org/wiki/Fifteen_puzzle
Automatic puzzle:
First of all, there should be certain rules for automatic puzzles. According to my puzzle experience, to complete the puzzle, different areas use different puzzle rules, so:
My grid map is divided into 4 areas (if the grid map has n*n grids)
The first area: x coordinate range 0 to n-2, y coordinate range 0 to n-3
Second area: x coordinate n-1, y coordinate range 0 to n-3
The third area: x coordinate range 0 to n-3, y coordinate range n-2 and n-1
The fourth area: x coordinate range n-2 to n-1, y coordinate range n-2 and n-1; that is, the last four cells
Each area can be completed according to the rules of the respective area.
Puzzle.java
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;//Platform base private int[][] puzzle; private int resetBlock = 0;// //Blank block position private int whiteBlockX; private int whiteBlockY; //The coordinates of the block currently to be moved are the reset block 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; // The number of shuffles must be an even number. 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) {// Guaranteed even sorting if((x0 ==n-1&&y0==n-1)||(x1==n-1&&y1==n-1)){//The last one is not replacedcontinue; } 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) {//The last one is blank, } else { reset(x, y) ; } } } } //Reset the block to the target position private void reset(int targetX, int targetY) { //Find the current position of the reset block initResetBlock(targetX, targetY); /* * The reset sequence is from left to right, top to bottom* The movement method is to move up first, then to the left* The current reset block, the position it wants to reset can be divided into four situations* 1. Not in the rightmost row nor the bottom two Rows * 2. The rightmost row x=n-1, but not the bottom two rows; * 3. The bottom two rows y=n-2, but not the rightmost row; * 4. Even the rightmost row is also the bottom two rows OK*/ if(targetX < n-1 && targetY < n-2){ if(resetBlockX==targetX&&resetBlockY==targetY){//The position is correct without moving return;//Exit the recursion} resetBlockToTarget(targetX, targetY); }else if( targetX==n-1 && targetY < n-2){//The second case if(resetBlockX==targetX&&resetBlockY==targetY){//The position is correct without moving return;//Exit the recursion} 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);//recursion} 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 is the position of the reset block 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)){//No reset successful// 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 the conditions are met, exit the recursion} //The white block may be on the left, lower left, or lower side of the reset block if(whiteBlockY= =resetBlockY){//left whiteBlockDown(); }else if(whiteBlockX < resetBlockX){//lower left whiteBlockRight(); }else { whiteBlockUp(); } reset2_3();//recursion} private void reset2_2(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//2. Move the reset block to the target position Return below;//Exit recursion} //Possible positions of reset block, target position left, directly below, lower left if(resetBlockX==targetX){//Move directly below and up resetBlockUp(targetX, targetY); }else{//Left or lower left; first Move right and then up resetBlockRight(targetX, targetY); } reset2_2(targetX, targetY);//recursion} private void reset2(int targetX, int targetY){ if (resetBlockX == target The bottom is not a reset block, move the white block to the target position* 2. Move the reset block directly below the target position* 3. Move the white block below the reset block* 4. Reset according to the prescribed steps*/ //The first step if(whiteBlockX==targetX&& whiteBlockY==targetY){ if(whiteBlockX==resetBlockX&&whiteBlockY==resetBlockY+1){//The reset block is below swapWhiteBlockAndCurrentBlock(); return; }else{ whiteBlockDown(); } } //The second step is to move the reset block directly below the target position reset2_2(targetX, targetY+1); //The third step moves the white block below the reset block reset2_3(); //The fourth step resets swapWhiteBlockAndCurrentBlock() according to the prescribed steps; 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){//Correct position without moving return ;//Exit recursion} if(resetBlockY==targetY){//positive left resetBlockLeft(targetX, targetY); }else{//lower left, lower, lower right if(resetBlockX>=targetX){//lower right||down; move up if( resetBlockX==n-1){//The reset block is on the far right, move left first; to facilitate the upward movement, the white block counterclockwise resetBlockLeft(targetX, targetY); }else{ resetBlockUp(targetX, targetY); } }else{//Lower left; right shift resetBlockRight(targetX, targetY); } } resetBlockToTarget(targetX, targetY);//Recursion} private void resetBlockRight(int targetX, int targetY){ if (resetBlockX == target ; }// System.out.println("resetBlockRight"); if(whiteBlockY<resetBlockY){//Above if(whiteBlockY<resetBlockY-1){//Multiple lines above whiteBlockDown(); }else{//A row above if(whiteBlockX<resetBlockX+1){//Top left and right above whiteBlockRight (); }else{//upper right whiteBlockDown(); } } }else if(whiteBlockY==resetBlockY){//Same line if(whiteBlockX<resetBlockX){//Left side if(whiteBlockY==n-1){//At the end, you can only go up whiteBlockUp(); }else{ whiteBlockDown (); } }else{//right if(whiteBlockX==resetBlockX+1){ swapWhiteBlockAndCurrentBlock(); return;//Exit recursion}else{ whiteBlockLeft(); } } }else{//Bottom if(whiteBlockX <= resetBlockX){//Bottom left, bottom whiteBlockRight(); }else{//Bottom right whiteBlockUp(); } } resetBlockRight(targetX, targetY);//recursion} private void resetBlockLeft(int targetX, int targetY){ if (resetBlockX == target / System.out.println("resetBlockLeft"); if(whiteBlockY<resetBlockY){//Above if(whiteBlockY<resetBlockY-1){//Multiple lines above whiteBlockDown(); }else{//A row above if(whiteBlockX==resetBlockX){//Above if(whiteBlockX= =n-1){//On the far right, the white block cannot be moved to the right, but can only be moved to the left whiteBlockLeft(); }else{ if(resetBlockY==n-1){//The reset block is at the lowest end, the white block cannot move clockwise whiteBlockLeft(); }else{ whiteBlockRight(); } } }else if(whiteBlockX>resetBlockX){//Upper right if(resetBlockY==n-1){//The reset block is at the lowest end, the white block cannot move clockwise whiteBlockLeft(); }else{ whiteBlockDown(); } }else{//upper left whiteBlockDown(); } } }else if(whiteBlockY==resetBlockY){//left, right if(whiteBlockX<resetBlockX){//left if(whiteBlockX= =resetBlockX-1){//One space on the left swapWhiteBlockAndCurrentBlock();//Exit the recursion return; }else{ whiteBlockRight(); } }else{//Right if(whiteBlockY==n-1){//It’s at the bottom and cannot move down. Can only be moved up whiteBlockUp(); }else{ whiteBlockDown(); } } }else{//Lower left, lower, lower right if(whiteBlockX<resetBlockX){//Lower left if(whiteBlockX==resetBlockX-1){ whiteBlockUp( ); }else{ whiteBlockRight(); } }else{//Bottom, lower right whiteBlockLeft(); } } resetBlockLeft(targetX, targetY);//Recursion} private void resetBlockUp(int targetX, int targetY){ if(resetBlockX==targetX&&resetBlockY==targetY){//The position is correct without moving return;//Exit recursion} if( resetBlockY==0){//The reset block has reached the top and cannot be moved up return; }// System.out.println("resetBlockUp"); if (whiteBlockY < resetBlockY) {//Above if(whiteBlockY < resetBlockY - 1){//Multiple lines above whiteBlockDown(); }else{//A row above if(whiteBlockX = = resetBlockX){//The white block and the reset block are in the same column (vertical column) The white block and the reset block directly swap positions swapWhiteBlockAndCurrentBlock();//Exit the recursion return; }else{ if(whiteBlockX<resetBlockX){//The white block is to the left of the reset block; the white block moves to the right whiteBlockRight(); }else{/ /The white block is on the right side of the reset block; the white block moves left whiteBlockLeft(); } } } } else if (whiteBlockY == resetBlockY) {//The white block and the reset block are in the same row; the white block moves up if(whiteBlockX<resetBlockX){//Forward left if(whiteBlockX<resetBlockX-1){//Forward left multi-cell whiteBlockRight(); } else{//One square to the left if(whiteBlockY==n-1){//The end whiteBlockUp(); }else { if(resetBlockX==n-1){//The reset block is on the far right and cannot be counterclockwise. Only the white block can be moved clockwise whiteBlockUp(); }else{ whiteBlockDown(); } } }else{//right whiteBlockUp (); } }else{//The white block is below the reset block. The white block needs to move up past the reset block. The white block goes around counterclockwise to the top of the white block//Three situations: lower left, lower, lower right if(whiteBlockX<=resetBlockX) {//Bottom left, down; white block moves right i f(resetBlockX==n-1){//The reset block is on the far right and cannot be counterclockwise. Only the white block can be moved clockwise if(whiteBlockX==resetBlockX){//Just below whiteBlockLeft(); }else{//Lower left whiteBlockUp(); } }else{ whiteBlockRight(); } }else{//Lower right; white block moves up whiteBlockUp(); } } resetBlockUp(targetX, targetY);//Recursion} / /White block and reset block swap positions 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); } }}The above is the entire content of this article, I hope you all like it.