///////////////////////
//   EightPuzzle.cs
// Copyright (c) 2025
//     by Ysama
///////////////////////
using System;
using System.Collections.Generic;	//List使用の為

namespace EightPuzzle
{
	public class App
	{
		static void Main()
		{
			ePuzzle ep = new ePuzzle();
			//初期状態
			Console.WriteLine(">>> 初期盤面 <<<");
			ep.ShowStartBoard();
			Console.Write(Environment.NewLine);
			//ゲーム開始
			ep.Start();
			Console.ReadLine();
		}
	}

	///////////////////
	//3 x 3 盤面クラス
	///////////////////
	public class NBoard
	{
		//メンバー定数
		const int Num = 9;				//ピース数
		const int None = -1;			//未設定の定数

		//メンバー変数
		private int [] Pieces;			//8パズルの9ピース配列
		int index = None;				//bdListにおけるthisのIndex
		int p_index = None;				//bdListにおける親のIndex

		//メンバープロパティ
		public int ID					//indexのプロパティ
		{
			get {return index;}
			set {index = value;}
		}
		public int ParentID				//p_indexのプロパティ
		{
			get {return p_index;}
			set {p_index = value;}
		}
		public int[] ptPieces			//Piecesのプロパティ
		{
			get {return Pieces;}
		}

		//メンバーメソッド
		public NBoard()					//コンストラクター
		{
			Pieces = new int [Num];
			for(int i = 0; i < Num; i++)
				Pieces[i] = i;
		}

		public NBoard(NBoard bd)		//コピーコンストラクター
		{
			if(bd == null)
				return;					//何もしない
			else
			{
				Pieces = new int [Num];
				for(int i = 0; i < Num; i++)
					Pieces[i] = bd.Pieces[i];
			}
		}

		//0～Num - 1のピースの値を返す
		public int Get(int pos)
		{
			if(pos < 0 || pos > Num - 1)
				return -1;
			return Pieces[pos];
		}

		//0-Num - 1のピースの値を代入
		public bool Set(int pos, int val)
		{
			if(pos < 0 || pos > Num - 1)
				return false;
			Pieces[pos] = val;
			return true;
		}

		//二つのNBoardが同一かチェックし、同一であれば真、異なれば偽を返す
		public override bool Equals(object obj)
		{
			if(obj == null || this.GetType() != obj.GetType())
				return false;

			NBoard that = (NBoard)obj;
			for(int i = 0; i < 9; i++)
				if(this.Pieces[i] != that.Pieces[i])
					return false;
			return true;
		}

		//pos1とpos2のピースの値を交換
		public bool Swap(int pos1, int pos2)
		{
			if(pos1 < 0 || pos1 > Num - 1)
				return false;
			if(pos2 < 0 || pos2 > Num - 1)
				return false;
			int temp = Pieces[pos1];
			Pieces[pos1] = Pieces[pos2];
			Pieces[pos2] = temp;
			return true;
		}

		//配列要素を検索し、あればその位置を返す（無ければ-1）
		public int IndexOf(int val)
		{
			return Array.IndexOf(Pieces, val);
		}

		//配列要素が完成形か否か
		public bool IsDone()
		{
			for(int i = 0; i < Num; i++)
				if(Pieces[i] != i)
					return false;
			return true;
		}

		//盤面（Pieces配列）を表示する
		public void Show()
		{
			for(int i = 0; i < Num; i++)
			{
				Console.Write(" " + Pieces[i].ToString());
				if(i % 3 == 2)		//右端の場合
					Console.Write(Environment.NewLine);
			}
		}

		//Chat-GPT推奨Listオーバーライドメソッド
		public override int GetHashCode()
		{
			int hash = 17;
			for (int i = 0; i < 9; i++)
				hash = hash * 31 + Pieces[i];
			return hash;
		}
	}

	////////////////
	//8Puzzleクラス
	////////////////
	public class ePuzzle
	{
		//メンバー定数
		const int Num = 9;				//配列要素数
		const int None = -1;			//未設定の定数

		//メンバー変数
		List <NBoard> bdList;			//NBoard配列
		private NBoard stBoard;			//ゲーム開始時のNBoard
		private int StartAt, EndAt;		//bdListのCheckAround開始、終了位置
		private bool Solved = false;	//パズル解決(ture)の完了フラグ
		int Layer = 0;					//世代を記録

		//コンストラクター
		public ePuzzle()
		{
			bdList = new List <NBoard> ();
			stBoard = new NBoard();
			StartAt = 0;
		}

		public void ShuffleArr()				//シャッフル方式
		{
			//要素数Numの配列を0 - Num - 1で初期化
			for(int i = 0; i < Num; i++)
				stBoard.Set(i, i);
			//乱数の初期化
			Random rand = new Random((int)DateTime.Now.Ticks & 0x0000FFFF);
			for(int i = Num - 1; i > 1; i--)
			{
				int n = rand.Next(i + 1);
				stBoard.Swap(n, i);
			}
			if(stBoard.IsDone())				//結果が完成形であればやり直し
				ShuffleArr();
		}

