using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 7 - 1;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal byte[,] BanArr;
internal int Level;
internal List<ulong> HashLog;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
byte[,] wkArr = new byte[,] {{9,9,1,1,1,9,9},
{9,9,1,1,1,9,9},
{1,1,1,1,1,1,1},
{1,1,1,0,1,1,1},
{1,1,1,1,1,1,1},
{9,9,1,1,1,9,9},
{9,9,1,1,1,9,9}};
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = wkArr;
WillPush.Level = 0;
WillPush.HashLog = new List<ulong>();
WillPush.HashLog.Add(GetHash(WillPush.BanArr));
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<ulong, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
List<ulong> AnswerLog = null;
int AnswerLevel = 18;
bool FoundAnswer = false;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
if (IsClear(Popped.BanArr)) {
if (FoundAnswer == false && Popped.Level == AnswerLevel
|| Popped.Level < AnswerLevel) {
Console.WriteLine("{0}手の解を発見。経過時間={1}", Popped.Level, sw.Elapsed);
FoundAnswer = true;
AnswerLog = Popped.HashLog;
AnswerLevel = Popped.Level;
}
continue;
}
//下限値枝切り
int Kagen = Popped.Level + DeriveNeedMinTesuu(Popped.BanArr);
if (Kagen > AnswerLevel) continue;
if (FoundAnswer && Kagen == AnswerLevel) continue;
var MovedArrList = new List<byte[,]>();
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] != 1) continue;
//盤面とペグの座標を引数として、1手後の盤面のListを返す
PointDef FromPos = new PointDef() { X = LoopX, Y = LoopY };
MovedArrList.AddRange(
DeriveMovedArrList(Popped.BanArr, FromPos));
}
}
foreach (byte[,] EachMovedArr in MovedArrList) {
ulong CurrHash = GetHash(EachMovedArr);
WillPush.BanArr = EachMovedArr;
WillPush.Level = Popped.Level + 1;
//ペグが存在必須のグループにペグがなければ枝切り
if (HasLatestOnePeg(EachMovedArr) == false) continue;
//コーナペグで枝切り
if (WillEdakiriCornerPeg(WillPush.BanArr)) continue;
//メモ化探索
bool IsOK = true;
List<byte[,]> KaitenArrList = CreateKaitenArr(EachMovedArr);
foreach (byte[,] EachKaitenArr in KaitenArrList) {
int MinTesuu;
ulong KaitenHash = GetHash(EachKaitenArr);
if (MinTesuuDict.TryGetValue(KaitenHash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level) {
IsOK = false;
break;
}
}
}
if (IsOK == false) continue;
MinTesuuDict[CurrHash] = WillPush.Level;
WillPush.HashLog = new List<ulong>(Popped.HashLog) { CurrHash };
Stk.Push(WillPush);
}
}
for (int I = 0; I <= AnswerLog.Count - 1; I++) {
Console.WriteLine("{0}手目", I);
PrintBan(AnswerLog[I]);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//クリア判定
static bool IsClear(byte[,] pBanArr)
{
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] == 9) continue;
if (X == 3 && Y == 3) {
if (pBanArr[X, Y] != 1) //中央にペグがなかったらNG
return false;
}
else if (pBanArr[X, Y] != 0) //中央以外にペグがあったらNG
return false;
}
}
return true;
}
//必要な最低手数を求める
static int DeriveNeedMinTesuu(byte[,] pBanArr)
{
int WillReturnCnt = 0;
Action<PointDef> CheckKadoPeg = (pKado) =>
{
if (pBanArr[pKado.X, pKado.Y] == 1) WillReturnCnt++;
};
CheckKadoPeg(new PointDef() { X = 0, Y = 2 });
CheckKadoPeg(new PointDef() { X = 0, Y = 4 });
CheckKadoPeg(new PointDef() { X = 2, Y = 0 });
CheckKadoPeg(new PointDef() { X = 2, Y = 6 });
CheckKadoPeg(new PointDef() { X = 4, Y = 0 });
CheckKadoPeg(new PointDef() { X = 4, Y = 6 });
CheckKadoPeg(new PointDef() { X = 6, Y = 2 });
CheckKadoPeg(new PointDef() { X = 6, Y = 4 });
Action<PointDef, PointDef, PointDef> CheckThreePeg = (pPeg1, pPeg2, pPeg3) =>
{
if (pBanArr[pPeg1.X, pPeg1.Y] == 0) return;
if (pBanArr[pPeg2.X, pPeg2.Y] == 0) return;
if (pBanArr[pPeg3.X, pPeg3.Y] == 0) return;
WillReturnCnt++;
};
PointDef Peg1, Peg2, Peg3;
Peg1.X = 1; Peg1.Y = 2; Peg2.X = 2; Peg2.Y = 1; Peg3.X = 2; Peg3.Y = 2;
CheckThreePeg(Peg1, Peg2, Peg3);
Peg1.X = 4; Peg1.Y = 1; Peg2.X = 4; Peg2.Y = 2; Peg3.X = 5; Peg3.Y = 2;
CheckThreePeg(Peg1, Peg2, Peg3);
Peg1.X = 1; Peg1.Y = 4; Peg2.X = 2; Peg2.Y = 4; Peg3.X = 2; Peg3.Y = 5;
CheckThreePeg(Peg1, Peg2, Peg3);
Peg1.X = 4; Peg1.Y = 4; Peg2.X = 4; Peg2.Y = 5; Peg3.X = 5; Peg3.Y = 4;
CheckThreePeg(Peg1, Peg2, Peg3);
//最後の移動の分
WillReturnCnt++;
return WillReturnCnt;
}
struct MoveInfoDef
{
internal byte[,] BanArr;
internal PointDef FromPos;
}
//盤面とペグの座標を引数として、1手後の盤面のListを返す
static List<byte[,]> DeriveMovedArrList(byte[,] pBanArr, PointDef pFromPos)
{
var WillReturn = new List<byte[,]>();
var Stk = new Stack<MoveInfoDef>();
MoveInfoDef WillPush;
WillPush.BanArr = pBanArr;
WillPush.FromPos = pFromPos;
Stk.Push(WillPush);
var VisitedSet = new HashSet<ulong>();
while (Stk.Count > 0) {
MoveInfoDef Popped = Stk.Pop();
MoveInfoDef[] MovedInfoArr = DeriveMovedInfoArr(Popped.BanArr, Popped.FromPos);
foreach (MoveInfoDef EachJyoutai in MovedInfoArr) {
ulong CurrHash = GetHash(EachJyoutai.BanArr);
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachJyoutai.BanArr);
Stk.Push(EachJyoutai);
}
}
return WillReturn;
}
//盤面とペグの座標を引数として、移動情報の配列を返す
static MoveInfoDef[] DeriveMovedInfoArr(byte[,] pBanArr, PointDef pFromPos)
{
var WillReturn = new List<MoveInfoDef>();
//変位ベクトルのList
var HeniList = new List<PointDef>();
HeniList.Add(new PointDef() { X = 0, Y = -1 });
HeniList.Add(new PointDef() { X = 0, Y = +1 });
HeniList.Add(new PointDef() { X = -1, Y = 0 });
HeniList.Add(new PointDef() { X = +1, Y = 0 });
foreach (PointDef EachHeni in HeniList) {
int MidX = pFromPos.X + EachHeni.X;
int MidY = pFromPos.Y + EachHeni.Y;
int ToX = MidX + EachHeni.X;
int ToY = MidY + EachHeni.Y;
if (ToX < 0 || UB < ToX) continue;
if (ToY < 0 || UB < ToY) continue;
if (pBanArr[MidX, MidY] != 1) continue;
if (pBanArr[ToX, ToY] != 0) continue;
//移動可能な場合
MoveInfoDef WillAdd;
WillAdd.BanArr = (byte[,])pBanArr.Clone();
WillAdd.BanArr[pFromPos.X, pFromPos.Y] = 0;
WillAdd.BanArr[MidX, MidY] = 0;
WillAdd.BanArr[ToX, ToY] = 1;
WillAdd.FromPos = new PointDef() { X = ToX, Y = ToY };
WillReturn.Add(WillAdd);
}
return WillReturn.ToArray();
}
//ペグが存在必須のグループにペグがあるかを返す
static bool HasLatestOnePeg(byte[,] pBanArr)
{
if (pBanArr[1, 3] == 1) return true;
if (pBanArr[3, 1] == 1) return true;
if (pBanArr[3, 3] == 1) return true;
if (pBanArr[3, 5] == 1) return true;
if (pBanArr[5, 3] == 1) return true;
return false;
}
//コーナーペグで枝切り
static bool WillEdakiriCornerPeg(byte[,] pBanArr)
{
//コーナーペグ数(X軸の端)
int CornerCntXJiku = 0;
if (pBanArr[0, 2] == 1) CornerCntXJiku++;
if (pBanArr[0, 4] == 1) CornerCntXJiku++;
if (pBanArr[6, 2] == 1) CornerCntXJiku++;
if (pBanArr[6, 4] == 1) CornerCntXJiku++;
//コーナーペグ数(Y軸の端)
int CornerCntYJiku = 0;
if (pBanArr[2, 0] == 1) CornerCntYJiku++;
if (pBanArr[4, 0] == 1) CornerCntYJiku++;
if (pBanArr[2, 6] == 1) CornerCntYJiku++;
if (pBanArr[4, 6] == 1) CornerCntYJiku++;
//グループBの数
int GroupBCnt = 0;
if (pBanArr[1, 2] == 1) GroupBCnt++;
if (pBanArr[1, 4] == 1) GroupBCnt++;
if (pBanArr[3, 0] == 1) GroupBCnt++;
if (pBanArr[3, 2] == 1) GroupBCnt++;
if (pBanArr[3, 4] == 1) GroupBCnt++;
if (pBanArr[3, 6] == 1) GroupBCnt++;
if (pBanArr[5, 2] == 1) GroupBCnt++;
if (pBanArr[5, 4] == 1) GroupBCnt++;
//グループCの数
int GroupCCnt = 0;
if (pBanArr[0, 3] == 1) GroupCCnt++;
if (pBanArr[2, 1] == 1) GroupCCnt++;
if (pBanArr[2, 3] == 1) GroupCCnt++;
if (pBanArr[2, 5] == 1) GroupCCnt++;
if (pBanArr[4, 1] == 1) GroupCCnt++;
if (pBanArr[4, 3] == 1) GroupCCnt++;
if (pBanArr[4, 5] == 1) GroupCCnt++;
if (pBanArr[6, 3] == 1) GroupCCnt++;
if (CornerCntXJiku > GroupBCnt) return true;
if (CornerCntYJiku > GroupCCnt) return true;
return false;
}
//配列を引数として、回転させた8通りの配列を返す
static List<byte[,]> CreateKaitenArr(byte[,] pBanArr)
{
var WillReturn = new List<byte[,]>();
for (int I = 1; I <= 8; I++) WillReturn.Add(new byte[UB + 1, UB + 1]);
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
byte CurrVal = pBanArr[X, Y];
WillReturn[0][X, Y] = CurrVal;
WillReturn[1][X, UB - Y] = CurrVal;
WillReturn[2][UB - X, Y] = CurrVal;
WillReturn[3][UB - X, UB - Y] = CurrVal;
WillReturn[4][Y, X] = CurrVal;
WillReturn[5][Y, UB - X] = CurrVal;
WillReturn[6][UB - Y, X] = CurrVal;
WillReturn[7][UB - Y, UB - X] = CurrVal;
}
}
return WillReturn;
}
//ハッシュ値を求める
static ulong GetHash(byte[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] == 9) continue;
else if (pBanArr[X, Y] == 0) sb.Append('0');
else if (pBanArr[X, Y] == 1) sb.Append('1');
}
}
return Convert.ToUInt64(sb.ToString(), 2);
}
//ハッシュ値から盤面を表示
static void PrintBan(ulong pHash)
{
byte[] wkArr = new byte[33];
ulong CopiedHash = pHash;
for (int I = 32; 0 <= I; I--) {
wkArr[I] = (byte)(CopiedHash % 2);
CopiedHash /= 2;
}
byte[,] wkBanArr = new byte[UB + 1, UB + 1];
wkBanArr[0, 0] = wkBanArr[0, 1] = 9;
wkBanArr[1, 0] = wkBanArr[1, 1] = 9;
wkBanArr[5, 0] = wkBanArr[5, 1] = 9;
wkBanArr[6, 0] = wkBanArr[6, 1] = 9;
wkBanArr[0, 5] = wkBanArr[0, 6] = 9;
wkBanArr[1, 5] = wkBanArr[1, 6] = 9;
wkBanArr[5, 5] = wkBanArr[5, 6] = 9;
wkBanArr[6, 5] = wkBanArr[6, 6] = 9;
int CurrInd = 0;
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (wkBanArr[X, Y] == 9) continue;
wkBanArr[X, Y] = wkArr[CurrInd++];
}
}
PrintBan(wkBanArr);
}
//盤面を表示
static void PrintBan(byte[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
