///////////////////////
//     8Puzzle.cs
// Copyright (c) 2025
//     by Ysama
///////////////////////
using System;

namespace Eight_Puzzle
{
	public class App
	{
		static void Main()
		{
			EightPuzzle ep = new EightPuzzle();
			Console.WriteLine(">>> 開始時の盤面 <<<");
			ep.ShowStartBoard();
			Console.Write(Environment.NewLine);
			ep.Start();
			Console.ReadLine();
		}
	}

	//3 x 3 盤面クラス
	public class NBoard
	{
		//メンバーフィールド
		const int Num = 9;				//ピース数
		private int [] Pieces;			//8パズルの9ピース配列
		NBoard next = null;				//子NBoardの盤面
		NBoard back = null;				//親NBoardの盤面

		//メンバープロパティ
		public NBoard Next				//nextのプロパティ
		{
			get {return next;}
			set {next = value;}
		}
		public NBoard Back				//backのプロパティ
		{
			get {return back;}
			set {back = 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];
				next = bd.Next;
				back = bd.Back;
			}
		}

		//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 bool IsSame(NBoard bd)
		{
			if(bd == null)
				return false;			//nullであればそもそも比較不可
			for(int i = 0; i < Num; i++)
				if(Pieces[i] != bd.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);
			}
		}
	}

	//8Puzzleクラス
	public class EightPuzzle
	{
		//メンバー定数
		const int Num = 9;			//配列要素数

		//メンバー変数
		private NBoard stBoard;		//ゲーム開始時のNBoard
		private NBoard [] Que;		//幅優先検索用のキュー
		int NumOfBoards = 0;		//Que登録盤面数

		public EightPuzzle()		//コンストラクター
		{
			stBoard = new NBoard();						//開始盤面
			SwapArr(false);								//初期値をランダムにばらす
			Que = new NBoard[3] {null, stBoard, null};	//空白ピース周囲のNBoardのキュー(2→1→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();
		}

		//親がnullになるまで、親を遡る
		public void TraceBack(NBoard bd)
		{
			int Counter = 0;
			NBoard n;
			for(n = bd; n != null; n = n.Back)
			{
				n.Show();
				Console.Write(Environment.NewLine);
				Counter++;
			}
			Console.WriteLine("TraceBack終了（盤面交換数：" + Counter.ToString() + "回、登録盤面数：" + NumOfBoards.ToString() + "回）");
		}

		//新しいNBoard bdをQue[2]の連鎖に登録する
		public bool IntoQue(NBoard bd)
		{
			if(Que[2] == null)			//初回はQue[2]がnullなので直接bdを登録する
				Que[2] = bd;
			else						//次回以降Que[2]に登録があるので
			{
				//Que[2]の子孫にbdと同一のものがあるか確認し、
				NBoard n;
				for(n = Que[2]; n != null; n = n.Next)
				{
					if(bd.IsSame(n))
					{
						bd = null;		//引数のbdをGC対象にする
						return false;
					}
					if(n.Next == null)
						break;
				}
				n.Next = bd;	//引数のbdを連鎖の最後に登録する
			}
			NumOfBoards++;		//登録数をカウント
			return true;
		}

		//bdの位置pos1とpos2を交換した新しいボードをキューに登録する
		public bool MakeNewNBoard(NBoard bd, int pos1, int pos2)
		{
			//bdのNBoardコピーインスタンスmを生成する
			NBoard m = new NBoard(bd);
			//pos1とpos2を交換する
			m.Swap(pos1, pos2);
			//mのBack（親）にbdを、Nextにnullを代入する
			m.Back = bd;
			m.Next = null;
			//完了確認（mがBG＜完了形＞であれば、そう表示して終了
			if(m.IsDone())
			{
				TraceBack(m);
				Console.WriteLine("{0}の盤面を探索し、8パズルが完成しました。", NumOfBoards);
				Console.ReadLine();
				Environment.Exit(0);
				return false;
			}

			//完了しなければQue[0]の子孫にmと同一のものがあるか確認し、
			for(NBoard n = Que[0]; n != null; n = n.Next)
			{
				if(m.IsSame(n))
				{
					m = null;		//あればmをGC対象にする
					return false;
				}
			}

			//無ければキューにmを置く
			IntoQue(m);
			return true;
		}

		public void CheckAround(NBoard bd)
		{
			//値Num - 1（空白ピース）の配列位置を探す
			int pos = bd.IndexOf(Num - 1);
			//3 x 3盤の下2行にある場合
			if(pos > 2)
				MakeNewNBoard(bd, pos, pos - 3);	//上のピースと入替え
			//3 x 3盤の右2列にある場合
			if(pos % 3 > 0)
				MakeNewNBoard(bd, pos, pos - 1);	//左のピースと入替え
			//3 x 3盤の左2列にある場合
			if(pos % 3 < 2)
				MakeNewNBoard(bd, pos, pos + 1);	//右のピースと入替え
			//3 x 3盤の上2行にある場合
			if(pos < 6)
				MakeNewNBoard(bd, pos, pos + 3);	//下のピースと入替え
		}

		public void Start()
		{
			while(Que[1] != null)
			{
				for(NBoard n = Que[1]; n != null; n = n.Next)
					CheckAround(n);
				Que[0] = Que[1];
				Que[1] = Que[2];
				Que[2] = null;
			}
			//失敗した場合の盤の推移を表示（追加）
			for(NBoard n = Que[0]; n != null; n = n.Next)
				if(n.Next == null)
					TraceBack(n);
			//失敗の表示（追加）
			Console.WriteLine("全ての盤面検索（{0}）を終了しましたが、完成形はありませんでした。\r\n", NumOfBoards);
		}
	}
}

/*
			//{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;
*/