		public void SwapArr(bool ease = true)	//スワップ方式
		{
			//要素数Numの配列を0 - Num - 1で初期化
			for(int i = 0; i < Num; i++)
				stBoard.Set(i, i);
			int pos = Num - 1;					//空白の位置（8）
			//乱数の初期化
			Random rand = new Random((int)DateTime.Now.Ticks & 0x0000FFFF);
			//スワップ回数の設定
			int maxswap;
			if(ease)
				maxswap = rand.Next(10, 20);	//最長手数19、最短は10
			else
				maxswap = rand.Next(15, 31);	//8Puzzleの最長手数は31、最短はその半分
			for(int i = 0; i < maxswap; i++)
			{
				int dir = rand.Next(4);			//↑(0)→(1)↓(2)←(3)
				switch(dir)
				{
					case 0:		//上
						if(pos > 2)				//3 x 3盤の下2行にある場合
						{
							stBoard.Swap(pos, pos - 3);
							pos -= 3;
						}
						else
							i--;
						break;
					case 1:		//右
						if(pos % 3 < 2)			//3 x 3盤の左2列にある場合
						{
							stBoard.Swap(pos, pos + 1);
							pos += 1;
						}
						else
							i--;
						break;
					case 2:		//下
						if(pos < 6)				//3 x 3盤の上2行にある場合
						{
							stBoard.Swap(pos, pos + 3);
							pos += 3;
						}
						else
							i--;
						break;
					case 3:		//左
						if(pos % 3 > 0)			//3 x 3盤の右2列にある場合
						{
							stBoard.Swap(pos, pos - 1);
							pos -= 1;
						}
						else
							i--;
						break;
				}
			}
			if(stBoard.IsDone())				//結果が完成形であればやり直し
				SwapArr();
		}

		//開始時の盤面を表示する
		public void ShowStartBoard()
		{
			stBoard.Show();
		}

		//親がNoneになるまで、親を遡る
		public void TraceBack(int id)
		{
			for(int i = id; i != None; i = bdList[i].ParentID)
			{
				bdList[i].Show();
				Console.Write(Environment.NewLine);
			}
		}

		//ピースを交換した新しいボードが既登録かチェックし、
		//無ければbdListに登録して、キューに入れる
		public bool MakeNewBoard(NBoard bd, int pos1, int pos2)
		{
			//引数bdのコピーインスタンスmを生成する
			NBoard m = new NBoard(bd);
			//pos1とpos2を交換する
			m.Swap(pos1, pos2);
			//mと同じものが無ければ、bdListに登録する
			if(bdList.IndexOf(m) > None)
			{
				m = null;
				return false;
			}
			else
			{	//mに自分の登録indexを記録
				m.ID = bdList.Count;
				//mのParentID（親）にbdのIDを代入する
				m.ParentID = bd.ID;	//親であるbdのIDを親IDとして記録する
				bdList.Add(m);
			}
			//mが完了形であれば終了
			if(m.IsDone())	//完了確認
			{
				Solved = true;
				return false;
			}
			return true;
		}

		//未完了なら空白ピースを探し、周囲のピースを幅優先検索する
		public void CheckAround(NBoard bd)
		{
			//値Num - 1（空白ピース）の配列位置を探す
			int pos = bd.IndexOf(Num - 1);
			//3 x 3盤の下2行にある場合
			if(!Solved && pos > 2)
				MakeNewBoard(bd, pos, pos - 3);	//上のピースと入替え
			//3 x 3盤の右2列にある場合
			if(!Solved && pos % 3 > 0)
				MakeNewBoard(bd, pos, pos - 1);	//左のピースと入替え
			//3 x 3盤の左2列にある場合
			if(!Solved && pos % 3 < 2)
				MakeNewBoard(bd, pos, pos + 1);	//右のピースと入替え
			//3 x 3盤の上2行にある場合
			if(!Solved && pos < 6)
				MakeNewBoard(bd, pos, pos + 3);	//下のピースと入替え
		}

		//ゲーム開始
		public void Start(bool rnd = false)
		{
			//すべてのbdListに登録された盤面を廃棄する
			bdList.Clear();
			//ゲームは未完了にする
			Solved = false;
			//Pieces配列をランダムに配置し直す
			if(rnd)
				ShuffleArr();		//不可解の配列配置を含む
			else
				SwapArr();			//全て可解の配列配置になる
			//開始時の盤面を表示
			Console.WriteLine(">>> 開始時の盤面 <<<");
			ShowStartBoard();
			Console.Write(Environment.NewLine);
			//先ず開始時の盤面をbdListに登録する
			StartAt = 0;
			stBoard.ID = StartAt;	//自分のIDを記録する
			bdList.Add(stBoard);
			EndAt = bdList.Count;	//EndAt = 1;
			while(StartAt < EndAt)	//盤面が追加されなければ終了
			{
				Layer++;			//世代交代
				for(int i = StartAt; i < EndAt; i++)
					CheckAround(bdList[i]);	//前世代最初の盤面
				StartAt = EndAt;			//ループ後の盤面増
				if(Solved)					//パズルが解けた場合、ループを抜ける
					break;
				else
					EndAt = bdList.Count;	//ループ終了時の盤面数
			}
			if(Solved)				//パズルが解けた場合、ループを抜ける
			{
				TraceBack(bdList.Count - 1);	//終了時の盤面から開始時の盤面まで表示
				Console.WriteLine("8パズルが完成しました。（世代：{0}、総登録盤面数：{1}）", Layer, bdList.Count);
			}
			else
			{
				TraceBack(bdList.Count - 1);	//終了時の盤面から開始時の盤面まで表示
				Console.WriteLine("全ての盤面をチェックしましたが、完成形はありませんでした。（世代：{0}、総登録盤面数：{1})）", Layer, bdList.Count);
			}
		}
	}
}

/*
			//{1, 2, 4, 6, 0, 5, 3, 7, 8};	//解ける初期設定（テスト用）
			stBoard.Set(0, 1);
			stBoard.Set(1, 2);
			stBoard.Set(2, 4);
			stBoard.Set(3, 6);
			stBoard.Set(4, 0);
			stBoard.Set(5, 5);
			stBoard.Set(6, 3);
			stBoard.Set(7, 7);
			stBoard.Set(8, 8);
			return;
			
*/
