/********************/
/* クラスDataの定義 */
/********************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Random;
import java.applet.*;

public class Data extends Applet implements ItemListener {

	int game = 0;   // ゲームの種類
                    //   =0 : ８パズル
                    //   =1 : １５パズル
	int i_set = 0;   // 初期状態の設定方法
                     //   =0 : 入力する
                     //   =1 : ランダム
	int goal = 0;   // 目標
                    //   =0 : 周辺を回る
                    //   =1 : 上から横並び
	int g[][];   // 目標状態
	int p[][];   // 現在の状態

	Choice choice1, choice2, choice3;
	Data dt = this;

	/************/
	/* 初期設定 */
	/************/
	public void init()
	{
						// レイアウトの変更
		setFont(new Font("TimesRoman", Font.BOLD, 20));
		setLayout(new GridLayout(4, 2, 5, 10));
						// スクロールリスト
		Label fill1 = new Label("ゲーム");
		add(fill1);
		choice1 = new Choice();
		choice1.add("８パズル");
		choice1.add("１５パズル");
		add(choice1);
		choice1.addItemListener(this);

		Label fill2 = new Label("初期設定");
		add(fill2);
		choice2 = new Choice();
		choice2.add("入力");
		choice2.add("ランダム");
		add(choice2);
		choice2.addItemListener(this);

		Label fill3 = new Label("ゴール");
		add(fill3);
		choice3 = new Choice();
		choice3.add("回転");
		choice3.add("横並び");
		add(choice3);
		choice3.addItemListener(this);
						// OK ボタンの設定
		Label fill4 = new Label("　スタート？");
		add(fill4);
		Button bt = new Button("OK");
		bt.addMouseListener(new ClickMouse());
		add(bt);
	}

	/******************************/
	/* 上，左，下，右の余白の設定 */
	/******************************/
	public Insets getInsets()
	{
		return new Insets(10, 10, 10, 10);
	}

	/******************************/
	/* チョイスコントロールの処理 */
	/******************************/
	public void itemStateChanged(ItemEvent e)
	{
		if (e.getItemSelectable() == choice1) {
			game = ((Choice)e.getItemSelectable()).getSelectedIndex();
		}
		if (e.getItemSelectable() == choice2) {
			i_set = ((Choice)e.getItemSelectable()).getSelectedIndex();
		}
		if (e.getItemSelectable() == choice3) {
			goal = ((Choice)e.getItemSelectable()).getSelectedIndex();
		}
	}

	/********************************/
	/* OKボタンが押されたときの処理 */
	/********************************/
	class ClickMouse extends MouseAdapter
	{
		/************************************/
		/* マウスがクリックされたときの処理 */
		/************************************/
		public void mouseClicked(MouseEvent e)
		{
			int i1, i2, k, k1, k2, n = 0;
		/*
		          ゲームの種類
		*/
							// ８パズル
			if (game == 0) {
				g = new int [3][3];
				p = new int [3][3];
				n = 3;
			}
							// １５パズル
			else {
				g = new int [4][4];
				p = new int [4][4];
				n = 4;
			}
		/*
		          初期状態と目標状態
		*/
					// 初期状態を入力する場合
			Initial initial;
			if (i_set == 0)
				initial = new Initial(dt);
					// 初期状態をランダムに決める場合
						// 目標状態の決定
							// 回転
			else {
				if (goal == 0) {
					if (game == 0) {
						k = 1;
						for (i1 = 0; i1 < n; i1++) {
							g[0][i1] = k;
							k++;
						}
						k = 7;
						for (i1 = 0; i1 < n; i1++) {
							g[2][i1] = k;
							k--;
						}
						g[1][0] = 8;
						g[1][1] = 0;
						g[1][2] = 4;
						k1      = 1;
						k2      = 1;
					}
					else {
						k = 1;
						for (i1 = 0; i1 < n; i1++) {
							g[0][i1] = k;
							g[1][i1] = k + 11;
							k++;
						}
						g[1][3] = 5;
						k       = 10;
						for (i1 = 0; i1 < n; i1++) {
							g[3][i1] = k;
							k--;
						}
						g[2][0] = 11;
						g[2][1] = 0;
						g[2][2] = 15;
						g[2][3] = 6;
						k1      = 2;
						k2      = 1;
					}
				}
							// 横並び
				else {
					k = 1;
					for (i1 = 0; i1 < n; i1++) {
						for (i2 = 0; i2 < n; i2++) {
							g[i1][i2] = k;
							k++;
						}
					}
					g[n-1][n-1] = 0;
					k1          = n - 1;
					k2          = n - 1;
				}
						// 初期状態の決定
				for (i1 = 0; i1 < n; i1++) {
					for (i2 = 0; i2 < n; i2++)
						p[i1][i2] = g[i1][i2];
				}

				for (i1 = 0; i1 < 200; i1++) {
					k = (int)(Math.random() * 4.0);
					switch (k) {
						case 0:   // 上へ移動
							if (k1 > 0) {
								p[k1][k2]   = p[k1-1][k2];
								p[k1-1][k2] = 0;
								k1--;
							}
							break;
						case 1:   // 下へ移動
							if (k1 < n-1) {
								p[k1][k2]   = p[k1+1][k2];
								p[k1+1][k2] = 0;
								k1++;
							}
							break;
						case 2:   // 左へ移動
							if (k2 > 0) {
								p[k1][k2]   = p[k1][k2-1];
								p[k1][k2-1] = 0;
								k2--;
							}
							break;
						default:   // 右へ移動
							if (k2 < n-1) {
								p[k1][k2]   = p[k1][k2+1];
								p[k1][k2+1] = 0;
								k2++;
							}
							break;
					}
				}
						// 目標状態の表示
				Goal goal_s = new Goal(dt);
			}
		}
	}

	/************/
	/* 終了処理 */
	/************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			System.exit(0);
		}
	}
}

----------------------------------------

/**************************/
/* クラスInitialの定義    */
/* （初期状態の入力）     */
/**************************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;

class Initial extends Frame {

	private int err = 0;   // エラーの有無
	private int n;   // 行・列の数
	private Data dt;
	private Initial in = this;

	TextField a[][];
	Label f[];

	/****************************************/
	/* コンストラクタ                       */
	/*      dt_i : Dataクラスのオブジェクト */
	/****************************************/
	Initial(Data dt_i)
	{
						// Frameクラスのコンストラクタの呼び出し
		super("初期状態");
						// ゲームの種類とレイアウトの変更
		int i1, i2;
		n  = (dt_i.game == 0) ? 3 : 4;
		dt = dt_i;
		a  = new TextField [n][n];
		f  = new Label [n-1];
		setLayout(new GridLayout(n, n+1, 5, 10));
		setFont(new Font("TimesRoman", Font.BOLD, 20));
						// テキストフィールドの設定
		for (i1 = 0; i1 < n; i1++) {
			for (i2 = 0; i2 < n; i2++) {
				a[i1][i2] = new TextField(2);
				add(a[i1][i2]);
			}
			if (i1 < n-1) {
				f[i1] = new Label();
				add(f[i1]);
			}
		}
						// OK ボタンの設定
		Button bt = new Button("OK");
		bt.addMouseListener(new ClickMouse());
		add(bt);
						// Windowサイズを設定
		setSize(200, 300);
						// ウィンドウを表示
		setVisible(true);
						// イベントアダプタ
		addWindowListener(new WinEnd());
	}

	/******************************/
	/* 上，左，下，右の余白の設定 */
	/******************************/
	public Insets getInsets()
	{
		return new Insets(70, 20, 100, 20);
	}

	/**************************/
	/* エラーメッセージの表示 */
	/**************************/
	public void paint(Graphics g)
	{
						// フォントの設定
		Font f = new Font("TimesRoman", Font.BOLD, 20);
		g.setFont(f);
						// エラーメッセージの出力
		Insets insets = getInsets();
		Dimension d = getSize();
		int x = insets.left + 20;
		int y = d.height - insets.bottom + 25;
		if (err == 0)
			g.drawString("             ", x, y);
		else {
			g.setColor(Color.red);
			g.drawString("*** Error ***", x, y);
			g.setColor(Color.black);
		}
	}

	/********************************/
	/* OKボタンが押されたときの処理 */
	/********************************/
	class ClickMouse extends MouseAdapter
	{
		/************************************/
		/* マウスがクリックされたときの処理 */
		/************************************/
		public void mouseClicked(MouseEvent e)
		{
			int i1, i2, i3, i4, k, k1;

			err = 0;
		/*
		          入力データの処理
		*/
			for (i1 = 0; i1 < n && err == 0; i1++) {
				for (i2 = 0; i2 < n && err == 0; i2++) {
					if ((a[i1][i2].getText()).length() <= 0)
						dt.p[i1][i2] = 0;
					else
						dt.p[i1][i2] = Integer.parseInt(a[i1][i2].getText());
					k1 = (dt.game == 0) ? 8 : 15;
					if (dt.p[i1][i2] < 0 || dt.p[i1][i2] > k1)
						err = 1;
					else {
						for (i3 = 0; i3 <= i1 && err == 0; i3++) {
							k1 = (i3 == i1) ? i2 : n;
							for (i4 = 0; i4 < k1 && err == 0; i4++) {
								if (dt.p[i1][i2] == dt.p[i3][i4])
									err = 1;
							}
						}
					}
				}
			}
		/*
		          目標状態
		*/
			repaint();

			if (err == 0) {
							// 回転
				if (dt.goal == 0) {
					if (dt.game == 0) {
						k = 1;
						for (i1 = 0; i1 < n; i1++) {
							dt.g[0][i1] = k;
							k++;
						}
						k = 7;
						for (i1 = 0; i1 < n; i1++) {
							dt.g[2][i1] = k;
							k--;
						}
						dt.g[1][0] = 8;
						dt.g[1][1] = 0;
						dt.g[1][2] = 4;
					}
					else {
						k = 1;
						for (i1 = 0; i1 < n; i1++) {
							dt.g[0][i1] = k;
							dt.g[1][i1] = k + 11;
							k++;
						}
						dt.g[1][3] = 5;
						k          = 10;
						for (i1 = 0; i1 < n; i1++) {
							dt.g[3][i1] = k;
							k--;
						}
						dt.g[2][0] = 11;
						dt.g[2][1] = 0;
						dt.g[2][2] = 15;
						dt.g[2][3] = 6;
					}
				}
							// 横並び
				else {
					k = 1;
					for (i1 = 0; i1 < n; i1++) {
						for (i2 = 0; i2 < n; i2++) {
							dt.g[i1][i2] = k;
							k++;
						}
					}
					dt.g[n-1][n-1] = 0;
				}
							// 目標状態の表示
				in.setVisible(false);
				Goal goal_s = new Goal(dt);
			}
		}
	}

	/************/
	/* 終了処理 */
	/************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			in.setVisible(false);
		}
	}
}

----------------------------------------

/**********************/
/* クラスGoalの定義   */
/* （目標状態の表示） */
/**********************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;

class Goal extends Frame {

	private int size;   // コマの大きさ
	private Data dt;
	private Goal ds = this;
	Insets insets;

	/****************************************/
	/* コンストラクタ                       */
	/*      dt_i : Dataクラスのオブジェクト */
	/****************************************/
	Goal(Data dt_i)
	{
					// Frameクラスのコンストラクタの呼び出し
		super("ゴール");
					// データの設定
		dt   = dt_i;
		size = 50;
		setFont(new Font("TimesRoman", Font.BOLD, 20));
					// Windowの大きさの設定
		if (dt.game == 0)
			setSize(3*(size+10)+70, 3*(size+10)+200);
		else
			setSize(4*(size+10)+70, 4*(size+10)+200);
					// 実行ボタンの設定
		Panel pnl = new Panel();
		Button bt = new Button("ゲームの実行");
		bt.addMouseListener(new ClickMouse());
		pnl.add(bt);
		add("South", pnl);
					// ウィンドウを表示
		setVisible(true);
		insets = getInsets();
					// イベントアダプタ
		addWindowListener(new WinEnd());
	}

	/******************************/
	/* 上，左，下，右の余白の設定 */
	/******************************/
	public Insets getInsets()
	{
		return new Insets(70, 20, 70, 30);
	}

	/********/
	/* 描画 */
	/********/
	public void paint (Graphics e)
	{
		int i1, i2, x, y;
		int n = (dt.game == 0) ? 3 : 4;
					// 四角形を描く
		x = insets.left + 20;
		y = insets.top;
		e.setColor(Color.cyan);
		for (i1 = 0; i1 < n; i1++) {
			for (i2 = 0; i2 < n; i2++) {
				e.fill3DRect(x, y, size, size, true);
				x += (size + 10);
			}
			x  = insets.left + 20;
			y += (size + 10);
		}
					// 数字を描く
		x = insets.left + 20;
		y = insets.top;
		e.setColor(Color.black);
		e.setFont(new Font("TimesRoman", Font.BOLD, size));
		for (i1 = 0; i1 < n; i1++) {
			for (i2 = 0; i2 < n; i2++) {
				if (dt.g[i1][i2] > 0) {
					if (dt.g[i1][i2] < 10)
						e.drawString(Integer.toString(dt.g[i1][i2]), x+13, y+size-9);
					else
						e.drawString(Integer.toString(dt.g[i1][i2]), x-2, y+size-9);
				}
				x += (size + 10);
			}
			x  = insets.left + 20;
			y += (size + 10);
		}
	}

	/**********************************/
	/* 実行ボタンが押されたときの処理 */
	/**********************************/
	class ClickMouse extends MouseAdapter
	{
		/****************************************/
		/*     マウスがクリックされたときの処理 */
		/****************************************/
		public void mouseClicked(MouseEvent e)
		{
			Run run = new Run(dt);
		}
	}

	/************/
	/* 終了処理 */
	/************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			ds.setVisible(false);
		}
	}
}

----------------------------------------

/********************/
/* クラスRunの定義  */
/* （ゲームの実行） */
/********************/
import java.io.*;
import java.awt.*;
import java.awt.event.*;

