Есть там молот, есть там серп…

import java.awt.Color; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.File; import java.util.ArrayList; import java.util.HashSet; import javax.imageio.ImageIO;  public class Main  { //Копирует плитку с номером p0 из исходного изображение img0 в позицию p1 изображения img1. //Если hl=true, плитка подсвечивается static void copy(int p0, BufferedImage img0, int p1, BufferedImage img1, boolean hl) { int ww=img0.getWidth()/3; int hh=img0.getHeight()/3; int y0=(p0/3)*hh; int x0=(p0%3)*ww; int y1=(p1/3)*hh; int x1=(p1%3)*ww; for(int i=0; i<hh; i++) { for(int j=0; j<ww; j++) { int rgb=img0.getRGB(x0+j, y0+i); if(hl) { int d=100; int r=((rgb>>16)&255)+d, g=((rgb>>8)&255)+d, b=(rgb&255)+d; if(r>255) r=255; if(g>255) g=255; if(b>255) b=255; rgb=(255<<24)+(r<<16)+(g<<8)+b;  } img1.setRGB(x1+j, y1+i, rgb); } } }  //Строит изображение img1 из исходного изображения img0 в соответствии с массивом перестановок плиток a. //hl - номер подсвеченной плитки. static void makeAll(int[] a, BufferedImage img0, BufferedImage img1, int hl) { for(int i=0; i<a.length; i++) { copy(a[i], img0, i, img1, (i==hl)); } }  //Выводит позицию, заданную массивом перестановок плиток a в файл оut. Плитка с номером hl подсвечивается. static void outPosition(int[] a, String out, int hl) { try { BufferedImage img=ImageIO.read(new File("puzzle.png")); int ww=img.getWidth(); int hh=img.getHeight(); int type=img.getType(); BufferedImage img1=new BufferedImage(ww, hh, type); makeAll(a, img, img1, hl); ImageIO.write(img1, "png", new File(out)); } catch (Exception e) { e.printStackTrace(); } }  //Класс узлов среды static class Node { public int[] value;    //массив перестановок public Node  parent;   //предыдущий узел public int act;        //активная (перемещаемая) плитка Node() {value=null; parent=null; act=-1;} } static String target;           //Наша целевая строка static HashSet<String> field;   //Множество уже пройденных строк static ArrayList<Node> nodes;   //Массив узлов static ArrayList<Node> front;   //Фронт волны  //Получает массив перестановок (поле value узла Node) //Выдает массив, нулевой элемент которого позиция числа 8, а остальные - соседи числа 8. static int[] getNeibours(int[] val) { int pos=0; for(int i=0; i<val.length; i++) { if(val[i]==8) {pos=i; break;} } if((pos<0)||(pos>8)) return null; int x=pos%3, y=pos/3; int n=0; int[] a=new int[6]; a[n++]=pos; if(x-1 >= 0) a[n++]=pos-1; if(x+1 <  3) a[n++]=pos+1; if(y-1 >= 0) a[n++]=pos-3; if(y+1 <  3) a[n++]=pos+3; int[] b=new int[n]; for(int i=0; i<n; i++) b[i]=a[i]; return b; }  //Массив перестановок в строку static String toString(int[] val) { String s=""; String a="012345678"; for(int i=0; i<val.length; i++) s+=a.charAt(val[i]); return s; }  //Шаг волнового алгоритма static int step() { ArrayList<Node> tmp=new ArrayList<>(); //новый волновой фронт for(int i=0; i<front.size(); i++)  {//Проходим по всему старому волновому фронту Node nd=front.get(i); int[] neib=getNeibours(nd.value); //массив соседств int pos=neib[0]; if(neib != null) { for(int j=1; j<neib.length; j++) {//для каждого из соседей меняем его местами с числом 8 int[] val=new int[nd.value.length]; for(int k=0; k<nd.value.length; k++) val[k]=nd.value[k]; int t=val[pos]; val[pos]=val[neib[j]]; val[neib[j]]=t; if(field.add(toString(val))) //смотрим, проходили мы уже такую позицию или нет  {//если проходили, добавляем узел в список узлов и новый волновой фронт  Node nd1=new Node(); nd1.value=val; nd1.parent=nd; nd1.act=neib[j]; tmp.add(nd1); nodes.add(nd1); if(target.equals(toString(val)))  return 1; //если получили целевую строку, дальше ничего делать не надо } } } } if(tmp.size()==0)  return -1; //если новый волновой фронт пустой, путь к целевой строке невозможен front=tmp; //обновляем волновой фронт return 0; }  //Извлечение пути от конца к началу static ArrayList<Node> extractPath() { ArrayList<Node> path=new ArrayList<>(); Node nd=nodes.get(nodes.size()-1); int act=-1; do { Node nd1=nd.parent; int act1=nd.act; nd.act=act; path.add(nd); nd=nd1; act=act1; } while(nd != null); return path; }  //Выводит одну суммарную картинку static void makeTotal() { try { BufferedImage img=ImageIO.read(new File("puzzle.png")); int ww=img.getWidth(); int hh=img.getHeight(); int type=img.getType(); int gap=30; //промежуток между картинками BufferedImage img1=new BufferedImage(5*ww+4*gap, 4*hh+3*gap, type); Graphics2D gr=img1.createGraphics(); gr.setPaint(new Color(255, 255, 255)); gr.fillRect ( 0, 0, img1.getWidth(), img1.getHeight());  int nn=1; int xx=0, yy=0; for(int i=0; i<4; i++) { xx=0; for(int j=0; j<5; j++) { String name="./solution/step_"+nn+".png"; nn++; BufferedImage imgn=ImageIO.read(new File(name)); int w=imgn.getWidth(), h=imgn.getHeight(); for(int y=0; y<h; y++) { for(int x=0; x<w; x++) { int rgb=imgn.getRGB(x, y); img1.setRGB(x+xx, y+yy, rgb); } } xx+=ww+gap; } yy+=hh+gap; } ImageIO.write(img1, "png", new File("./solution/total.png")); } catch (Exception e) { e.printStackTrace(); } }  static void solve() { field=new HashSet<>(); nodes=new ArrayList<>(); front=new ArrayList<>(); target="104635278"; int[] a= new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8}; Node nd0 = new Node(); nd0.value=a; field.add(toString(a)); nodes.add(nd0); front.add(nd0); int res=0; while(res==0) res=step(); if(res==1)  { System.out.println("Puzzle solved. Now save pictures"); ArrayList<Node> path=extractPath(); for(int i=0; i<path.size(); i++) { outPosition(path.get(i).value, "./solution/step_"+(path.size()-i)+".png", path.get(i).act); } makeTotal(); System.out.println("Done"); } else { System.out.println("Solution not found"); } }  public static void main(String[] args)  {                      solve(); } }