using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 9 - 1;
struct JyoutaiDef
{
internal int Level;
internal bool[,] KikiArr;
internal bool[,] HaitiArr;
}
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
//反復深化深さ優先探索で解く
for (int Depth = 1; Depth <= 9 * 9; Depth++) {
Console.WriteLine("深さ制限={0}で解を検証中。経過時間={1}", Depth, sw.Elapsed);
List<bool[,]> AnswerHaitiArrList = ExecDFS(Depth);
if (AnswerHaitiArrList.Count == 0) continue;
//回転を除外
RemoveKaiten(AnswerHaitiArrList);
for (int I = 0; I <= AnswerHaitiArrList.Count - 1; I++) {
Console.WriteLine("(回転除外後の)解{0}", I + 1);
PrintBan(AnswerHaitiArrList[I]);
}
Console.WriteLine("解は{0}通り。経過時間={1}", AnswerHaitiArrList.Count, sw.Elapsed);
break;
}
}
//深さ制限を引数として深さ優先探索を行う
static List<bool[,]> ExecDFS(int pDepthMax)
{
var WillReturnBoolArrList = new List<bool[,]>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.KikiArr = WillPush.HaitiArr = new bool[UB + 1, UB + 1];
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//レベル制限
if (pDepthMax < Popped.Level) continue;
//クリア判定
if (Popped.KikiArr.Cast<bool>().All(X => X)) {
WillReturnBoolArrList.Add(Popped.HaitiArr);
Console.WriteLine("(回転除外前の)解候補{0}を発見。経過時間={1}",
WillReturnBoolArrList.Count, sw.Elapsed);
continue;
}
//最後に龍を配置した座標を求める
int LastRyuX = 0, LastRyuY = 0;
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
if (Popped.HaitiArr[X, Y]) {
LastRyuX = X;
LastRyuY = Y;
}
WillPush.Level = Popped.Level + 1;
var KagentiEdakiriXSet = new HashSet<int>();
for (int Y = LastRyuY; Y <= UB; Y++) {
//回転解の除外で1枚目の龍は左上に配置
if (WillPush.Level == 1 && 3 < Y) break;
for (int X = 0; X <= UB; X++) {
//回転解の除外で1枚目の龍は左上に配置
if (WillPush.Level == 1 && 3 < X) break;
//最後に龍を配置した座標までは、Continue
if (Y == LastRyuY && X <= LastRyuX) continue;
//下限値枝切りされたX座標ならContinue
if (KagentiEdakiriXSet.Contains(X)) continue;
WillPush.KikiArr = (bool[,])Popped.KikiArr.Clone();
SetRyuKikiTrue(WillPush.KikiArr, X, Y);
//下限値枝切り
if (WillPush.Level + CalcNeedMinTesuu(WillPush.KikiArr, Y) > pDepthMax) {
KagentiEdakiriXSet.Add(X);
continue;
}
WillPush.HaitiArr = (bool[,])Popped.HaitiArr.Clone();
WillPush.HaitiArr[X, Y] = true;
stk.Push(WillPush);
}
}
}
return WillReturnBoolArrList;
}
//龍の配置座標を引数として効きの座標をTrueにする
static void SetRyuKikiTrue(bool[,] pHaitiArr, int pX, int pY)
{
pHaitiArr[pX, pY] = true;
for (int X = 0; X <= UB; X++) pHaitiArr[X, pY] = true;
for (int Y = 0; Y <= UB; Y++) pHaitiArr[pX, Y] = true;
Action<int, int> SetNaname = (pNanameX, pNanameY) =>
{
if (pNanameX < 0 || UB < pNanameX) return;
if (pNanameY < 0 || UB < pNanameY) return;
pHaitiArr[pNanameX, pNanameY] = true;
};
SetNaname(pX - 1, pY - 1);
SetNaname(pX - 1, pY + 1);
SetNaname(pX + 1, pY - 1);
SetNaname(pX + 1, pY + 1);
}
//必要な最低手数を求める
static int CalcNeedMinTesuu(bool[,] pKikiArr, int pY)
{
int NeedMinTesuu = 0;
//カレント座標より2つ以上上のマスで効きがなかったら、
//そのマスの下に龍を配置する必要あり
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= pY - 2; Y++) {
if (pKikiArr[X, Y] == false) {
NeedMinTesuu++;
break;
}
}
}
return NeedMinTesuu;
}
//回転を除外
static void RemoveKaiten(List<bool[,]> pTargetList)
{
Predicate<int> IsExist = (pCurrInd) =>
{
for (int I = 0; I <= pCurrInd - 1; I++) {
bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
bool CurrVal = pTargetList[pCurrInd][X, Y];
if (pTargetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
if (pTargetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
if (pTargetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
if (pTargetList[I][Y, X] != CurrVal) IsOK4 = true;
if (pTargetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
if (pTargetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
if (pTargetList[I][Y, UB - X] != CurrVal) IsOK7 = true;
}
}
if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
|| IsOK5 == false || IsOK6 == false || IsOK7 == false)
return true;
}
return false;
};
for (int I = pTargetList.Count - 1; I >= 0; I--) {
if (IsExist(I)) pTargetList.RemoveAt(I);
}
}
//盤面を表示
static void PrintBan(bool[,] pHaitiArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pHaitiArr[X, Y] ? '龍' : '□');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
