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

namespace EightPuzzle
{
	public class App
	{
		//メンバー定数
		const int None = -1;			//未設定の定数

		static void Main()
		{
			ePuzzle ep = new ePuzzle();
			//初期状態
			Console.WriteLine(">>> 初期盤面 <<<");
			ep.GetBoard(None).Show();					//None－開始時の盤面を表示する為の引数
			Console.Write(Environment.NewLine);
			while(true)
			{
				Console.WriteLine("\r\n可能解のみ（1）または不可能解を含む（2）：");
				string v = Console.ReadLine();
				switch(v)
				{
					case "1":
						ep.SwapArr();
						break;
					case "2":
						ep.ShuffleArr();
						break;
					default:
						continue;
				}
				break;
			}
			Console.Write(Environment.NewLine);
			//開始時の盤面を表示
			Console.WriteLine(">>> 開始時の盤面 <<<");
			ep.GetBoard(None).Show();					//None－開始時の盤面を表示する為の引数
			Console.Write(Environment.NewLine);
			//ゲーム開始
			bool Solved = ep.Start();
			//パズルの解を取得
			int[] Solution = ep.GetTraceBack();
			//パズルの解を表示
			for(int i = 0; i < Solution.Length; i++)
			{
				ep.GetBoard(Solution[i]).Show();		//NBoardの表示
				Console.Write(Environment.NewLine);		//改行
			}
			if(Solved)				//パズルが解けた場合、ループを抜ける
				Console.WriteLine("8パズルが完成しました。（世代：{0}、総登録盤面数：{1}）", ep.Generation, ep.Registered);
			else
				Console.WriteLine("全ての盤面をチェックしましたが、完成形はありませんでした。（世代：{0}、総登録盤面数：{1}）", ep.Generation, ep.Registered);
			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)の完了フラグ
		public int Generation			//世代
			{get; private set;}
		public int Registered			//bdList最終登録数
			{get; private set;}
		public int [] Solution;			//パズルの解のbdList盤面引数配列

		//コンストラクター
		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();
		}

		//NBoard盤面データを取得
		public NBoard GetBoard(int n)
		{
			if(n > bdList.Count - 1)			//引数が登録数を超え、不正であれば
				return null;					//ヌルを返す
			else if(n < 0 || bdList.Count == 0)	//引数が負または登録盤面が無ければ
				return stBoard;					//初期盤面を返す
			else								//盤面登録があり引数が適正であれば
				return bdList[n];				//盤面データを返す
		}

		//親がNoneになるまで、親を遡る
		public bool SetTraceBack()
		{
			if(Solved)
			{
				Solution =new int[Generation + 1];
				for(int i = Registered, j = 0; i != None; i = bdList[i].ParentID, j++)
					Solution[j] = i;
				return true;
			}
			else
				return false;
		}

		//親がNoneになるまで、親を遡る
		public int[] GetTraceBack()
		{
			return Solution;
		}

		//ピースを交換した新しいボードが既登録かチェックし、
		//無ければ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 bool Start(bool rnd = false)
		{
			//すべてのbdListに登録された盤面を廃棄する
			bdList.Clear();
			Registered = 0;
			//ゲームは未完了にする
			Solved = false;
			//世代初期化（(stBoardが0世代）
			Generation = 0;
			//先ず開始時の盤面をbdListに登録する
			StartAt = 0;
			stBoard.ID = StartAt;	//自分のIDを記録する
			bdList.Add(stBoard);
			EndAt = bdList.Count;	//EndAt = 1;
			while(StartAt < EndAt)	//盤面が追加されなければ終了
			{
				Generation++;					//世代交代
				for(int i = StartAt; i < EndAt; i++)
					CheckAround(bdList[i]);	//前世代最初の盤面
				StartAt = EndAt;			//ループ後の盤面増
				if(Solved)					//パズルが解けた場合、ループを抜ける
					break;
				else
					EndAt = bdList.Count;	//ループ終了時の盤面数
			}
			Registered = bdList.Count - 1;	//bdListの最終登録数
			SetTraceBack();					//完成盤面から初期盤面までのbdList添字をSolutionに入れる
			return Solved;
		}
	}
}
