using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//ジャンプ情報の配列を作成
DeriveJumpInfoArr();
//反復深化深さ優先探索で解く
for (int I = 2; I < int.MaxValue; I++) {
Console.WriteLine("レベル制限={0}で深さ優先探索中。経過時間={1}", I, sw.Elapsed);
if (ExecDFS(I)) break;
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//ジャンプ情報
struct JumpInfoDef
{
internal char SpacePos;
internal char FromPos;
internal char[] JumpedPosArr;
}
static JumpInfoDef[] JumpInfoArr;
//ジャンプ情報の配列を作成
static void DeriveJumpInfoArr()
{
var JumpInfoList = new List<JumpInfoDef>();
Action<char, char, char[]> AddAct = (pSpacePos, pFromPos, pJumpedPosArr) =>
{
JumpInfoDef WillAdd;
WillAdd.SpacePos = pSpacePos;
WillAdd.FromPos = pFromPos;
WillAdd.JumpedPosArr = pJumpedPosArr;
JumpInfoList.Add(WillAdd);
};
AddAct('A', 'F', new char[] { 'C' });
AddAct('A', 'G', new char[] { 'D' });
AddAct('A', 'I', new char[] { 'F', 'C' });
AddAct('A', 'J', new char[] { 'G', 'D' });
AddAct('B', 'D', new char[] { 'C' });
AddAct('B', 'E', new char[] { 'D', 'C' });
AddAct('B', 'H', new char[] { 'F' });
AddAct('B', 'J', new char[] { 'H', 'F' });
AddAct('C', 'E', new char[] { 'D' });
AddAct('C', 'I', new char[] { 'F' });
AddAct('D', 'B', new char[] { 'C' });
AddAct('D', 'J', new char[] { 'G' });
AddAct('E', 'B', new char[] { 'C', 'D' });
AddAct('E', 'C', new char[] { 'D' });
AddAct('E', 'H', new char[] { 'G' });
AddAct('E', 'I', new char[] { 'H', 'G' });
AddAct('F', 'A', new char[] { 'C' });
AddAct('F', 'J', new char[] { 'H' });
AddAct('G', 'A', new char[] { 'D' });
AddAct('G', 'I', new char[] { 'H' });
AddAct('H', 'B', new char[] { 'F' });
AddAct('H', 'E', new char[] { 'G' });
AddAct('I', 'A', new char[] { 'C', 'F' });
AddAct('I', 'C', new char[] { 'F' });
AddAct('I', 'E', new char[] { 'G', 'H' });
AddAct('I', 'G', new char[] { 'H' });
AddAct('J', 'A', new char[] { 'D', 'G' });
AddAct('J', 'B', new char[] { 'H', 'F' });
AddAct('J', 'D', new char[] { 'G' });
AddAct('J', 'F', new char[] { 'H' });
JumpInfoArr = JumpInfoList.ToArray();
}
struct JyoutaiDef
{
internal Dictionary<char, char> BanDict;
internal int Level;
internal List<string> Log;
}
//深さ制限を引数として、深さ優先探索する
static bool ExecDFS(int pLimitLevel)
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
Action<char> wkAct = pChar =>
{
WillPush.BanDict = new Dictionary<char, char>();
for (char I = 'A'; I <= 'J'; I++) {
WillPush.BanDict.Add(I, I == pChar ? '空' : '○');
}
WillPush.Log = new List<string>();
WillPush.Log.Add(BanToStr(WillPush.BanDict));
stk.Push(WillPush);
};
//対称解の排除で、初期盤面の空白は、AかC
wkAct('A'); wkAct('C');
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.BanDict.Values.Any(X => X == '○') == false) {
Console.WriteLine("{0}手の解を発見", pLimitLevel);
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.BanDict) > pLimitLevel)
continue;
char wkSpacePos =
Popped.BanDict.Keys.First(X => Popped.BanDict[X] == '空');
foreach (JumpInfoDef EachJumpInfo in JumpInfoArr) {
if (EachJumpInfo.SpacePos != wkSpacePos) continue;
//対称解の除外
if (wkSpacePos == 'A' && Popped.Level == 0) {
if (EachJumpInfo.FromPos == 'G') continue;
if (EachJumpInfo.FromPos == 'J') continue;
}
if (wkSpacePos == 'C' && Popped.Level == 0) {
if (EachJumpInfo.FromPos == 'I') continue;
}
WillPush.BanDict = new Dictionary<char, char>(Popped.BanDict);
WillPush.BanDict[wkSpacePos] = WillPush.BanDict[EachJumpInfo.FromPos];
WillPush.BanDict[EachJumpInfo.FromPos] = '空';
Array.ForEach(EachJumpInfo.JumpedPosArr, A =>
WillPush.BanDict[A] = (WillPush.BanDict[A] == '●' ? '○' : '●'));
WillPush.Level = Popped.Level + 1;
WillPush.Log = new List<string>(Popped.Log);
WillPush.Log.Add(BanToStr(WillPush.BanDict));
stk.Push(WillPush);
}
}
return false;
}
//最小の残り手数を返す(下限値枝切り用)
static int DeriveNeedMinTesuu(Dictionary<char, char> pBanDict)
{
//表の枚数 / 2 の余りを切り上げ
int OmoteCnt = pBanDict.Values.Count(X => X == '○');
if (OmoteCnt % 2 == 0) return OmoteCnt / 2;
return OmoteCnt / 2 + 1;
}
//盤面をString型で表現
static string BanToStr(Dictionary<char, char> pBanDict)
{
var wkP = pBanDict;
var sb = new System.Text.StringBuilder();
sb.AppendFormat(" {0}", wkP['A']);
sb.AppendLine();
sb.AppendLine();
sb.AppendFormat("{0} {1}{2} {3}", wkP['B'], wkP['C'], wkP['D'], wkP['E']);
sb.AppendLine();
sb.AppendFormat(" {0} {1}", wkP['F'], wkP['G']);
sb.AppendLine();
sb.AppendFormat(" {0}", wkP['H']);
sb.AppendLine();
sb.AppendFormat(" {0} {1}", wkP['I'], wkP['J']);
sb.AppendLine();
return sb.ToString();
}
}
