using System;
using System.Collections.Generic;
class Program
{
const int UB_X = 2;
const int UB_Y = 3;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal List<string> Log;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//反復深化深さ優先探索で解く
for (int Depth = 2; Depth < int.MaxValue; Depth++) {
Console.WriteLine("深さ制限={0}で解を検証中。経過時間={1}", Depth, sw.Elapsed);
if (ExecDFS(Depth)) break;
}
}
static bool ExecDFS(int pLevelLimit)
{
string[] InitArr ={"172",
"345",
"6*8",
"9AB"};
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
WillPush.BanArr[X, Y] = InitArr[Y][X];
}
}
WillPush.Level = 0;
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsClear(Popped.BanArr)) {
Console.WriteLine("解を発見");
Console.WriteLine("Level={0}", Popped.Level);
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
Console.WriteLine(Popped.Log[I]);
}
return true;
}
if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) > pLevelLimit) continue;
//空白マスの座標を求める
int SpaceX, SpaceY;
DeriveSpaceMasu(Popped.BanArr, out SpaceX, out SpaceY);
//空白マスの4近傍の座標のListを求める
PointDef[] KinbouArr = DeriveKinbouArr(SpaceX, SpaceY);
//Push処理を行う
foreach (PointDef EachKinbou in KinbouArr) {
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[SpaceX, SpaceY] = Popped.BanArr[EachKinbou.X, EachKinbou.Y];
WillPush.BanArr[EachKinbou.X, EachKinbou.Y] = '*';
WillPush.Level = Popped.Level + 1;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanArr));
int MinTesuu;
string wkHash = GetHash(WillPush.BanArr);
if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) continue;
}
MinTesuuDict[wkHash] = WillPush.Level;
Stk.Push(WillPush);
}
}
return false;
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(char[,] pBanArr)
{
int SumKyori = 0;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBanArr[X, Y] == '1') SumKyori += DeriveKyori(X, Y, 0, 0);
if (pBanArr[X, Y] == '2') SumKyori += DeriveKyori(X, Y, 2, 0);
if (pBanArr[X, Y] == '3') SumKyori += DeriveKyori(X, Y, 0, 1);
if (pBanArr[X, Y] == '4') SumKyori += DeriveKyori(X, Y, 1, 1);
if (pBanArr[X, Y] == '5' || pBanArr[X, Y] == '9') {
int Kyori1 = DeriveKyori(X, Y, 2, 1);
int Kyori2 = DeriveKyori(X, Y, 0, 3);
SumKyori += Math.Min(Kyori1, Kyori2);
}
if (pBanArr[X, Y] == '6') SumKyori += DeriveKyori(X, Y, 0, 2);
if (pBanArr[X, Y] == '7') SumKyori += DeriveKyori(X, Y, 1, 2);
if (pBanArr[X, Y] == '8') SumKyori += DeriveKyori(X, Y, 2, 2);
if (pBanArr[X, Y] == 'A') SumKyori += DeriveKyori(X, Y, 1, 3);
if (pBanArr[X, Y] == 'B') SumKyori += DeriveKyori(X, Y, 2, 3);
}
}
return SumKyori;
}
//2つの座標のマンハッタン距離を求める
static int DeriveKyori(int pX1, int pY1, int pX2, int pY2)
{
return Math.Abs(pX1 - pX2) + Math.Abs(pY1 - pY2);
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
string[] GoalArr1 ={"1*2",
"345",
"678",
"9AB"};
string[] GoalArr2 ={"1*2",
"349",
"678",
"5AB"};
bool IsGoal1 = true, IsGoal2 = true;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBanArr[X, Y] != GoalArr1[Y][X]) IsGoal1 = false;
if (pBanArr[X, Y] != GoalArr2[Y][X]) IsGoal2 = false;
}
}
return IsGoal1 || IsGoal2;
}
//空白マスの座標を求める
static void DeriveSpaceMasu(char[,] pBanArr, out int pX, out int pY)
{
pX = pY = -1;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] == '*') {
pX = LoopX; pY = LoopY;
return;
}
}
}
}
//4近傍の座標の配列を求める
static PointDef[] DeriveKinbouArr(int pBaseX, int pBaseY)
{
var WillReturn = new List<PointDef>();
Action<int, int> wkAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
WillReturn.Add(new PointDef() { X = pX, Y = pY });
};
wkAct(pBaseX, pBaseY - 1);
wkAct(pBaseX, pBaseY + 1);
wkAct(pBaseX - 1, pBaseY);
wkAct(pBaseX + 1, pBaseY);
return WillReturn.ToArray();
}
//ハッシュ値を求める
static string GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
sb.Append(pBanArr[X, Y]);
}
}
return sb.ToString();
}
//盤面をString型で表現
static string BanToStr(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
return sb.ToString();
}
}
ゴール