class Run extends Frame {

	private int count = 0;   // コマを動かした回数
	private int n;   // 行・列の数
	private int ok = 0;   // ゲームの終了
	private int size;   // コマの大きさ
	private Data dt;
	private Run rn = this;
	Insets insets;

	/****************************************/
	/* コンストラクタ                       */
	/*      dt_i : Dataクラスのオブジェクト */
	/****************************************/
	Run(Data dt_i)
	{
					// Frameクラスのコンストラクタの呼び出し
		super("ゲーム");
					// データの設定
		dt   = dt_i;
		size = 50;
		n    = (dt.game == 0) ? 3 : 4;
		setFont(new Font("TimesRoman", Font.BOLD, 20));
					// Windowの大きさの設定
		if (dt.game == 0)
			setSize(3*(size+10)+70, 3*(size+10)+200);
		else
			setSize(4*(size+10)+70, 4*(size+10)+200);
					// ウィンドウを表示
		setVisible(true);
		insets = getInsets();
					// イベントアダプタ
		addWindowListener(new WinEnd());
		addMouseListener(new ClickMouse());
	}

	/******************************/
	/* 上，左，下，右の余白の設定 */
	/******************************/
	public Insets getInsets()
	{
		return new Insets(70, 20, 70, 30);
	}

	/********/
	/* 描画 */
	/********/
	public void paint (Graphics e)
	{
		int i1, i2, x, y;
					// 四角形を描く
		x = insets.left + 20;
		y = insets.top;
		e.setColor(Color.cyan);
		for (i1 = 0; i1 < n; i1++) {
			for (i2 = 0; i2 < n; i2++) {
				e.fill3DRect(x, y, size, size, true);
				x += (size + 10);
			}
			x  = insets.left + 20;
			y += (size + 10);
		}
					// 数字を描く
		x = insets.left + 20;
		y = insets.top;
		e.setColor(Color.black);
		e.setFont(new Font("TimesRoman", Font.BOLD, size));
		for (i1 = 0; i1 < n; i1++) {
			for (i2 = 0; i2 < n; i2++) {
				if (dt.p[i1][i2] > 0) {
					if (dt.p[i1][i2] < 10)
						e.drawString(Integer.toString(dt.p[i1][i2]), x+13, y+size-9);
					else
						e.drawString(Integer.toString(dt.p[i1][i2]), x-2, y+size-9);
				}
				x += (size + 10);
			}
			x  = insets.left + 20;
			y += (size + 10);
		}
					// ゲームの終了
		if (ok > 0) {
			Dimension d = getSize();
			x = insets.left + 20;
			y = d.height - insets.bottom - 25;
			e.setFont(new Font("TimesRoman", Font.PLAIN, 20));
			e.drawString("Congratulation!!", x, y-20);
			e.drawString("Number of Trial : "+Integer.toString(count), x, y);
		}
	}

