using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//const int UB = 6 - 1; //6*6の盤
const int UB = 7 - 1; //7*7の盤
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal bool[,] IsBlackArr;
internal bool[,] IsWhiteArr;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.IsBlackArr = new bool[UB + 1, UB + 1];
WillPush.IsWhiteArr = new bool[UB + 1, UB + 1];
//(0,0)が黒の解に対応して、(0,0)が白の解が存在するので、
//(0,0)は黒固定とする
WillPush.IsBlackArr[0, 0] = true;
stk.Push(WillPush);
var AnswerBanList = new List<bool[,]>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (++Popped.CurrX > UB) {
Popped.CurrY++;
Popped.CurrX = 0;
}
if (Popped.CurrY > UB) {
AnswerBanList.Add(Popped.IsBlackArr);
continue;
}
WillPush.CurrX = Popped.CurrX;
WillPush.CurrY = Popped.CurrY;
//黒をセット
if (ExistSquare(Popped.IsBlackArr, WillPush.CurrX, WillPush.CurrY) == false) {
WillPush.IsWhiteArr = Popped.IsWhiteArr;
WillPush.IsBlackArr = (bool[,])Popped.IsBlackArr.Clone();
WillPush.IsBlackArr[WillPush.CurrX, WillPush.CurrY] = true;
stk.Push(WillPush);
}
//白をセット
if (ExistSquare(Popped.IsWhiteArr, WillPush.CurrX, WillPush.CurrY) == false) {
WillPush.IsWhiteArr = (bool[,])Popped.IsWhiteArr.Clone();
WillPush.IsWhiteArr[WillPush.CurrX, WillPush.CurrY] = true;
WillPush.IsBlackArr = Popped.IsBlackArr;
stk.Push(WillPush);
}
}
Console.WriteLine("{0}*{0}の盤で検証しました。経過時間は{1}", UB + 1, sw.Elapsed);
if (AnswerBanList.Count == 0) {
Console.WriteLine("解はありませんでした。");
return;
}
//回転を除外
RemoveKaiten(AnswerBanList);
for (int I = 0; I <= AnswerBanList.Count - 1; I++) {
int BlackCnt = AnswerBanList[I].Cast<bool>().Count(X => X);
int WhiteCnt = AnswerBanList[I].Cast<bool>().Count(X => X == false);
Console.WriteLine("解{0} 黒数{1}、白数{2}", I + 1, BlackCnt, WhiteCnt);
PrintBan(AnswerBanList[I]);
}
}
//正方形の存在判定メソッド
static bool ExistSquare(bool[,] pTargetArr, int pCurrX, int pCurrY)
{
//3個以下なら、正方形は存在しない
if (pTargetArr.Cast<bool>().Count(X => X) <= 3) return false;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pTargetArr[X, Y]) {
if (ExistSquareHelper(pTargetArr, pCurrX, pCurrY,
X - pCurrX, Y - pCurrY)) return true;
}
}
}
return false;
}
//正方形の存在判定メソッド(ヘルパ)
static bool ExistSquareHelper(bool[,] pTargetArr, int pCurrX, int pCurrY,
int pHeniX, int pHeniY)
{
//盤上の点か？
Func<int, int, bool> IsBanJyou = (pX, pY) =>
{
if (pX < 0 || UB < pX) return false;
if (pY < 0 || UB < pY) return false;
return true;
};
//変位ベクトルを90度回転させたベクトルを加算
int Kaiten90DoX = pHeniY;
int Kaiten90DoY = -pHeniX;
int wkX = pCurrX + Kaiten90DoX;
int wkY = pCurrY + Kaiten90DoY;
if (IsBanJyou(wkX, wkY) == false || pTargetArr[wkX, wkY] == false)
return false;
//正方形の対角線の変位ベクトルを加算
wkX = pCurrX + pHeniX + Kaiten90DoX;
wkY = pCurrY + pHeniY + Kaiten90DoY;
if (IsBanJyou(wkX, wkY) == false || pTargetArr[wkX, wkY] == false)
return false;
return true;
}
//盤面を表示
static void PrintBan(bool[,] pIsBlackArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pIsBlackArr[X, Y]) sb.Append('●');
else sb.Append('○');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
//回転を除外
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);
}
}
}
