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();
	}
}