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); |
} |
} |
} |
初级程序员
by: 雨落冬夜 发表于:2017-04-19 11:33:21 顶(3) | 踩(1) 回复
想要源代码
回复评论