using System;
using System.Collections.Generic;
class Program
{
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int CoinCnt;
internal bool[,] IsSetArr;
}
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.CoinCnt = 0;
WillPush.IsSetArr = new bool[8, 8];
stk.Push(WillPush);
var AnswerArrList = new List<bool[,]>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (Popped.CoinCnt == 16) {
AnswerArrList.Add(Popped.IsSetArr);
continue;
}
//次に配置するコインのX座標は、配置済のコイン数/2で求まる
int X = Popped.CoinCnt / 2;
for (int Y = 0; Y <= Popped.IsSetArr.GetUpperBound(1); Y++) {
//コインが配置不可ならContinue
if (IsOKMasu(X, Y) == false) continue;
//Currentより後の座標でない場合は、Continue
if (X < Popped.CurrX) continue;
if (X == Popped.CurrX && Y <= Popped.CurrY) continue;
//コインが2枚並んだライン上ならContinue
if (Popped.CoinCnt >= 2 && IsExist2CoinsLine(Popped.IsSetArr, X, Y))
continue;
WillPush.CurrX = X;
WillPush.CurrY = Y;
WillPush.CoinCnt = Popped.CoinCnt + 1;
WillPush.IsSetArr = (bool[,])Popped.IsSetArr.Clone();
WillPush.IsSetArr[X, Y] = true;
stk.Push(WillPush);
}
}
RemoveKaiten(AnswerArrList);
for (int I = 0; I <= AnswerArrList.Count - 1; I++) {
Console.WriteLine("解{0}を発見。", I + 1);
PrintBan(AnswerArrList[I]);
}
}
//コインが配置可能なマスかを返す
static bool IsOKMasu(int pX, int pY)
{
if (pX == pY) return false;
if (pX + pY == 7) return false;
return true;
}
//コインが2枚並んだラインの有無を返す
static bool IsExist2CoinsLine(bool[,] pIsSetArr, int pX1, int pY1)
{
Func<int, int, bool> Is2CoinsLine = (pX2, pY2) =>
{
int HeniX = pX2 - pX1;
int HeniY = pY2 - pY1;
DeriveHeniNBai(ref HeniX, ref HeniY);
int CoinCnt = 0;
for (int X = pX1, Y = pY1;
0 <= X && X <= pIsSetArr.GetUpperBound(0)
&& 0 <= Y && Y <= pIsSetArr.GetUpperBound(1); X += HeniX, Y += HeniY) {
if (pIsSetArr[X, Y] && ++CoinCnt == 2) return true;
}
for (int X = pX1, Y = pY1;
0 <= X && X <= pIsSetArr.GetUpperBound(0)
&& 0 <= Y && Y <= pIsSetArr.GetUpperBound(1); X -= HeniX, Y -= HeniY) {
if (pIsSetArr[X, Y] && ++CoinCnt == 2) return true;
}
return false;
};
for (int X = 0; X <= pIsSetArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pIsSetArr.GetUpperBound(1); Y++) {
if (pIsSetArr[X, Y] && Is2CoinsLine(X, Y))
return true;
}
}
return false;
}
//2点間の変位ベクトルのn分の1倍を求める
static void DeriveHeniNBai(ref int pX, ref int pY)
{
if (pX == 0) { pY = 1; return; }
if (pY == 0) { pX = 1; return; }
while (true) { //互いに素になるまで最大公約数で割る
int GCD = DeriveGCD(Math.Abs(pX), Math.Abs(pY));
if (GCD == 1) return;
pX /= GCD;
pY /= GCD;
}
}
//ユークリッドの互除法で2数の最大公約数を求める
static int DeriveGCD(int pVal1, int pVal2)
{
int WarareruKazu = Math.Max(pVal1, pVal2);
int WaruKazu = Math.Min(pVal1, pVal2);
while (true) {
int Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
//回転を除外
static void RemoveKaiten(List<bool[,]> pTargetList)
{
const int UB = 8 - 1;
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[,] pIsSetArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pIsSetArr.GetUpperBound(0); Y++) {
for (int X = 0; X <= pIsSetArr.GetUpperBound(1); X++) {
if (pIsSetArr[X, Y]) sb.Append('●');
else sb.Append('□');
}
sb.AppendLine();
}
Console.Write(sb.ToString());
}
}
