using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 24;
struct JyoutaiDef
{
internal bool[] BanArr;
internal int Level;
internal List<uint> HashLog;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//ノード間のネットワーク図を作成
DeriveNodeNetWork();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new bool[UB + 1];
for (int I = 0; I <= UB; I++) {
WillPush.BanArr[I] = true;
}
WillPush.BanArr[11] = false;
WillPush.Level = 0;
uint StaHash = GetHash(WillPush.BanArr);
WillPush.HashLog = new List<uint>() { StaHash };
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<ulong, int>();
MinTesuuDict.Add(StaHash, 0);
List<uint> AnswerLog = null;
int AnswerLevel = 12;
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<bool[]>();
for (int I = 0; I <= UB; I++) {
if (Popped.BanArr[I] == false) continue;
//盤面とペグの位置を引数として、1手後の盤面のListを返す
MovedArrList.AddRange(DeriveMovedArrList(Popped.BanArr, I));
}
foreach (bool[] EachMovedArr in MovedArrList) {
uint CurrHash = GetHash(EachMovedArr);
WillPush.BanArr = EachMovedArr;
WillPush.Level = Popped.Level + 1;
//ペグが存在必須のグループにペグがなければ枝切り
if (HasLatestOnePeg(EachMovedArr) == false) continue;
//メモ化探索
bool IsOK = true;
List<bool[]> KaitenArrList = CreateKaitenArr(EachMovedArr);
foreach (bool[] EachKaitenArr in KaitenArrList) {
int MinTesuu;
uint 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<uint>(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);
}
//移動のネットワーク図
struct NodeNetWork
{
internal int FromInd;
internal int JumpInd;
internal int ToInd;
}
static NodeNetWork[] mNodeNetWorkArr;
//移動のネットワーク図を作成
static void DeriveNodeNetWork()
{
var NodeNetWorkList = new List<NodeNetWork>();
Action<int, int, int> AddAct = (pFromInd, pJumpInd, pToInd) =>
{
NodeNetWorkList.Add(
new NodeNetWork() { FromInd = pFromInd, JumpInd = pJumpInd, ToInd = pToInd });
NodeNetWorkList.Add(
new NodeNetWork() { FromInd = pToInd, JumpInd = pJumpInd, ToInd = pFromInd });
};
AddAct(0, 2, 5); AddAct(0, 3, 7);
AddAct(1, 3, 6); AddAct(1, 4, 8);
AddAct(2, 3, 4); AddAct(2, 5, 9); AddAct(2, 6, 11);
AddAct(3, 6, 10); AddAct(3, 7, 12);
AddAct(4, 7, 11); AddAct(4, 8, 13);
AddAct(5, 6, 7); AddAct(5, 9, 14); AddAct(5, 10, 16);
AddAct(6, 7, 8); AddAct(6, 10, 15); AddAct(6, 11, 17);
AddAct(7, 11, 16); AddAct(7, 12, 18);
AddAct(8, 12, 17); AddAct(8, 13, 19);
AddAct(9, 10, 11); AddAct(9, 15, 21);
AddAct(10, 11, 12); AddAct(10, 15, 20); AddAct(10, 16, 22);
AddAct(11, 12, 13); AddAct(11, 16, 21); AddAct(11, 17, 23);
AddAct(12, 17, 22); AddAct(12, 18, 24);
AddAct(13, 18, 23);
AddAct(14, 15, 16);
AddAct(15, 16, 17);
AddAct(16, 17, 18);
AddAct(17, 18, 19);
AddAct(20, 21, 22);
AddAct(21, 22, 23);
AddAct(22, 23, 24);
mNodeNetWorkArr = NodeNetWorkList.ToArray();
}
//クリア判定
static bool IsClear(bool[] pBanArr)
{
//中央にペグがなかったらNG
if (pBanArr[11] == false) return false;
//ペグが1個しかなければOK
return pBanArr.Count(X => X) == 1;
}
//必要な最低手数を求める
static int DeriveNeedMinTesuu(bool[] pBanArr)
{
int WillReturn = 0;
if (pBanArr[0]) WillReturn++;
if (pBanArr[1]) WillReturn++;
if (pBanArr[14]) WillReturn++;
if (pBanArr[20]) WillReturn++;
if (pBanArr[19]) WillReturn++;
if (pBanArr[24]) WillReturn++;
Action<int, int, int> wkAct = (p1, p2, p3) =>
{
if (pBanArr[p1] && pBanArr[p2] && pBanArr[p3])
WillReturn++;
};
wkAct(2, 5, 9);
wkAct(4, 8, 13);
wkAct(21, 22, 23);
if (WillReturn == 0) WillReturn = 1;
return WillReturn;
}
struct MoveInfoDef
{
internal bool[] BanArr;
internal int FromInd;
}
//盤面とペグの位置を引数として、1手後の盤面のListを返す
static List<bool[]> DeriveMovedArrList(bool[] pBanArr, int pFromInd)
{
var WillReturn = new List<bool[]>();
var Stk = new Stack<MoveInfoDef>();
MoveInfoDef WillPush;
WillPush.BanArr = pBanArr;
WillPush.FromInd = pFromInd;
Stk.Push(WillPush);
var VisitedSet = new HashSet<ulong>();
while (Stk.Count > 0) {
MoveInfoDef Popped = Stk.Pop();
MoveInfoDef[] MovedInfoArr = DeriveMovedInfoArr(Popped.BanArr, Popped.FromInd);
foreach (MoveInfoDef EachJyoutai in MovedInfoArr) {
uint CurrHash = GetHash(EachJyoutai.BanArr);
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachJyoutai.BanArr);
Stk.Push(EachJyoutai);
}
}
return WillReturn;
}
//盤面とペグの位置を引数として、移動情報の配列を返す
static MoveInfoDef[] DeriveMovedInfoArr(bool[] pBanArr, int pFromInd)
{
var WillReturn = new List<MoveInfoDef>();
foreach (NodeNetWork EachNodeNetWork in mNodeNetWorkArr) {
if (EachNodeNetWork.FromInd != pFromInd) continue;
int JumpInd = EachNodeNetWork.JumpInd;
int ToInd = EachNodeNetWork.ToInd;
if (pBanArr[JumpInd] == false) continue;
if (pBanArr[ToInd]) continue;
//移動可能な場合
MoveInfoDef WillAdd;
WillAdd.BanArr = (bool[])pBanArr.Clone();
WillAdd.BanArr[pFromInd] = false;
WillAdd.BanArr[JumpInd] = false;
WillAdd.BanArr[ToInd] = true;
WillAdd.FromInd = ToInd;
WillReturn.Add(WillAdd);
}
return WillReturn.ToArray();
}
//ペグが存在必須のグループにペグがあるかを返す
static bool HasLatestOnePeg(bool[] pBanArr)
{
if (pBanArr[2]) return true;
if (pBanArr[4]) return true;
if (pBanArr[9]) return true;
if (pBanArr[11]) return true;
if (pBanArr[13]) return true;
if (pBanArr[21]) return true;
if (pBanArr[23]) return true;
return false;
}
//配列を引数として、回転させた配列を返す
static List<bool[]> CreateKaitenArr(bool[] pBanArr)
{
var WillReturn = new List<bool[]>();
bool[] Kaiten060Do = DeriveKaiten60Do(pBanArr);
bool[] Kaiten120Do = DeriveKaiten60Do(Kaiten060Do);
bool[] Kaiten180Do = DeriveKaiten60Do(Kaiten120Do);
bool[] Kaiten240Do = DeriveKaiten60Do(Kaiten180Do);
bool[] Kaiten300Do = DeriveKaiten60Do(Kaiten240Do);
bool[] wkHanten = SayuuHanten(pBanArr);
bool[] wkHanten060Do = DeriveKaiten60Do(wkHanten);
bool[] wkHanten120Do = DeriveKaiten60Do(wkHanten060Do);
bool[] wkHanten180Do = DeriveKaiten60Do(wkHanten120Do);
bool[] wkHanten240Do = DeriveKaiten60Do(wkHanten180Do);
bool[] wkHanten300Do = DeriveKaiten60Do(wkHanten240Do);
WillReturn.Add(pBanArr);
WillReturn.Add(Kaiten060Do);
WillReturn.Add(Kaiten120Do);
WillReturn.Add(Kaiten180Do);
WillReturn.Add(Kaiten240Do);
WillReturn.Add(Kaiten300Do);
WillReturn.Add(wkHanten);
WillReturn.Add(wkHanten060Do);
WillReturn.Add(wkHanten120Do);
WillReturn.Add(wkHanten180Do);
WillReturn.Add(wkHanten240Do);
WillReturn.Add(wkHanten300Do);
return WillReturn;
}
//60度回転させた盤面を返す
static bool[] DeriveKaiten60Do(bool[] pBanArr)
{
bool[] WillReturn = new bool[UB + 1];
WillReturn[0] = pBanArr[20];
WillReturn[1] = pBanArr[14];
WillReturn[2] = pBanArr[21];
WillReturn[3] = pBanArr[15];
WillReturn[4] = pBanArr[9];
WillReturn[5] = pBanArr[22];
WillReturn[6] = pBanArr[16];
WillReturn[7] = pBanArr[10];
WillReturn[8] = pBanArr[5];
WillReturn[9] = pBanArr[23];
WillReturn[10] = pBanArr[17];
WillReturn[11] = pBanArr[11];
WillReturn[12] = pBanArr[6];
WillReturn[13] = pBanArr[2];
WillReturn[14] = pBanArr[24];
WillReturn[15] = pBanArr[18];
WillReturn[16] = pBanArr[12];
WillReturn[17] = pBanArr[7];
WillReturn[18] = pBanArr[3];
WillReturn[19] = pBanArr[0];
WillReturn[20] = pBanArr[19];
WillReturn[21] = pBanArr[13];
WillReturn[22] = pBanArr[8];
WillReturn[23] = pBanArr[4];
WillReturn[24] = pBanArr[1];
return WillReturn;
}
//左右反転させた盤面を返す
static bool[] SayuuHanten(bool[] pBanArr)
{
bool[] WillReturn = new bool[UB + 1];
Action<int, int> SetAct = (pFromInd, pToInd) =>
{
while (true) {
WillReturn[pFromInd] = pBanArr[pToInd];
WillReturn[pToInd] = pBanArr[pFromInd];
pFromInd++; pToInd--;
if (pFromInd > pToInd) break;
}
};
SetAct(0, 1);
SetAct(2, 4);
SetAct(5, 8);
SetAct(9, 13);
SetAct(14, 19);
SetAct(20, 24);
return WillReturn;
}
//ハッシュ値を求める
static uint GetHash(bool[] pBanArr)
{
var sb = new System.Text.StringBuilder();
Array.ForEach(pBanArr, X => sb.Append(X ? "1" : "0"));
return Convert.ToUInt32(sb.ToString(), 2);
}
//ハッシュ値から盤面を表示
static void PrintBan(uint pHash)
{
bool[] wkBanArr = new bool[UB + 1];
uint CopiedHash = pHash;
for (int I = UB; 0 <= I; I--) {
wkBanArr[I] = (CopiedHash % 2 == 1);
CopiedHash /= 2;
}
PrintBan(wkBanArr);
}
//盤面を表示
static void PrintBan(bool[] pBanArr)
{
var sb = new System.Text.StringBuilder();
Action<int, int> AppendAct = (pStaInd, pEndInd) =>
{
for (int I = pStaInd; I <= pEndInd; I++)
sb.Append(pBanArr[I] ? '●' : '□');
};
sb.Append(" "); AppendAct(0, 1); sb.AppendLine();
sb.Append(" "); AppendAct(2, 4); sb.AppendLine();
sb.Append(" "); AppendAct(5, 8); sb.AppendLine();
sb.Append(" "); AppendAct(9, 13); sb.AppendLine();
AppendAct(14, 19); sb.AppendLine();
sb.Append(" "); AppendAct(20, 24); sb.AppendLine();
Console.WriteLine(sb.ToString());
}
}
