using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 4 - 1;
static int[,] QuestionArr;
static int DepthLimit;
static int FirstDepthLimit;
static string PathToCorrectTo2 = "";
static string PathToCorrectTo4 = "";
static string PathToCorrectTo8 = "";
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
int[,] Q0 = new int[,] {{ 1, 2, 3, 4,}, //1
{ 0, 5, 6, 7,}, //2
{ 9,10,11, 8,}, //3
{13,14,15,12,}}; //4;
//1〜15 縦配列
int[,] Q1 = new int[,]{{ 1, 5, 9,13},
{ 2, 6,10,14},
{ 3, 7,11,15},
{ 4, 8,12, 0}};
//大小逆転配列
int[,] Q3 = new int[,]{{15,14,13,12},
{11,10, 9, 8},
{ 7, 6, 5, 4},
{ 3, 2, 1, 0}};
//上り下り配列
int[,] Q4 = new int[,]{{ 4, 5,12,13},
{ 3, 6,11,14},
{ 2, 7,10,15},
{ 1, 8, 9, 0}};
//対角線配列
int[,] Q5 = new int[,]{{ 7,11,14, 0},
{ 4, 8,12,15},
{ 2, 5, 9,13},
{ 1, 3, 6,10}};
//奇数偶数交互線配列
int[,] Q6 = new int[,]{{ 1, 3, 5, 7},
{ 2, 4, 6, 8},
{ 9,11,13,15},
{10,12,14, 0}};
//ラセン1配列
int[,] Q7 = new int[,]{{ 7, 8, 9,10},
{ 6, 1, 2,11},
{ 5, 4, 3,12},
{ 0,15,14,13}};
//ラセン2配列
int[,] Q8 = new int[,]{{ 1, 2, 3, 4},
{12,13,14, 5},
{11, 0,15, 6},
{10, 9, 8, 7}};
int[,] wkArr = Q3;
QuestionArr = new int[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
QuestionArr[X, Y] = wkArr[Y, X];
}
}
bool HasEvenKai = true; //解の手数が偶数か？
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (QuestionArr[X, Y] == 0) {
HasEvenKai = ((X + Y) % 2 == 0);
}
}
}
FirstDepthLimit = (HasEvenKai ? 2 : 1);
for (DepthLimit = FirstDepthLimit; DepthLimit <= 80; DepthLimit += 2) {
bool FoundTo2 = (PathToCorrectTo2 != "");
bool FoundTo4 = (PathToCorrectTo4 != "");
bool FoundTo8 = (PathToCorrectTo8 != "");
Console.WriteLine("手数上限={0}で探索中。FoundTo2={1},FoundTo4={2},FoundTo8={3}",
DepthLimit, FoundTo2, FoundTo4, FoundTo8);
bool FoundSamLoyd;
string LastMoveLog = ExecDFS(out FoundSamLoyd);
//文字を5文字ずつ出力
Action<string> OutString5MojiZutu = pStr =>
{
for (int I = 0; I <= pStr.Length - 1; I++) {
Console.Write(pStr[I]);
if (I < pStr.Length - 1 && I % 5 == 4) Console.WriteLine();
};
Console.WriteLine();
};
if (LastMoveLog != "") {
int SumTesuu = PathToCorrectTo2.Length + PathToCorrectTo4.Length
+ PathToCorrectTo8.Length + LastMoveLog.Length;
if (FoundSamLoyd) {
Console.WriteLine("この問題の解はありません。経過時間{0}", sw.Elapsed);
Console.WriteLine("サムロイドの懸賞問題の形までの{0}手を表示します。", SumTesuu);
}
else {
Console.WriteLine("{0}手の解を発見。経過時間{1}", SumTesuu, sw.Elapsed);
}
if (PathToCorrectTo2 != "") {
Console.WriteLine("12までの手順は");
OutString5MojiZutu(PathToCorrectTo2);
}
if (PathToCorrectTo4 != "") {
Console.WriteLine("1234までの手順は");
OutString5MojiZutu(PathToCorrectTo4);
}
if (PathToCorrectTo8 != "") {
Console.WriteLine("12345678までの手順は");
OutString5MojiZutu(PathToCorrectTo8);
}
Console.WriteLine("以降の手順は");
OutString5MojiZutu(LastMoveLog);
break;
}
}
}
struct JyoutaiDef
{
internal int Level;
internal int[,] Ban;
internal string MoveLog;
internal char PreMove;
internal bool CorrectTo2;
internal bool CorrectTo4;
internal bool CorrectTo8;
internal int[] NeedTesuuArr;
}
//反復深化深さ優先探索を行う
static string ExecDFS(out bool pFoundSamLoyd)
{
pFoundSamLoyd = false;
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.Ban = QuestionArr;
WillPush.MoveLog = "";
WillPush.PreMove = '\0';
WillPush.CorrectTo2 = IsCorrectPlace(QuestionArr, 2);
WillPush.CorrectTo4 = IsCorrectPlace(QuestionArr, 4);
WillPush.CorrectTo8 = IsCorrectPlace(QuestionArr, 8);
WillPush.NeedTesuuArr = new int[15];
for (int I = 1; I <= 15; I++) {
WillPush.NeedTesuuArr[I - 1] = NeedMinTesuuForNum(QuestionArr, I);
}
stk.Push(WillPush);
//盤面に対する最少手数のDict
var SortedMinTesuuDict = new SortedDictionary<ulong, int>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (IsCorrectPlace(Popped.Ban, 15)) return Popped.MoveLog;
//サムロイドの懸賞問題の形の判定
if (Popped.CorrectTo8 && IsSamLoydQuestion(Popped.Ban)) {
pFoundSamLoyd = true;
return Popped.MoveLog;
}
int X = 0, Y = 0;
while (Popped.Ban[X, Y] != 0) {
if (++X > UB) {
Y++; X = 0;
}
}
WillPush.Level = Popped.Level + 1;
bool WillQuestionReWrite = false;
Action<int, int, char> PushSyori = (pFromX, pFromY, pMoveLog) =>
{
WillQuestionReWrite = false;
int MoveNum = Popped.Ban[pFromX, pFromY];
if (Popped.CorrectTo2 && MoveNum <= 2) return;
if (Popped.CorrectTo4 && MoveNum <= 4) return;
if (Popped.CorrectTo8 && MoveNum <= 8) return;
WillPush.Ban = (int[,])Popped.Ban.Clone();
WillPush.Ban[X, Y] = MoveNum;
WillPush.Ban[pFromX, pFromY] = 0;
WillPush.NeedTesuuArr = (int[])Popped.NeedTesuuArr.Clone();
WillPush.NeedTesuuArr[MoveNum - 1] = NeedMinTesuuForNum(WillPush.Ban, MoveNum);
if (WillPush.Level + WillPush.NeedTesuuArr.Sum() > DepthLimit) return;
ulong BanULong = BanToULong(WillPush.Ban);
//当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
int MinTesuu;
if (SortedMinTesuuDict.TryGetValue(BanULong, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) return;
}
SortedMinTesuuDict[BanULong] = WillPush.Level;
WillPush.MoveLog = Popped.MoveLog + pMoveLog;
WillPush.PreMove = pMoveLog;
//12まで正しい位置
//1234まで正しい位置
//12345678まで正しい位置
//のいずれかだったら問題を差し替え
WillPush.CorrectTo2 = Popped.CorrectTo2;
WillPush.CorrectTo4 = Popped.CorrectTo4;
WillPush.CorrectTo8 = Popped.CorrectTo8;
if (WillPush.CorrectTo8 == false) {
if (WillPush.CorrectTo8 = IsCorrectPlace(WillPush.Ban, 8)) {
PathToCorrectTo8 = WillPush.MoveLog;
WillPush.CorrectTo4 = WillPush.CorrectTo2 = true;
WillQuestionReWrite = true;
}
}
if (WillPush.CorrectTo4 == false) {
if (WillPush.CorrectTo4 = IsCorrectPlace(WillPush.Ban, 4)) {
PathToCorrectTo4 = WillPush.MoveLog;
WillPush.CorrectTo2 = true;
WillQuestionReWrite = true;
}
}
if (WillPush.CorrectTo2 == false) {
if (WillPush.CorrectTo2 = IsCorrectPlace(WillPush.Ban, 2)) {
PathToCorrectTo2 = WillPush.MoveLog;
WillQuestionReWrite = true;
}
}
if (WillQuestionReWrite) { //問題の差し替え
QuestionArr = WillPush.Ban;
DepthLimit = FirstDepthLimit;
return;
}
stk.Push(WillPush);
};
//左の数字を、右に移動
if (X > 0 && Popped.PreMove != '←') PushSyori(X - 1, Y, '→');
if (WillQuestionReWrite) return "";
//右の数字を、左に移動
if (X < UB && Popped.PreMove != '→') PushSyori(X + 1, Y, '←');
if (WillQuestionReWrite) return "";
//上の数字を、下に移動
if (Y > 0 && Popped.PreMove != '↑') PushSyori(X, Y - 1, '↓');
if (WillQuestionReWrite) return "";
//下の数字を、上に移動
if (Y < UB && Popped.PreMove != '↓') PushSyori(X, Y + 1, '↑');
if (WillQuestionReWrite) return "";
}
return "";
}
//盤面を符号なしLong型で表現
static ulong BanToULong(int[,] pBan)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBan[X, Y] == 10) sb.Append('A');
else if (pBan[X, Y] == 11) sb.Append('B');
else if (pBan[X, Y] == 12) sb.Append('C');
else if (pBan[X, Y] == 13) sb.Append('D');
else if (pBan[X, Y] == 14) sb.Append('E');
else if (pBan[X, Y] == 15) sb.Append('F');
else sb.Append(pBan[X, Y]);
}
}
return Convert.ToUInt64(sb.ToString(), 16);
}
//1から指定した値までの位置が正しい位置かを返す
static bool IsCorrectPlace(int[,] pBan, int pToNum)
{
int MustNumber = 0;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
++MustNumber;
if (pBan[X, Y] != MustNumber) return false;
if (MustNumber == pToNum) return true;
}
}
return true;
}
//サムロイドの懸賞問題の形かを返す
static bool IsSamLoydQuestion(int[,] pBan)
{
if (IsCorrectPlace(pBan, 13) == false) return false;
if (pBan[1, 3] != 15) return false;
if (pBan[2, 3] != 14) return false;
return true;
}
//指定した数字が正しい位置に到達するのに必要な、最少手数を求める
static int NeedMinTesuuForNum(int[,] pBan, int pTargetNum)
{
int X1 = 0, Y1 = 0;
if (pTargetNum == 1) { X1 = 0; Y1 = 0; }
if (pTargetNum == 2) { X1 = 1; Y1 = 0; }
if (pTargetNum == 3) { X1 = 2; Y1 = 0; }
if (pTargetNum == 4) { X1 = 3; Y1 = 0; }
if (pTargetNum == 5) { X1 = 0; Y1 = 1; }
if (pTargetNum == 6) { X1 = 1; Y1 = 1; }
if (pTargetNum == 7) { X1 = 2; Y1 = 1; }
if (pTargetNum == 8) { X1 = 3; Y1 = 1; }
if (pTargetNum == 9) { X1 = 0; Y1 = 2; }
if (pTargetNum == 10) { X1 = 1; Y1 = 2; }
if (pTargetNum == 11) { X1 = 2; Y1 = 2; }
if (pTargetNum == 12) { X1 = 3; Y1 = 2; }
if (pTargetNum == 13) { X1 = 0; Y1 = 3; }
if (pTargetNum == 14) { X1 = 1; Y1 = 3; }
if (pTargetNum == 15) { X1 = 2; Y1 = 3; }
int X2, Y2;
SearchNumXY(pBan, pTargetNum, out X2, out Y2);
return Math.Abs(X1 - X2) + Math.Abs(Y1 - Y2);
}
//指定した数字の存在する座標を返す
static void SearchNumXY(int[,] pBan, int pTargetNum, out int pX, out int pY)
{
pX = pY = -1;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBan[X, Y] == pTargetNum) {
pX = X;
pY = Y;
return;
}
}
}
}
}