	/************************************/
	/* マウスがクリックされたときの処理 */
	/************************************/
	class ClickMouse extends MouseAdapter
	{
		public void mouseClicked(MouseEvent e)
		{
			int i1, i2, k1 = -1, k2 = -1, sw, x, xp, y, yp;
							// マウスの位置
			xp = e.getX();
			yp = e.getY();
							// クリックされたコマを決定
			x = insets.left + 20;
			y = insets.top;
			for (i1 = 0; i1 < n && k1 < 0; i1++) {
				for (i2 = 0; i2 < n && k1 < 0; i2++) {
					if (xp > x && xp < x+size && yp > y && yp < y+size) {
						k1 = i1;
						k2 = i2;
					}
					else
						x += (size + 10);
				}
				x  = insets.left + 20;
				y += (size + 10);
			}
							// コマの移動
			sw = 0;

			if (k1 > 0) {                // 上へ移動
				if (dt.p[k1-1][k2] == 0) {
					dt.p[k1-1][k2] = dt.p[k1][k2];
					dt.p[k1][k2]   = 0;
					sw             = 1;
				}
			}

			if (sw == 0 && k1 < n-1) {   // 下へ移動
				if (dt.p[k1+1][k2] == 0) {
					dt.p[k1+1][k2] = dt.p[k1][k2];
					dt.p[k1][k2]   = 0;
					sw             = 1;
				}
			}

			if (sw == 0 && k2 > 0) {     // 左へ移動
				if (dt.p[k1][k2-1] == 0) {
					dt.p[k1][k2-1] = dt.p[k1][k2];
					dt.p[k1][k2]   = 0;
					sw             = 1;
				}
			}

			if (sw == 0 && k2 < n-1) {   // 右へ移動
				if (dt.p[k1][k2+1] == 0) {
					dt.p[k1][k2+1] = dt.p[k1][k2];
					dt.p[k1][k2]   = 0;
					sw             = 1;
				}
			}
							// ゴールに達したか否かのチェックと描画
			if (sw > 0) {
				count++;
				ok = 1;
				for (i1 = 0; i1 < n && ok > 0; i1++) {
					for (i2 = 0; i2 < n && ok > 0; i2++) {
						if (dt.g[i1][i2] != dt.p[i1][i2])
							ok = 0;
					}
				}
				repaint();
			}
		}
	}

	/************/
	/* 終了処理 */
	/************/
	class WinEnd extends WindowAdapter
	{
		public void windowClosing(WindowEvent e) {
			rn.setVisible(false);
		}
	}
}