オリジナルのC言語プログラムをC#に忠実に移植して作ったプログラムが、しっかりと動いているのに予期した結果が得られない為、オリジナルプログラムのアルゴリズムを生かしながら、C#の得意技を導入する等C#向けに変更したプログラムを作りました。
変更点は以下の通り。
（１）オリジナルでは、BOARD構造体を「親－自分－子」という異なる世代をつなぐ「縦」の関係と、世代の兄弟の「横」の関係を全世代でまとめた「キュー（q0, q1, q2）」に使っていますが、C#ではNBoardクラスとして「親－自分－子」という世代を横切る「縦」の関係のみに使います。（これは「完成形」が発現したら、それから初期盤面までの世代の縦関係を得るために必要です。）その為にNBoardのメンバーを”Back”と"Next"→"index (ID)"と"p_index (ParentID)"へ変更しました。
（２）一方、オリジナルプログラムで「キュー（注）」が扱っていた「横」の関係は（二分木を使わなくとも）単に探索した盤面を登録順にリニアに管理しても問題ありません。従って、これはデータベース言語も取り入れているC#の得意技（System.Collectionsおよび同.Generic）の"List"を使って管理してみました。これにより、総ての盤面データが「明示の参照」となり、GCの対象にはならないことが確実となり、またStartメソッドが簡素になりました。
注：q0, q1, q2の三つある。初期盤面を入れて開始すq1が現「親世代」、q2がその「子世代」（新しい盤面を次々と追加する）、q0が「子世代を作り終えた親世代という世代累計（過去の全盤面）」になります。
【EightPuzzle.cs】
///////////////////////
// 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
//解説：二分木の場合は二分木クラスのインスタンスへのポインターであったが、ここではListにおける整数尾インデックス（何番目のデータか）にしている。
//メンバープロパティ
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; //解説：objをNBoardオブジェクトとして「that」の名前を与えます。
for(int i = 0; i < 9; i++)
if(this.Pieces[i] != that.Pieces[i]) //解説：米国人の好きな、”this and that"したかったのでhitakattanode ...（笑）
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;
}
//配列要素を検索し、あればその位置を返す（無ければNone）
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
{
//メンバー定数（解説：NBoardと同じ。C#も定数はnamespaceを通用範囲にしたいですね。）
const int Num = 9; //配列要素数
const int None = -1; //未設定の定数
//メンバー変数
List <NBoard> bdList; //NBoard配列
private NBoard stBoard; //ゲーム開始時のNBoard
private int StartAt, EndAt; //bdListのCheckAround開始、終了位置（解説：世代がbdListの何番目から始まり終わるのか）
private bool Solved = false; //パズル解決(ture)の完了フラグ
int Layer = 0; //世代を記録
//コンストラクター
public ePuzzle()
{
bdList = new List <NBoard> (); //解説：空のリストを作ります。
stBoard = new NBoard(); //解説：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) //スワップ方式
{
//{2, 3, 5, 7, 1, 6, 4, 8, 0}; //解ける初期設定（テスト用）
stBoard.Set(0, 2);
stBoard.Set(1, 3);
stBoard.Set(2, 5);
stBoard.Set(3, 7);
stBoard.Set(4, 1);
stBoard.Set(5, 6);
stBoard.Set(6, 4);
stBoard.Set(7, 8);
stBoard.Set(8, 0);
return;
/* 解説：開発段階なので↑のテストデータを使用しました。↓も正しく動きます。
//要素数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 //解説：dirが↑（0）でposが最上行（0, 1, 2）であれば
i--; //スワップしないので、やり直しの為にカウンター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; //解説：nullにするとGC対象になります。
return false;
}
else
{ //mに自分の登録indexを記録
m.ID = bdList.Count; //解説：新規登録なので、登録盤面数が次のindexになります。
//mのParentID（親）にbdのIDを代入する
m.ParentID = bd.ID; //親であるbdのIDを親IDとして記録する
bdList.Add(m); //解説：最後にbdListに追加します。
}
//mが完了形であれば終了
if(m.IsDone()) //完了確認
{
Solved = true; //解説：ここで終了するオリジナルのCプログラムと異なり、終了フラグを立てるだけにしました。
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) //解説：オリジナルのCプログラムと異なり、終了フラグを条件に入れました。（以下同じ）
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);
}
}
}
}
これでC#のリストを使ったプログラムとして完璧な筈です。ということで、
実行！
すると、
悪夢！
が再び襲ってきます。
なーんと、結果は、
と、二分木を使ったプログラムの結果である（32世代、9! / 2 = 181,440）
と（最初の盤面の登録時期が異なること以外は）全く同じとなりました。
何故だーーー！
何故C言語のプログラムで解けるパズルがC#では解けないんだーーー！
と嘆き、悩むだけで、その理由は未だ分からなかったのでした。（勿論、Chat-GPS様も。）