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;// 打乱次数，必须是偶数
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
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();
}
str=str==null?"":str;
if(str.length()<len){
return _str(str+" ", len);
}
return str;
}
private void println
(String str
){ if(isPrint){
}
}
// System.setOut(new PrintStream("e:/puzzle.txt","UTF-8"));
Puzzle p = new Puzzle();
try {
p.sort();
e.printStackTrace();
System.
out.
println("Exception:"); }finally{
}
}
}