using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 5 - 1;
struct JyoutaiDef
{
internal char[,] BanArr;
internal int CurrX;
internal int CurrY;
internal int CoinCnt10;
internal int CoinCnt100;
}
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
WillPush.BanArr[X, Y] = ' ';
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.CoinCnt10 = 0;
WillPush.CoinCnt100 = 0;
stk.Push(WillPush);
var PushedBanULongSet = new HashSet<ulong>();
int AnswerCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.CoinCnt10 == 5 && Popped.CoinCnt100 == 3) {
AnswerCnt++;
Console.WriteLine("解{0}を発見", AnswerCnt);
PrintAnswer(Popped.BanArr);
continue;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB) continue;
Action<bool> PushSyori = pWillSet10 =>
{
if (IsValid(Popped.BanArr, Popped.CurrX, Popped.CurrY, pWillSet10)) {
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
if (pWillSet10) {
WillPush.BanArr[Popped.CurrX, Popped.CurrY] = '十';
WillPush.CoinCnt10 = Popped.CoinCnt10 + 1;
WillPush.CoinCnt100 = Popped.CoinCnt100;
}
else {
WillPush.BanArr[Popped.CurrX, Popped.CurrY] = '百';
WillPush.CoinCnt10 = Popped.CoinCnt10;
WillPush.CoinCnt100 = Popped.CoinCnt100 + 1;
}
HashSet<ulong> wkULongSet = BanToULongSet(WillPush.BanArr);
if (PushedBanULongSet.Overlaps(wkULongSet) == false) {
PushedBanULongSet.Add(wkULongSet.First());
stk.Push(WillPush);
}
}
};
//10円を配置する経路
if (Popped.CoinCnt10 < 5) PushSyori(true);
//100円を配置する経路
if (Popped.CoinCnt100 < 3) PushSyori(false);
//コインを配置しない経路のPush
WillPush.BanArr = Popped.BanArr;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.CoinCnt10 = Popped.CoinCnt10;
WillPush.CoinCnt100 = Popped.CoinCnt100;
//特殊枝切り
if ((WillPush.CurrX == 3 && WillPush.CurrY == 2 && WillPush.CoinCnt10 == 0) == false)
stk.Push(WillPush);
}
}
//座標を引数として、配置済の硬貨の効き筋ならFalseを返す
static bool IsValid(char[,] pBanArr, int TargetX, int TargetY, bool pWillSet10)
{
char RevChar = (pWillSet10 ? '百' : '十');
//上チェック
for (int Y = TargetY - 1; 0 <= Y; Y--) {
if (pBanArr[TargetX, Y] == RevChar) return false;
}
//左チェック
for (int X = TargetX - 1; 0 <= X; X--) {
if (pBanArr[X, TargetY] == RevChar) return false;
}
//左上チェック
for (int X = TargetX - 1, Y = TargetY - 1;
0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y--) {
if (pBanArr[X, Y] == RevChar) return false;
}
//右上チェック
for (int X = TargetX + 1, Y = TargetY - 1;
0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y--) {
if (pBanArr[X, Y] == RevChar) return false;
}
return true;
}
//盤面をULong型のSetに変換
static HashSet<ulong> BanToULongSet(char[,] pBanArr)
{
var WillReturn = new HashSet<ulong>();
var NumListArr = new List<ulong>[8];
for (int I = 0; I <= NumListArr.GetUpperBound(0); I++) {
NumListArr[I] = new List<ulong>();
}
Func<char, ulong> wkFunc = (pChar) =>
{
if (pChar == '十') return 1;
if (pChar == '百') return 2;
return 0;
};
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
NumListArr[0].Add(wkFunc(pBanArr[X, Y]));
NumListArr[1].Add(wkFunc(pBanArr[X, UB - Y]));
NumListArr[2].Add(wkFunc(pBanArr[UB - X, Y]));
NumListArr[3].Add(wkFunc(pBanArr[UB - X, UB - Y]));
NumListArr[4].Add(wkFunc(pBanArr[Y, X]));
NumListArr[5].Add(wkFunc(pBanArr[UB - Y, X]));
NumListArr[6].Add(wkFunc(pBanArr[Y, UB - X]));
NumListArr[7].Add(wkFunc(pBanArr[UB - Y, UB - X]));
}
}
foreach (List<ulong> EachNumList in NumListArr) {
//3の25乗=847288609443なので3進数ならオーバーフローしない
ulong WillAdd = 0;
foreach (ulong EachInt in EachNumList) {
WillAdd *= 3;
WillAdd += EachInt;
}
WillReturn.Add(WillAdd);
}
return WillReturn;
}
//解を出力
static void PrintAnswer(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
char CurrChar = pBanArr[X, Y];
sb.Append(CurrChar == ' ' ? '□' : CurrChar);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}